Compressed Tries - Learning Module

Loading content...

0/276

Radix Trees Overview

The Trie Variant That Powers Infrastructure

Deep within the Linux kernel, managing the mapping between virtual memory addresses and physical pages, sits a radix tree. In network routers around the world, forwarding billions of packets per second, radix trees determine where each packet goes. On your computer right now, radix trees are tracking file system caches, managing device drivers, and coordinating memory access.

Radix trees are not obscure academic curiosities—they are critical infrastructure.

A radix tree is a compressed trie specialized for numeric or binary keys. By exploiting the fixed structure of such keys (32-bit integers, 128-bit IPv6 addresses, memory addresses), radix trees achieve remarkable efficiency: O(w) time complexity for all operations where w is the key width in bits, with low constant factors and minimal memory overhead.

What You Will Learn

By the end of this page, you will understand: • The defining characteristics of radix trees vs general compressed tries • How binary radix trees structure their paths using bit patterns • The multi-bit optimization that reduces tree height • Key real-world applications in operating systems and networking • Implementation strategies used in production systems • The relationship between radix, Patricia, and crit-bit trees

Defining Radix Trees

The Term "Radix":

The word "radix" comes from Latin, meaning "root" (as in the root of a number system). In computing, the radix (or base) of a number system determines how many symbols we use: decimal has radix 10 (digits 0-9), binary has radix 2 (bits 0-1), hexadecimal has radix 16 (0-9, A-F).

A radix tree is a compressed trie where:

Keys are interpreted as sequences in a fixed radix system
The radix determines the maximum branching factor per node
Compression collapses chains of single-branch decisions

Formal Definition:

A radix-k tree (k = radix) for a set S of fixed-width keys is a compressed trie where:

Each edge label is a sequence of symbols from {0, 1, ..., k-1}
The concatenation of edge labels from root to a stored key equals that key's representation in radix k
Internal nodes have ≥2 children (compression invariant)
Keys are typically fixed-width (e.g., 32 bits, 64 bits)

Radix Tree Variants by Base
Variant	Radix (k)	Symbols	Max Branching	Common Use
Binary Radix Tree	2	0, 1	2	IP routing, memory management
Radix-4 Tree	4	0-3	4	Some compression schemes
Radix-16 Tree	16	0-F	16	IPv6 optimization
Radix-256 Tree	256	Bytes	256	String tries, file paths

Binary Radix Trees (The Foundation):

The most fundamental variant uses radix 2—each key is a bit sequence. At every node, we branch based on a bit value (0 or 1). This reduces the conceptual complexity to simple binary decisions.

For a 32-bit integer key:

Maximum tree height without compression: 32 levels
Maximum tree height with compression: 32 levels (worst case) but typically much less
Branching factor per node: 2

Example: Storing 32-bit IPs {192.168.1.1, 192.168.1.2, 10.0.0.1}

In binary:

192.168.1.1 = 11000000.10101000.00000001.00000001
192.168.1.2 = 11000000.10101000.00000001.00000010
10.0.0.1 = 00001010.00000000.00000000.00000001

First bit: 192.168.x.x starts with 1, 10.x.x.x starts with 0 → immediate split at root.

The two 192.168.1.x addresses share 30 bits, differing only in the last bit—perfect for compression.

Why Fixed-Width Keys Matter

Unlike string tries where keys have variable length, radix trees typically work with fixed-width keys (32-bit, 64-bit). This enables optimizations: we know the maximum depth, we can use bit manipulation for navigation, and we don't need separate end-of-word markers—every path to a leaf is a complete key.

Structure and Navigation

