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

Issue 269/2023

Buy this issue as a PDF

Digital Issue: Price $12.99
(incl. VAT)

Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Find SysAdmin Jobs