$arr_19 ), array( 3, false, $arr_20, $arr_24 ), array( 2, false, "\" />", $arr_25 ) ) ); ?> $arr_27 ), array( 3, false, $arr_28, $arr_30 ), array( 2, false, "\" />\n\n", $arr_31 ) ) ); ?> array( 2, false, false, $arr_9 ), array( 4, $arr_10, "if", $arr_245, $arr_248 ), array( 2, false, "\n", $arr_249 ) ) ); ?> rr_466 ), array( 4, $arr_467, "if", $arr_482, $arr_484 ), array( 2, false, "\n", $arr_485 ) ) ); ?> Google Releases C++ B-Tree Template Library » Linux Magazine
 

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.

comments powered by Disqus

Issue 152/2013

Tag Cloud

Bruce Byfield Gnome KDE Kernel Linux Linux Pro Magazine Open Source Projects Red Hat Ubuntu events foss free software google

News