BTree

A B-Tree implementation based upon "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein.

B-Trees are both smaller and faster than most implementations of set/map. The red-black tree implementation of a set/map typically has an overhead of 3 pointers (left, right, and parent) plus the node color information for each stored value. This B-Tree implementation stores multiple values on fixed size nodes (usually 256 bytes) and does not store child pointers for leaf nodes.

The packing of multiple values into each node of a B-Tree also improves cache locality which translates into faster operations.

Because nodes contain both node pointers and values, a BTree will not have good performance when used with large types that are passed by value, such as large structs.

As always, using the BTree with class objects, which are passed by reference, also avoids storage in the BTree itself.

final

class BTree (

ValueT

size_t NodeSizeV = 256

alias ValueLessF = "a < b"

) if (

is(typeof(binaryFun!ValueLessF(ValueT.init, ValueT.init)) : bool)

) {

enum MIN_DEGREE;

enum MAX_DEGREE;

this();

inout(Node) root [@property getter];

size_t length [@property getter];

bool empty [@property getter];

Iterator begin();

Iterator end();

Range opIndex();

ValueT[2] opSlice(ValueT a, ValueT b);

Range opIndex(ValueT[2] slice);

Range equalRange(ValueT v);

Range lowerRange(ValueT v);

Range upperRange(ValueT v);

void clear();

void insert(ValueT v);

bool opBinaryRight(ValueT value);

void remove(ValueT v);

struct Iterator;

struct Range;

class Node;

}

Constructors

this this(): Undocumented in source.

Members

Classes

Node class Node: A node in the BTree.

Functions

begin Iterator begin(): / /
clear void clear(): / /
end Iterator end(): Undocumented in source. Be warned that the author may not have intended to support it.
equalRange Range equalRange(ValueT v): Find a range of elements whose value is equal to 'v'.
insert void insert(ValueT v): Inserts a new value into the BTree.
lowerRange Range lowerRange(ValueT v): Returns a range of all elements strictly less than 'v'.
opBinaryRight bool opBinaryRight(ValueT value): Implements the "in" operator for membership.
opIndex Range opIndex(): / / A full slice for expressions of the form: myBTree[].
opIndex Range opIndex(ValueT[2] slice): Undocumented in source. Be warned that the author may not have intended to support it.
opSlice ValueT[2] opSlice(ValueT a, ValueT b): Defines the structure of a slice for slice expression of the form: myBTreea..b.
remove void remove(ValueT v): Removes a value and value from the BTree if it exists.
upperRange Range upperRange(ValueT v): Returns a range of all elements strictly greater than 'v'.

Manifest constants

MAX_DEGREE enum MAX_DEGREE;: Undocumented in source.
MIN_DEGREE enum MIN_DEGREE;: Undocumented in source.

Properties

empty bool empty [@property getter]: Undocumented in source. Be warned that the author may not have intended to support it.
length size_t length [@property getter]: Undocumented in source. Be warned that the author may not have intended to support it.
root inout(Node) root [@property getter]: The root Node of the B-Tree.

Structs

Iterator struct Iterator: Lower level iterators on the tree.
Range struct Range: D-style Ranges.

Parameters

ValueT: The element type to be organized by the BTree.
NodeSizeV: The size in bytes of a node in the BinaryTree. Values are chosen to optimize performance depending on usage. For example, a value of 4096 bytes may be useful when retrieving items from disk, or the value 256 bytes to assure good use of CPU caches. The default value is 256 bytes.
ValueLessF: A less-than comparison function for values, either a function or a string representing a function as described by std.functional.binaryFun.

Examples

Simple use case with primitive types.

auto btree = new BTree!int();
btree.insert(2);
btree.insert(3);
btree.insert(4);
btree.insert(1);
btree.insert(4);

// equalRange() provides a range used to get the tree values equal to the given search value.
auto r = btree.equalRange(2);
assert(!r.empty());
assert(r.front() == 2);

// There can be more than one match.
r = btree.equalRange(4);
assert(!r.empty());
assert(r.front() == 4);
r.popFront();
assert(!r.empty());
assert(r.front() == 4);

// If there is not match, an empty range is returned.
r = btree.equalRange(-3);
assert(r.empty());

Use case using comparison by a specific value.

struct Structo {
  int _id;
  string _data;
}

// Organize the BTree using the _id field as the value used for comparison.
auto btree = new BTree!(Structo, 1024, "a._id < b._id");
btree.insert(Structo(1, "Good Day"));
btree.insert(Structo(2, "Guten Tag"));
btree.insert(Structo(3, "G'Day Mate"));
assert(!btree.equalRange(Structo(2)).empty());
assert(btree.equalRange(Structo(4)).empty());
assert(btree.equalRange(Structo(3)).front()._data == "G'Day Mate");