- Adaptive Radix Tree (Trie)
Radix Tree #
- The height depends on the length of the keys
- Inner node
- array of $2^{s}$ pointers
- use s bit chunk of the key to index into array
s: span
Adaptive Radix Tree #
- Adaptively use different node sizes
- use span of 8 bits
Inner node #
- Node4, Node16 (Linear search)
- Node48, Node 256 (direct index)
Optimization #
- Path compression
- Lazy expansion
Binary–Comparable Keys #
- String: naturally sorted in radix tree
- How about int, float … (negative two-complement signed integers are lexicographically greater than positive integers)