BenoitP
3 days ago
What would be nice with that would be an additional explanation as to their popularity.
Why not binary trees? Because random memory fetch can incur high latency. How to size max node size? -> Aim for L1 or cache line size; Just like like we make ring buffers fit into L2/L3.
bootsmann
3 days ago
Isn't the biggest usecase for B-trees in environments where we don't hold the data in memory (i.e. databases)? There the block size is optimized to balance the cost benefit of one more disk seek vs one more list traversal.
bddicken
3 days ago
The corresponding blog post covers this a bit:
https://planetscale.com/blog/btrees-and-database-indexes
In short, B+trees are good because the nodes can be set to match the size of a disk page.