Class BTree

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

class BTree(ValueT, ulong NodeSizeV = 256, alias ValueLessF)
  
if (is(typeof(binaryFun!ValueLessF(ValueT.init, ValueT.init)) : bool));

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.

Properties

NameTypeDescription
root[get] inout(BTree.Node)The root Node of the B-Tree.

Methods

NameDescription
_isValueEqual (v1, v2) Wrapper for ValueLessF that will fail at compile time if its signature does not match.
begin ()
clear ()
equalRange (v) Find a range of elements whose value is equal to 'v'.
getMinDegree () Gets the minimum degree of the B-Tree.
insert (v) Inserts a new value into the BTree.
lowerRange (v) Returns a range of all elements strictly less than 'v'.
opBinaryRight (value) Implements the "in" operator for membership.
opIndex () A full slice for expressions of the form: myBTree[].
opSlice (a, b) Defines the structure of a slice for slice expression of the form: myBTree[a..b].
remove (v) Removes a value and value from the BTree if it exists.
upperRange (v) Returns a range of all elements strictly greater than 'v'.

Inner classes

NameDescription
Node A node in the BTree.

Inner structs

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

Parameters

NameDescription
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.

Example

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());

Example

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");

Example

Use case using comparison by a specific value. 

struct Structo {
  int _id;
  string _data;
}

// This time use the string _data field, but only the first two characters.
auto btree2 = new BTree!(Structo, 1024, "a._data[0..2] > b._data[0..2]");

// Lambdas may also be used.
auto btree3 = new BTree!(
    Structo,  // The type of thing being stored in the BTree.
    1024,  // The size of a node in bytes.
    (a, b) => a._data[0..2] > b._data[0..2]);  // Determine if one value is less than another.

btree3.insert(Structo(1, "RW-Fish"));
btree3.insert(Structo(2, "LG-Sheep"));
btree3.insert(Structo(3, "BK-Bunny"));
assert(!btree3.equalRange(Structo(0, "RW")).empty());
assert(btree3.equalRange(Structo(0, "ZM")).empty());
assert(btree3.equalRange(Structo(0, "BK")).front()._data == "BK-Bunny");

Example

Use case compatible with class comparing operator overrides: 

class Thingy {
  int _a, _b;

  this(int a, int b) {
    _a = a;
    _b = b;
  }

  int opCmp(in Thingy o) const {
    return _a < o._a ? -1
        : _a > o._a ? 1
        : _b < o._b ? -1
        : _b > o._b ? 1
        : 0;
  }

  override
  bool opEquals(in Object o) const {
    Thingy other = cast(Thingy) o;
    if (other is null) return false;
    return _a == other._a && _b == other._b;
  }
}

auto btree = new BTree!Thingy();
btree.insert(new Thingy(1, 2));
btree.insert(new Thingy(1, 3));
btree.insert(new Thingy(2, 1));
btree.insert(new Thingy(1, 2));

assert(!btree.equalRange(new Thingy(2, 1)).empty());
assert(btree.equalRange(new Thingy(2, 2)).empty());