Adaptive radix trees: compress shared paths, adapt the branches

In a bytewise trie, an internal branch selects the next key byte. Several keys beginning with the same bytes follow the same path until they differ. Path compression replaces a chain with only one meaningful child at each step by a stored prefix and a later branch. Lookup must still establish that the compressed prefix matches the query; removing intermediate nodes does not authorize ignoring their bytes. Leaf validation may compare a complete key, especially in implementations that store only part of a long compressed prefix directly in the node.

Variable-length keys need an unambiguous way to distinguish a key from its extension, such as an appropriate terminal representation. The strings a and ab must not become indistinguishable when the first ends. Bytewise order also needs to match the intended database comparison. Unsigned fixed-width integers can use an order-preserving big-endian representation, but signed integers, floating-point values, and collated text require additional rules. Raw UTF-8 byte order is not a universal replacement for a database collation, and equality semantics must remain consistent with lookup.

The original ART design uses Node4, Node16, Node48, and Node256 families to accommodate different numbers of byte-labeled children. Small nodes store compact key-byte and child arrays. A Node48 uses a byte-indexed mapping into a smaller child-reference array; a Node256 can directly index a child array by byte. Those choices trade selection work and metadata against unused pointer slots. They are specific published design mechanisms, not a claim that every structure called a radix tree has those names or exact machine-byte sizes.

When a node outgrows its representation, insertion can allocate a larger layout and preserve its child mapping; deletion may permit shrinking under the implementation's policy. Path compression and node adaptation solve separate problems: one reduces unary path overhead, while the other handles branching density. Their interaction with concurrent readers needs publication and reclamation rules beyond the sequential layout. Memory measured per key includes leaves and key storage as well as internal nodes, so counting only the smallest internal representation can dramatically understate the footprint.

A radix structure can support ordered traversal only if its encoding and child iteration preserve the desired order. Hash tables answer a different navigation question, while B-trees group entries into pages with different fanout and cache properties. Compare the same key types, distributions, update ratios, and range requests. Long common prefixes can save node material while still requiring byte comparisons. Very short keys may make other overhead dominant. A benchmark result for one in-memory structure and machine does not establish a universal winner for persistent or concurrent databases.

The cache lab isolates a tiny working-set effect. Reset, set C=2 and s=8, predict two misses and fourteen hits among the sixteen initial requests, then Play or Step. Separately Reset, set C=2 and s=4, predict zero hits for a four-address cycle, then Play or Step. These capacity values count toy addresses, not ART node bytes. The instrument cannot compress prefixes or switch node families. Use it to motivate measuring whether a compact representation actually reduces the active address working set, then perform the separate encoding and full-key correctness checks.