Package btree implements in-memory B-Trees of arbitrary degree.
btree implements an in-memory B-Tree for use as an ordered data structure.
It is not meant for persistent storage solutions.
It has a flatter structure than an equivalent red-black or other binary tree,
which in some cases yields better memory usage and/or performance.
See some discussion on the matter here:
Note, though, that this project is in no way related to the C++ B-Tree
implementation written about there.
Within this tree, each node contains a slice of items and a (possibly nil)
slice of children. For basic numeric values or raw structs, this can cause
efficiency differences when compared to equivalent C++ template code that
stores values in arrays within the node:
These issues don't tend to matter, though, when working with strings or other
heap-allocated structures, since C++-equivalent structures also must store
pointers and also distribute their values across the heap.
This implementation is designed to be a drop-in replacement to gollrb.LLRB
trees, (http://github.com/petar/gollrb), an excellent and probably the most
widely used ordered tree implementation in the Go ecosystem currently.
Its functions, therefore, exactly mirror those of
llrb.LLRB where possible. Unlike gollrb, though, we currently don't
support storing multiple equivalent values.
There are two implementations; those suffixed with 'G' are generics, usable
for any type, and require a passed-in "less" function to define their ordering.
Those without this prefix are specific to the 'Item' interface, and use
its 'Less' function for ordering.