| ▲ | crest an hour ago |
| Binary trees have worse cache locality. The cost of accessing memory has grown so much compared to computation that supposedly slower "heavy weight" data structures are worth it now (as in the last 10-20 years). |
|
| ▲ | eventualcomp an hour ago | parent [-] |
| A b-tree isn't a binary tree. B doesn't officially stand for binary either, see History[0]. [0] https://en.wikipedia.org/wiki/B-tree |
| |
| ▲ | jjmarr an hour ago | parent [-] | | I'm guessing their point is unlike binary trees which have two children per node, B trees can have as many children per node is best for cache locality/SIMD/etc. Which despite being "heavyweight" (wasted space if not all children per node are occupied) is faster in practice because it's cheaper to preload large unused blocks to cache rather than only access memory when it is needed. |
|