See also: > C++ standard libraries commonly implement the map and set data structures using Red-Black trees, which store one element per node, requiring three

See also: > C++ standard libraries commonly implement the map and set data structures using Red-Black trees, which store one element per node, requiring three pointers plus one bit of information per element to keep the tree balanced. By comparison, B-tree containers store a number of elements per node, thereby reducing pointer overhead and saving a significant amount of memory. For small data types, B-tree containers typically reduce memory use by 50 to 80% compared with Red-Black tree containers. https://opensource.googleblog.com/2013/01/c-containers-that-save-memory-and-time.html https://opensource.googleblog.com/2013/01/c-containers-that-... And also: > However, there are many reasons why B-trees are often a good choice for in-memory collections.The first reason is cache locality. When searching for a key in a binary tree, the algorithm would visit up to logN elements that are very likely dispersed in memory. On a B-tree, this search will consist of two phases — intra-node search and descending the tree — executed one after another. And while descending the tree doesn’t differ much from the binary tree in the aforementioned sense, intra-node search will access keys that are located next to each other, thus making much better use of CPU caches. https://www.scylladb.com/2021/11/23/the-taming-of-the-b-trees/ https://www.scylladb.com/2021/11/23/the-taming-of-the-b-tree... And also, also: > In this paper, we conduct a comprehensive performance study on five state-of-the-art indices, Masstree, BwTree, FAST, ART and PSL, with respect to throughput, scalability, latency, memory consumption and cache miss rate. According to our results, PSL achieves a similar query performance in terms of get throughput to a read-only index, FAST, and meanwhile performs up to 5x, 0.3x and 2.5x faster than Masstree, ART and BwTree respectively. Another interesting point observed in the results is that the performance of BwTree drops significantly when the workload is write-only, probably due to the contenction caused by the frequent fails on the hot blocks. FAST and ART win the competition on the cost of memory space, leading other indices with a saving factor between 20%-100%. Our experiments also reveal that for the dense dataset, ART and BwTree, which belong to indices built based on tries, may be the suitable candidates for a better overall performance. https://www.comp.nus.edu.sg/~dbsystem/download/xie-icde18-paper.pdf https://www.comp.nus.edu.sg/~dbsystem/download/xie-icde18-pa...