Google's C++ library for B-tree containers

Google's Open Source Programs Office has released a new C++ template library, called cpp-btree, which offers various containers designed to work in the same way as the map, set, multimap and multiset standard implementations. The difference is that these are implemented using B-trees. Typically, the C++ Standard Template Library's containers are implemented using structures called red-black trees.

That approach involves storing one element per node, which requires three pointers and 1 bit per element. The alternative approach in Google's new library uses B-trees and should significantly reduce memory requirements by storing a number of elements per node. For example, Google says that, on a 32-bit operating system, a set<int32_t> generates an overhead of 16 bytes for all 4-byte-sized set elements, while the btree_set<int32_t> B-tree equivalent only generates around 1 byte per element. The developers note that access times can also be reduced for large containers because the cache is used differently.

However, there is one difference in terms of compatibility: insertions into and deletions from B-tree containers invalidate existing iterators. To prevent mistakes in this area, the developers have also implemented "safe" versions of the containers that create backup copies and reposition the iterator after use.

The library has been released under the Apache 2.0 License and can be downloaded from the project's web site.

(djwm)