Google Releases C++ B-Tree Template Library

Feb 07, 2013

C++ B-Tree offers memory and time advantages over standard containers.

Google has announced C++ B-Tree, a C++ template library that implements ordered in-memory containers based on a B-tree data structure. This library provides the following containers: btree_map, btree_set, btree_multimap, and btree_multiset.

According to the website, C++ B-tree containers have some advantages over standard containers, which are typically implemented using Red-Black trees. B-trees keep disk seeks to a minimum, and C++ B-tree containers make better use of the cache. The announcement, posted on Google Open Source Blog says that, “for small data types, B-tree containers typically reduce memory use by 50 to 80% compared with Red-Black tree containers.”

The Google blog states, “B-trees are well-known data structures for organizing secondary storage, because they are optimized for reading and writing large blocks of data. But the same property that makes B-trees appropriate for use with databases and file systems also makes them appropriate for use in main-memory, just with smaller blocks.”

C++ B-tree containers do have some disadvantages. For example, modifying a C++ B-tree container will invalidate all outstanding iterators on that container. However, the library contains “safe variations” on the four containers to address this drawback. C++ B-tree containers have the same interface as the standard C++ containers.

Related content

comments powered by Disqus

Issue 180/2015

Buy this issue as a PDF

Digital Issue: Price $9.99
(incl. VAT)


njobs Europe
Njobs Netherlands Njobs Deutschland Njobs United Kingdom Njobs Italia Njobs France Njobs Espana Njobs Poland
Njobs Austria Njobs Denmark Njobs Belgium Njobs Czech Republic Njobs Mexico Njobs India Njobs Colombia