3 ms·
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 n
by aidenn0 2y ago
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 https://cr.yp.to/critbit.html
- fweimer 2y agoB-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.
- crest 2y agoYes 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.
- shpongled 2y agoSomething 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.
- aidenn0 2y agoFor very small number of keys, an array with linear searching can win out.