Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

B-trees are supposed to address the bad cache behavior of binary trees because they are generally much shallower. Crit-bit trees as originally described do not have this property.


Yes and no. A lot of it depends on how the low fan-out tree is laid out in memory. Also some binary tree structures (e.g. binary heaps) are often stored in an array with one child implied and only the other child index stored in each node. In such cases chasing down the child references may no be more expensive that searching inside a B(+)-tree node.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: