Re:In-memory hash tree implementation
by freefrag on Sunday March 27, 2016 @09:41AM
(#11369908)
What's the advantage of using wider trees at every level? Asymptotically wouldn't you get the same behaviour with a binary tree?
[ Parent
| on HN ]
Advantage: constant level time complexity with better space utilization.
The binary tree with the binary-search searching strategy has a time complexity O(logN), which is higher than htree's.
This htree is mainly for memory bounded cases.
Re:In-memory hash tree implementation
by aweinstock on Sunday March 27, 2016 @10:13AM
(#11370005)
Higher branching factor gets you a better constant factor because the depth of the tree is the base-(branching factor) logarithm of the number of nodes. The number of pointers you need to follow to reach a leaf is equal to the depth of the tree, and pointer-dereferences are likely to cause a cache miss, which is a relatively slow operation.
You're correct that asymptotically, it's the same thing.