Hacker News Reader

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.

View on HN

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.

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.

Reply on news.ycombinator.com