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

  • Tech Tools
    • Google Releases C++ B-Tree Template Library
    • Oracle Releases MySQL 5.6
    • Eclipse Releases Hudson 3.0
  • Embedded File System 1.0 – Filesystem in a File

    The Embedded File System (EFS) library, of which the first stable version, 1.0, has just been released, is a C++ library that creates a virtual filesystem in a file.

  • Kernel News

    This month in Kernel News: Chasing the Dream; The Power of the FUSE Side; NTFS3 Maintainership Issues: and Crashing and Warning.

comments powered by Disqus
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters

Support Our Work

Linux Magazine content is made possible with support from readers like you. Please consider contributing when you’ve found an article to be beneficial.

Learn More