Hacker News Reader

It's been a while since I last tried things, but I found crit-bit trees[1] to be much faster than b-trees. Hash array-mapped tries are also good if you don't need the things that trees give you (e.g. in-order traversal, get all values in a certain range).

1: https://cr.yp.to/critbit.html

View on HN

Something like a radix trie can give you the in-order traversal and range query aspect, while still keeping some of the nice properties of HAMTs. In practice though (for my domain, scientific floating point data), I have found that b-trees and simple sorted arrays with binary search (sadly) outperform radix tries and cleverer solutions.

For very small number of keys, an array with linear searching can win out.

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.

Reply on news.ycombinator.com