3 ms·
That's true for on-disk b-trees which typically have large node sizes (typically 4KB), but in-memory btrees tend to aim for CPU cache lines (typically a small m
by marginalia_nu 2y ago
That's true for on-disk b-trees which typically have large node sizes (typically 4KB), but in-memory btrees tend to aim for CPU cache lines (typically a small multiple of 32B), and thus do actually waste a fair amount of memory with their comparatively low branching factor, and thus relatively large number of branches compared to their number of leaves.
- pclmulqdq 2y agoThe waste of abseil's b-tree, for example, is small per value: https://abseil.io/about/design/btree https://abseil.io/about/design/btree The efficiency compared to hash tables very much does carry over to the small b-trees used for in-memory data.