4 ms·
Btrees don't waste much memory, while hash tables have to have excess capacity if you want them to go fast.
by pclmulqdq 2y ago
Btrees don't waste much memory, while hash tables have to have excess capacity if you want them to go fast.
- marginalia_nu 2y agoThat'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.