Repository files navigation

Code in this repository is based onGoogle's B-tree implementation.

C++ B-tree is a template library that implements ordered in-memory containersbased on a B-tree data structure. Similar to the STLstd::map,std::set,std::multimap, andstd::multiset templates, this library providesbtree::map,btree::set,btree::multimap andbtree::multiset.

This difers from the original project by Google in that containers behave morelike modern STL (C++17) and are an almost drop-in replacements (except for theiterator invalidation, see below); including support foremplace andtry_emplace as well as values in the map not needing to have a defaultconstructor.

C++ B-tree containers have a few advantages compared with the standardcontainers, which are typically implemented using Red-Black trees. Nodes in aRed-Black tree require three pointers per entry (plus 1 bit), whereas B-treeson average make use of fewer than one pointer per entry, leading tosignificant memory savings. For example, aset<int32_t> has an overheadof 16 bytes for every 4 byte set element (on a 32-bit operating system); thecorrespondingbtree::set<int32_t> has an overhead of around 1 byte per setelement.

B-trees are widely known as data structures for secondary storage, because theykeep disk seeks to a minimum. For an in-memory data structure, the same propertyyields a performance boost by keeping cache-line misses to a minimum. C++ B-treecontainers make better use of the cache by performing multiple key-comparisonsper node when searching the tree. Although B-tree algorithms are more complex,compared with the Red-Black tree algorithms, the improvement in cache behaviormay account for asignificant speedup in accessing large containers.

The C++ B-tree containers are not without drawbacks, however. Unlike thestandard STL containers, modifying a C++ B-tree containerinvalidates all outstanding iterators on that container.