The C++ B-Tree has interfaces similar to that of the standard STL map, set, multimap, and multiset containers and is most commonly used for databases and file-systems but have found usage for storage of data in system memory as well. “We’re pleased to announce C++ B-Tree, a C++ template library that implements B-tree containers with an analogous interface to the standard STL map, set, multimap, and multiset containers”, noted Google in its Open Source Blog.

According to statistics published by Google, by using B-tree containers memory use can be reduced from around 50 to 80% as compared to Red-Black tree containers. Explaining the reason behind the reduction in memory usage Google noted that unlike Red-Black tree containers B-Tree containers store multiple elements per node “thereby reducing pointer overhead and saving a significant amount of memory.”

According to the Android maker, B-trees can also improve performance while saving memory when dealing with large data-sets. You can find the Google code as cpp-btree here.