Understanding how radix trees organize data requires grasping two concepts: the logical structure (how we think about the tree) and the physical structure (how it's actually implemented).

Logical Structure:

Conceptually, a binary radix tree is a full binary tree where:

The root represents "no bits consumed"
Going left consumes a 0 bit; going right consumes a 1 bit
Each node represents a prefix of all keys in its subtree
Leaves store complete keys or values associated with keys

Physical Structure (Compressed):

The physical tree collapses all unary chains:

Nodes exist only at branch points (where keys diverge)
Each node stores the bit position where it branches
Children are labeled by the bit value (0 or 1) at that position
The path from root to a node implicitly defines the prefix

Navigation Algorithm:

To search for key K in a compressed binary radix tree:

Start at root with bit position 0
At each node, examine the branching bit position P stored in the node
Extract bit P from key K
Follow the child corresponding to that bit value (0 or 1)
Continue until reaching a leaf
Compare the complete key stored at the leaf with K

Why the Final Comparison?

Compressed radix trees are "lazy"—they only check bits at branch points. Two keys that agree at all branch point positions but differ elsewhere would follow the same path. The final comparison catches such false matches.

Example Navigation:

Tree storing {0b1100, 0b1010, 0b0001} with branching at bit positions 0, 2:

root (branch at bit 0)
  ├── 0 → leaf(0b0001)  [only key starting with 0]
  └── 1 → node (branch at bit 2)
          ├── 0 → leaf(0b1010)  [bit 2 is 0]
          └── 1 → leaf(0b1100)  [bit 2 is 1]

Searching for 0b1010:

Bit 0 of 0b1010 = 1 → go right
Bit 2 of 0b1010 = 0 → go left
Reach leaf(0b1010) → compare: match! Return success.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class RadixNode:
    def __init__(self):
        self.bit_position = -1  # Position of discriminating bit
        self.children = [None, None]  # [0-child, 1-child]
        self.key = None  # For leaf nodes: the actual key
        self.value = None  # Associated data
 
def get_bit(key, position, key_bits=32):
    """Extract bit at position (0 = MSB, key_bits-1 = LSB)."""
    return (key >> (key_bits - 1 - position)) & 1
 
def search(root, key, key_bits=32):
    """
    Search for key in radix tree.
    Returns associated value if found, None otherwise.
    Time: O(key_bits) worst case, typically O(tree_height)
    """
    if root is None:
        return None
    
    node = root
    
    # Navigate to leaf
    while node.bit_position != -1:  # While not a leaf
        bit = get_bit(key, node.bit_position, key_bits)
        child = node.children[bit]
        
        if child is None:
            return None  # Key not in tree
        
        node = child
    
    # At leaf: verify exact match
    if node.key == key:
        return node.value
    else:
        return None  # Key differs at non-branching position

Bit Position Interpretation

Be careful with bit position conventions. Some implementations count from LSB (position 0 = rightmost bit), others from MSB (position 0 = leftmost bit). Mixing conventions causes silent corruption. Document your choice and stick to it.

The Patricia Tree Variant

Patricia (Practical Algorithm to Retrieve Information Coded in Alphanumeric) is a specific radix tree variant invented by Donald R. Morrison in 1968. Patricia trees have historical significance and some unique properties.

Key Innovation:

Patricia's key insight was to eliminate redundant nodes entirely by threading the tree—making some pointers point upward to ancestors rather than downward to descendants. This creates a single tree structure for both navigation and storage, reducing memory further.

Patricia Tree Properties:

No external nodes: Every node stores a key (no separate leaf nodes)
Skip counts: Each node stores how many bits to skip before its discriminating bit
Back-pointers: Some children pointers point to ancestors, detected by checking if child's bit position ≤ parent's
Exactly n nodes: For n keys, exactly n nodes (compared to up to 2n-1 for general radix trees)

Skip Counts Explained:

Rather than storing edge labels explicitly, Patricia stores a "skip count"—the number of bits that are implicitly matched before this node's discriminating bit.

Consider storing "1010" and "1011" (4-bit keys):

They agree on bits 0,1,2 and differ at bit 3
A Patricia node stores: skip_to_bit_position = 3
The bits at positions 0,1,2 are implicitly matched by following the path

Back-Pointer Detection:

In Patricia trees, cycle detection is elegant:

When following a child pointer, check if child.bit_position ≤ current.bit_position
If true, this is a back-pointer (we've reached a stored key)
The pointed-to node contains the actual key for verification

This eliminates the need for null pointers and explicit leaf markers.

Patricia Tree vs General Radix Tree
Aspect	Patricia Tree	General Radix Tree
Node count for n keys	Exactly n	Up to 2n-1
Leaf representation	Back-pointers	Null children or leaf nodes
Edge labels	Implicit (skip counts)	Explicit or implicit
Memory per node	Lower	Higher
Implementation complexity	Higher	Lower
Historical usage	Classic networking	Modern systems

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class PatriciaNode:
    """
    Patricia tree node using back-pointers.
    Every node stores a key; no separate leaves.
    """
    def __init__(self, key, bit_position):
        self.key = key  # The key stored at/through this node
        self.bit_position = bit_position  # Skip directly to this bit
        self.left = self  # Default: point to self (back-pointer)
        self.right = self  # Default: point to self
 
def patricia_search(root, key, key_bits=32):
    """
    Search Patricia tree.
    Follow pointers until back-pointer detected (child.bit_pos <= parent.bit_pos)
    """
    if root is None:
        return None
    
    current = root
    prev = None
    
    while prev is None or current.bit_position > prev.bit_position:
        prev = current
        bit = get_bit(key, current.bit_position, key_bits)
        current = current.right if bit else current.left
    
    # 'current' is now pointed to by a back-pointer
    # It contains the candidate key
    if current.key == key:
        return current
    return None

Modern Preference

While Patricia trees are elegant, modern implementations often prefer simpler radix trees with explicit structure. The space savings of Patricia are offset by implementation complexity and cache performance. The Linux kernel, for instance, uses a straightforward radix tree, not a pure Patricia trie.

Multi-Bit Radix Trees

Binary radix trees examine one bit at a time, resulting in up to w levels for w-bit keys. Multi-bit radix trees examine multiple bits per level, reducing tree height at the cost of increased node size.

The Trade-off:

Examining k bits per level: max height = ⌈w/k⌉
Node branching factor: 2^k
Node children array size: 2^k pointers

Example Configurations:

Bits per Level	Height (32-bit key)	Children per Node	Node Size (8-byte ptrs)
1 bit	32	2	16 bytes
2 bits	16	4	32 bytes
4 bits	8	16	128 bytes
8 bits	4	256	2KB

The Linux kernel uses 6 bits per level (64-way branching), balancing height and node size.

Variable Stride (Multibit Patricia/Level Compression):

Advanced implementations use variable stride—different levels examine different numbers of bits based on the data distribution:

Dense regions: Use more bits per level (exploit that many entries exist)
Sparse regions: Use fewer bits per level (avoid wasted pointers)

This optimization is common in IP routing tables where some prefixes are densely populated (many routes share a prefix) and others are sparse.

Level Compression Strategies:

Fixed stride: Same bits per level everywhere. Simple but wastes space in sparse regions.
Variable stride optimization: Pre-analyze data to choose optimal strides per level. Good for static datasets.
Dynamic expansion: Start with small stride; expand only when nodes fill up. Good for dynamic datasets.
Hybrid: Use large stride near root (where almost all paths pass), smaller stride at leaves (where paths diverge).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
BITS_PER_LEVEL = 4
CHILDREN_PER_NODE = 1 << BITS_PER_LEVEL  # 16
 
class MultibitRadixNode:
    def __init__(self):
        self.children = [None] * CHILDREN_PER_NODE
        self.value = None  # Non-None if a key ends here
        self.has_value = False
 
def get_chunk(key, level, key_bits=32):
    """
    Extract BITS_PER_LEVEL bits starting at position level * BITS_PER_LEVEL.
    """
    shift = key_bits - (level + 1) * BITS_PER_LEVEL
    if shift < 0:
        # Handle edge case for non-divisible key widths
        return (key << (-shift)) & (CHILDREN_PER_NODE - 1)
    return (key >> shift) & (CHILDREN_PER_NODE - 1)
 
def multibit_insert(root, key, value, key_bits=32):
    """
    Insert key-value into multi-bit radix tree.
    """
    if root is None:
        root = MultibitRadixNode()
    
    node = root
    num_levels = (key_bits + BITS_PER_LEVEL - 1) // BITS_PER_LEVEL
    
    for level in range(num_levels - 1):
        chunk = get_chunk(key, level, key_bits)
        if node.children[chunk] is None:
            node.children[chunk] = MultibitRadixNode()
        node = node.children[chunk]
    
    # Final level: store value
    final_chunk = get_chunk(key, num_levels - 1, key_bits)
    if node.children[final_chunk] is None:
        node.children[final_chunk] = MultibitRadixNode()
    
    node.children[final_chunk].value = value
    node.children[final_chunk].has_value = True
    
    return root

Memory-Speed Trade-off is Critical

Increasing bits per level reduces tree height but increases node size exponentially. For 8 bits: 256 children × 8 bytes = 2KB per node. If only 3 children are used, you've wasted 2KB - 24 bytes = 99% of the node. Choose stride based on data density, not just performance goals.

Real-World Applications

Radix trees are not theoretical constructs—they power critical infrastructure across operating systems, networking, and databases. Understanding their applications reveals why they're essential knowledge for systems engineers.

Operating System Applications

•Linux Page Cache: The kernel uses radix trees to map file offsets to cached pages. Key = page index in file; Value = pointer to page structure. Enables O(log n) lookup by offset.
•Memory Management: Virtual-to-physical address translation can use radix trees. Some architectures use multi-level page tables that are essentially radix trees.
•IRQ Handling: Mapping interrupt numbers to handlers uses radix tree-like structures for efficient dispatch.
•Device Drivers: Mapping device addresses to driver structures; managing I/O space.
•File Systems: Extent trees in modern file systems (similar to radix) map file regions to disk blocks.

Networking Applications

•IP Routing (Longest Prefix Matching): The classic application. Given destination IP, find the longest matching route prefix. Radix trees enable O(log n) LPM where n is number of routes.
•Packet Classification: Matching packets against rules (ACLs, firewall rules). Multi-dimensional radix trees handle compound keys (IP + port).
•DNS Caching: Domain name lookups cached by radix tree keyed on domain components (reversed for prefix matching).
•Software Defined Networking: Flow tables in SDN switches often use radix tree variants.
•CIDR Block Management: Tracking and allocating IP address blocks using prefix-based structures.

Case Study: Linux Kernel Radix Tree

The Linux kernel's radix_tree was a cornerstone structure for decades (now partially replaced by XArray). Key characteristics:

6 bits per level: 64-way branching, height ≤ 6 for 32-bit keys
Slot tagging: Each slot can be tagged (e.g., "dirty", "ready") for bulk operations
Preallocation support: Can preallocate nodes to avoid allocation in critical paths
Gang lookup: Retrieve multiple entries in a range efficiently
Lock integration: Works with RCU (Read-Copy-Update) for scalable concurrent access

Code Sample (from Linux kernel style):

// Insert a page into the page cache
radix_tree_insert(&mapping->page_tree, offset, page);

// Look up a page
page = radix_tree_lookup(&mapping->page_tree, offset);

// Find pages in a range
radix_tree_gang_lookup(&mapping->page_tree, pages, start, nr_pages);

The API is deceptively simple, but the implementation handles all the complexity of multi-bit indexing, memory allocation, and concurrent access.

Radix Trees in Production Systems
System	Use Case	Key Type	Special Features
Linux Kernel	Page cache	Page index (unsigned long)	Tagging, gang lookup, RCU
FreeBSD	VM object pages	Page index	Sleepable, concurrent
DPDK	Longest prefix match	IPv4/IPv6 address	Lock-free, NUMA-aware
ClickRouter	Routing table	IP prefix	Compressed for fast LPM
Redis	Key expiry	Expiration timestamp	Variable stride

Longest Prefix Matching Deep Dive

Longest Prefix Matching (LPM) is the quintessential radix tree application. Every IP packet traversing the Internet relies on LPM to determine its next hop.

The Problem:

Given:

A routing table with entries like "192.168.0.0/16 → Gateway A", "192.168.1.0/24 → Gateway B"
A destination IP address like "192.168.1.100"

Find the entry with the longest prefix that matches the destination.

In this example:

192.168.0.0/16 matches (first 16 bits match)
192.168.1.0/24 also matches (first 24 bits match)
192.168.1.0/24 has longer prefix → choose Gateway B

Why Radix Trees Excel at LPM:

Natural prefix representation: Path from root encodes prefix
Incremental matching: Can track "best match so far" during traversal
Variable-length prefixes: Different routes end at different depths
Efficient updates: Adding/removing routes is O(prefix length)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class LPMNode:
    def __init__(self):
        self.children = [None, None]  # Binary radix
        self.prefix_len = None  # If this is a prefix endpoint
        self.next_hop = None  # Gateway for this prefix
 
def lpm_lookup(root, ip_address, ip_bits=32):
    """
    Find longest matching prefix for ip_address.
    Returns next_hop of longest match, or None if no match.
    
    Time: O(ip_bits) = O(32) for IPv4, O(128) for IPv6
    """
    if root is None:
        return None
    
    node = root
    best_match = None  # Track best match seen so far
    
    for bit_pos in range(ip_bits):
        # Check if current node is a prefix endpoint
        if node.prefix_len is not None:
            best_match = node.next_hop
        
        # Get next bit
        bit = (ip_address >> (ip_bits - 1 - bit_pos)) & 1
        child = node.children[bit]
        
        if child is None:
            # No more specific prefix exists
            break
        
        node = child
    
    # Check the final node too
    if node.prefix_len is not None:
        best_match = node.next_hop
    
    return best_match
 
def lpm_insert(root, prefix, prefix_len, next_hop, ip_bits=32):
    """
    Insert a routing entry.
    prefix: The network address (e.g., 192.168.1.0)
    prefix_len: Number of significant bits (e.g., 24 for /24)
    next_hop: Gateway to use for matching destinations
    """
    if root is None:
        root = LPMNode()
    
    node = root
    
    for bit_pos in range(prefix_len):
        bit = (prefix >> (ip_bits - 1 - bit_pos)) & 1
        
        if node.children[bit] is None:
            node.children[bit] = LPMNode()
        
        node = node.children[bit]
    
    # Mark this node as a prefix endpoint
    node.prefix_len = prefix_len
    node.next_hop = next_hop
    
    return root

LPM Performance is Critical

High-speed routers process millions of packets per second. Each packet requires an LPM lookup. Hardware routers use TCAM (Ternary Content-Addressable Memory) for O(1) LPM, but software implementations rely on radix trees. Optimizations like multi-bit strides and path compression are essential for line-rate performance.

Optimizations for High-Performance LPM:

Multi-bit stride: Reduce tree height (4-8 bits typical for software routers)
Leaf pushing: Copy prefix to all descendant leaves; eliminates backtracking during lookup
Prefix expansion: Expand shorter prefixes into longer ones to simplify lookup (space-time trade-off)
Cache optimization: Structure nodes for cache line alignment; prefetch likely paths
Parallel lookup: SIMD instructions to check multiple prefixes simultaneously
Incremental updates: Support adding/removing routes without full tree rebuild

Crit-Bit Trees: A Modern Variant

Crit-bit trees (critical-bit trees) are a modern, simplified variant of Patricia/radix trees designed for clarity and performance. They were popularized by Dan Bernstein (djb) and are used in djbdns and other high-performance software.

Key Characteristics:

Minimal nodes: Exactly n leaves for n keys (like Patricia)
Simple structure: Internal nodes store only the critical bit position
No key storage in internal nodes: Keys stored only at leaves
Deterministic traversal: Follow left for 0, right for 1
No back-pointers: Unlike Patricia, uses null pointers for missing paths

Why "Critical Bit"?

The critical bit is the first bit position where two keys differ. A crit-bit tree is organized such that:

Each internal node stores exactly one critical bit position
All keys in the left subtree have 0 at that position
All keys in the right subtree have 1 at that position
The tree minimizes the number of bit inspections

Example:

Keys: {0b0010, 0b0100, 0b0110, 0b1010}

Critical bits:

0b0010 vs 0b0100: differ at bit 1 (0 vs 1)
0b0100 vs 0b0110: differ at bit 2 (0 vs 1)
All 0xxx vs 0b1010: differ at bit 0 (0 vs 1)

Tree structure:

        (bit 0)
       /       \
   (bit 1)    leaf(0b1010)
   /     \
 leaf   (bit 2)
(0b0010) /     \
     leaf     leaf
   (0b0100)  (0b0110)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class CritBitInternal:
    """Internal node: stores critical bit position."""
    def __init__(self, bit_pos):
        self.bit_pos = bit_pos  # The discriminating bit
        self.children = [None, None]  # [0-child, 1-child]
 
class CritBitLeaf:
    """Leaf node: stores actual key and value."""
    def __init__(self, key, value):
        self.key = key
        self.value = value
 
def critbit_search(root, key, key_bits=32):
    """Search crit-bit tree for key."""
    if root is None:
        return None
    
    node = root
    
    # Navigate to leaf
    while isinstance(node, CritBitInternal):
        bit = get_bit(key, node.bit_pos, key_bits)
        node = node.children[bit]
        if node is None:
            return None
    
    # At leaf: verify match
    if node.key == key:
        return node.value
    return None
 
def critbit_insert(root, key, value, key_bits=32):
    """
    Insert key-value into crit-bit tree.
    More complex than search due to finding critical bit.
    """
    if root is None:
        return CritBitLeaf(key, value)
    
    # First, find where the new key would go
    node = root
    while isinstance(node, CritBitInternal):
        bit = get_bit(key, node.bit_pos, key_bits)
        child = node.children[bit]
        if child is None:
            # Can insert here directly
            node.children[bit] = CritBitLeaf(key, value)
            return root
        node = child
    
    # 'node' is now a leaf
    existing_key = node.key
    
    if existing_key == key:
        # Update existing
        node.value = value
        return root
    
    # Find critical bit position where keys differ
    crit_bit = find_critical_bit(existing_key, key, key_bits)
    
    # Create new internal node
    new_internal = CritBitInternal(crit_bit)
    existing_bit = get_bit(existing_key, crit_bit, key_bits)
    new_bit = get_bit(key, crit_bit, key_bits)
    
    new_internal.children[existing_bit] = node  # Existing leaf
    new_internal.children[new_bit] = CritBitLeaf(key, value)  # New leaf
    
    # Insert new_internal at correct position in tree
    # (This requires walking from root again)
    return insert_internal_node(root, new_internal, key, key_bits)
 
def find_critical_bit(key1, key2, key_bits):
    """Find first bit position where keys differ."""
    diff = key1 ^ key2
    # Find position of highest set bit in diff
    for pos in range(key_bits):
        if (diff >> (key_bits - 1 - pos)) & 1:
            return pos
    return key_bits  # Keys are equal

Crit-Bit Advantages

Crit-bit trees are cache-friendly (small nodes), have simple logic, and support variable-length keys (strings) as easily as integers. They're an excellent choice when you want radix tree benefits without Patricia's complexity or general radix trees' overhead.

Summary: Radix Trees in Perspective

We've journeyed through the world of radix trees—from binary variants to multi-bit optimizations, from Patricia's elegant back-pointers to crit-bit's modern simplicity. These structures are the workhorses of systems software, quietly enabling the infrastructure we depend on daily.

Key Takeaways

•Radix trees are compressed tries for numeric keys: Optimized for bit-level operations on fixed-width integers
•Navigate by examining bit positions: Branch left for 0, right for 1, at each discriminating bit
•Patricia trees use back-pointers: Elegant space optimization but complex implementation
•Multi-bit strides reduce height: Trade node size for fewer memory accesses
•Longest prefix matching is the classic application: Powers IP routing worldwide
•Crit-bit trees offer modern simplicity: Minimal nodes, clear semantics, cache-friendly
•Production systems use radix trees extensively: Linux kernel, routers, DNS, databases

Radix Tree Variants Summary
Variant	Best For	Complexity	Space Efficiency
Binary Radix	General purpose	Low	Medium
Patricia	Maximum compression	High	Best
Multi-bit Radix	Low latency lookup	Medium	Lower
Crit-bit	Variable-length keys	Low	Good

What's Next:

With a comprehensive understanding of radix trees, we now turn to the final question: When does compression actually help? Not all datasets benefit equally from trie compression. The next page provides a rigorous analysis of when compressed tries outperform their standard counterparts, when the overhead isn't worth it, and how to make informed decisions for your specific use case.

Page Complete

You now understand radix trees—their structure, navigation algorithms, major variants (Patricia, multi-bit, crit-bit), and critical applications in operating systems and networking. These are not academic curiosities but essential infrastructure powering the Internet and modern operating systems.