B-Tree in C++ by Google

I have stumbled upon a B-Tree template library written in C++. The library I found was written by someone from Google and can be downloaded from http://code.Google.com/p/cpp-btree/. According to the authors the advantage over the standard libraries implementing map and set data structures is the memory overhead. Usually those are implemented using Red-Black trees, which store one element per node. In contrast B-Trees can store multiple elements per node and that should result in a significant speed boost.

For more detailed comparison of the standard STL map and set versus aforementioned B-Tree implementation please go to Google-OpenSource.Blogspot.com.

Leave a Reply