4 ms·

Also known as a radix tree, I believe.

• DanielRibeiro 15y ago
  Seems to be so: http://en.wikipedia.org/wiki/Radix_tree http://en.wikipedia.org/wiki/Radix_tree
• rhizome 15y ago
  Years ago we used this at Singshot to evenly distribute numerical assets across subdirectories. Very useful these days for shardy cloudbucket applications.
• deleted 15y ago
  [deleted]
• gsg 15y ago
  Crit-bit trees are not radix trees. A crit-bit tree stores next-different-bit positions at branches and entire values at the leaves, and is searched by following branches depending on the value of the relevant bit in the search key (the "critical bit" which gives the data structure its name). Once a leaf is reached the entire search key is compared to the value at the leaf, which is necessary because a key that is not in the tree might differ at bit positions that are non-critical and would not have been tested during the tree descent. This is a very different arrangement to a radix tree, which is essentially a form of trie.