Tries, ART and skip lists

When does a trie beat comparison search, and why is a skip list chosen for concurrency rather than speed?

Trie, radix tree and ART

The constraint. Comparison search costs O(log n) comparisons of whole keys. Digital search (a trie: a tree that follows the key one character or byte at a time) costs O(k) for key length k, independent of n. For a billion short keys that is a real difference. Tries also give prefix operations for free ("all keys starting with PUN") and never store a shared prefix twice.

Why the naive version fails, and what ART fixes

A naive trie node with 256 children (one per byte value) is 256 × 8 = 2 KB of pointers, almost all null. For sparse real-world key sets, space amplification reaches 10 to 100×. ART (Adaptive Radix Tree) fixes this with two ideas:

• Adaptive node types with 4, 16, 48 or 256 children, chosen by the actual number of children;
• Path compression: collapse a chain of single-child nodes into one edge.

The structure sizes itself to the density of the data, not to the size of the key space. The general principle: the cost of a sparse structure is dominated by the sparsity, so winning designs adapt their shape to observed density rather than to the domain. Roaring bitmaps (Bit-level structures) do exactly the same at bit level.

A trie is a memory structure; a B-tree is a block structure

A trie descent is k dependent pointer chases. In memory at about 80 ns each, a 16-byte key costs 16 × 80 ns ≈ 1.3 µs, which is fine. On disk at 100 µs each it is 16 × 100 µs = 1.6 ms, against a B-tree's two I/Os (about 0.2 ms). The depth is the problem: trie depth is set by key length, which has nothing to do with the medium's transfer unit, so a trie cannot do the one thing a B-tree does, which is tune its fanout to the hardware. That explains where each is deployed, and it is a cleaner discriminator than anything in a complexity table.

Where tries appear in data engineering

• Longest-prefix-match IP routing is literally a radix trie: a router finds the most specific network that matches a destination address.
• ART is a standard in-memory index in modern analytical engines.
• Lucene's term dictionary is an FST (finite-state transducer): a trie minimized into a DAG (a graph with shared sub-paths) so that the term index of a large text corpus fits in memory while the postings (the lists of documents per term) stay on disk. It is a good example of a structure earning its place purely by fitting in a faster tier.

Skip list

State the honest version first. A skip list is a sorted linked list with extra "express" pointers that skip ahead; each node gets a random height. Its advantage is not asymptotic: the expected O(log n) equals a balanced tree's. It is not space: about two pointers per node when each node is promoted with probability ½. It is not cache behaviour, which is worse than a B-tree's by a wide margin because every level hop is an independent miss. Anyone who says skip lists are as fast as B-trees for single-threaded lookups is comparing implementations, not structures.

The advantage is the absence of rebalancing. An insert splices a node in with a handful of CAS operations on pointers, each affecting one node, with no structural change propagating upward and no subtree rotation to make atomic. That makes concurrent lock-free insertion practical in a way that concurrent B-tree insertion is not. This is why the skip list is the memtable in LevelDB, RocksDB and HBase and the ordered set in Redis: these workloads are write-heavy with many threads, short-lived, and memory-resident. The structure is chosen for its coordination profile, not its lookup profile.

// Insert at one level of a lock-free skip list (sketch).
// 'pred' and 'succ' were found by a search. Link the new node between them.
new_node->next = succ;
if (!atomic_compare_exchange(&pred->next, &succ, new_node)) {
    // someone changed pred->next first: re-run the search and retry
}

The general mechanism: randomness replaces coordination

Probabilistic balancing replaces a global invariant ("the tree is balanced everywhere"), which needs coordination to maintain, with local randomness, which needs none. You give up worst-case guarantees and you get rid of a synchronization point. It is the same trade as random load balancing, random partition assignment, and the randomized ring in consistent hashing. We call it the Randomization law:

Note how this interacts with the Independence law: randomization works because of an independence assumption, and skew is exactly the case where that assumption fails. That interaction is where most production surprises in this family live.