C++ Btree - Template Library B-tree data structure
C++ B-tree is a template library that implements ordered in-memory containers based on a B-tree data structure. Similar to the STL map, set, multimap, and multiset templates, this library provides btree_map, btree_set, btree_multimap, and btree_multiset.
C++ B-tree containers have a few advantages compared with the standard containers, which are typically implemented using Red-Black trees. Nodes in a Red-Black tree require three pointers per entry (plus 1 bit), whereas B-trees on average make use of fewer than one pointer per entry, leading to significant memory savings. For example, a set<int32_t> has an overhead of 16 bytes for every 4 byte set element (on a 32-bit operating system); the corresponding btree_set<int32_t> has an overhead of around 1 byte per set element.