BTree

An implementation of a vanilla B-Tree.

The API should looks closely like the builtin associative arrays. O(lg(n)) insertion, removal, and search time. This BTree is designed to operate even without initialization through makeBTree.

Note: the keys don't need opEquals, but !(a < b) && !(b > a) should imply that a == b

Reference: http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap19.htm

https://en.wikipedia.org/wiki/B-tree

Constructors

this this(int dummy): Constructor.

Destructor

~this ~this(): Destructor. All nodes are cleared.

Postblit

this(this) this(this): Undocumented in source.

Members

Enums

RangeType enum RangeType: Undocumented in source.

Functions

byKey auto byKey(): Return forward range of keys, over all elements.
byKeyValue auto byKeyValue(): Return forward range of a struct that has .key and .value.
byValue auto byValue(): Return forward range of values, over all elements.
contains bool contains(K key): Search for an element.
display void display(): Undocumented in source. Be warned that the author may not have intended to support it.
empty bool empty(): Is this B-Tree empty?
insert bool insert(K key, V value): Insert an element in the container.
length size_t length(): Number of items in the B-Tree.
opBinaryRight inout(V)* opBinaryRight(K key): in operator. Check to see if the given element exists in the container. In case of duplicate keys, it returns one of those, unspecified order.
opIndex inout(V) opIndex(K key): Index the B-Tree by key.
remove size_t remove(K key): Erases an element from the tree, if found.

Manifest constants

minDegree enum minDegree;: Called "t" or "minimum degree" in litterature, can never be < 2. Make it lower (eg: 2) to test tree algorithms. See <digression> below to see why this is not B-Tree "order".

Structs

BTreeRange struct BTreeRange(RangeType type): Btree Range

Variables

maxChildren enum int maxChildren;: Undocumented in source.
maxKeys enum int maxKeys;: Undocumented in source.
minChildren enum int minChildren;: Undocumented in source.
minKeys enum int minKeys;: Undocumented in source.