C ++ library from Google with map and set containers on B-trees

One of the Google employees in 20% of free time developed and laid out under the free license the cpp-btree library (C ++ B-Tree), which contains containers working as map, set, multimap and multiset from the standard template library (STL).

The difference is that STL containers are implemented on red-black trees, and similar cpp-btree containers are implemented on B-trees. At the same time, in certain situations a significant gain is achieved in the use of memory (on small elements) and in performance (on large container sizes).

B-trees are known as a tool for working with disk storage: databases and file systems. But the same properties that give a win there, allow more efficient use of RAM. Each node of the red-black tree contains one element, requires three pointers plus a bit of information on the element for balance. For comparison, containers on B-trees store several items per node, therefore decreasing the overhead of pointers and saving a significant amount of memory.

According to tests, data structures on B-trees take up 50-80% less space compared to red-black trees. The table shows the average number of bytes per item in different types of set / map containers. For example, the standard container set <int32_t> creates an overhead of 16 bytes on each of the many small elements, while the alternative container btree_set <int32_t> creates an overhead of only 1 byte per element.
')

Type of	Insert	B-Tree (32-bit)	Red-Black (32-bit)	B-Tree (64-bit)	Red-Black (64-bit)
set <int32_t>	sorted	4.19	20.00	4.40	40.00
	random	4.90	20.00	5.15	40.00
set <int64_t>	sorted	8.39	24.00	8.80	40.00
	random	9.96	24.00	10.47	40.00
set <string>	sorted	24.57	40.00	33.60	64.00
	random	29.49	40.00	40.74	64.00
map <int32_t, void *>	sorted	8.39	24.00	8.80	48.00
	random	9.96	24.00	10.47	48.00
map <int64_t, void *>	sorted	12.60	28.00	13.20	48.00
	random	15.16	28.00	15.92	48.00
map <string, void *>	sorted	28.67	44.00	38.16	72.00
	random	34.49	44.00	46.53	72.00

On some large containers there is also a gain in access speed due to more efficient use of the cache. The graph shows the average execution time of the insert, depending on the size of the container.


^{Especially for the “Russian friends”, the author of the library explained that he did not sign the Y axis, because the specific time of the operation depends on the equipment used. In this case, for 10 million elements, the operation takes 1.6 microseconds on red-black trees, versus 400 nanoseconds on B-trees. Intel Xeon CPU E5-1650 @ 3.20GHz with L1 = 32K, L2 = 256K, L3 = 12M.}

The developer warns about the difference between cpp-btree and standard containers: since any operations of inserting and deleting nodes into the B-tree will invalidate existing iterators, so if necessary, you need to use secure versions .

via Google Open Source Blog