Loading learning content...
Database indexes frequently store string keys—URLs, email addresses, file paths, product codes, composite keys. Unlike fixed-size integers, string keys present unique challenges:
The Prefix B-tree (sometimes called a Simple Prefix B-tree or P-tree) addresses these challenges by storing only the minimum distinguishing prefix needed to route searches correctly, rather than complete keys in internal nodes.
This optimization can dramatically reduce index storage, increase effective fanout, and accelerate search operations—particularly for datasets with high prefix redundancy like URLs, file paths, or hierarchical codes.
By the end of this page, you will understand prefix compression in B-trees, how minimum separators are computed, the trade-offs between prefix B-trees and standard B+-trees, and practical applications in database systems. You'll see why this technique is particularly valuable for text-heavy workloads.
To appreciate prefix B-trees, consider a real-world example: indexing URLs on an e-commerce website.
Sample URLs to index:
https://shop.example.com/products/electronics/laptops/dell-xps-13
https://shop.example.com/products/electronics/laptops/macbook-pro
https://shop.example.com/products/electronics/phones/iphone-15
https://shop.example.com/products/electronics/phones/samsung-s24
https://shop.example.com/products/clothing/shirts/blue-oxford
https://shop.example.com/products/clothing/shirts/white-dress
These URLs share a 42-character common prefix: https://shop.example.com/products/. In a standard B+-tree, this prefix is stored repeatedly in every index entry—both in leaf nodes and internal nodes.
| Metric | Without Prefix Compression | With Prefix Compression |
|---|---|---|
| Average key length | 70 bytes | 28 bytes (unique suffix) |
| Keys per 8KB node | ~100 keys | ~250 keys |
| Effective fanout | ~100 | ~250 |
| Index size for 1M URLs | ~70 MB | ~28 MB |
| Tree height (order 100) | 4 levels | 3 levels |
The inefficiency compounds:
In internal nodes, the full key isn't even needed for routing decisions. Consider searching for a URL starting with 'electronics/laptops'. The search only needs enough information to choose the correct child pointer—the common 'https://shop.example.com/products/' prefix is entirely redundant for this decision.
This observation leads to the core insight of prefix B-trees: internal nodes should store minimum distinguishing prefixes, not complete keys.
Variable-length strings create additional complexity: node management becomes more complex, split points are harder to calculate, and key comparisons are slower. Prefix B-trees address the storage issue but add their own complexity. Understanding both is essential for making informed design decisions.
A Prefix B-tree extends the standard B+-tree with a key insight: internal (non-leaf) nodes only need to store separators—strings that distinguish keys in the left subtree from keys in the right subtree. These separators can be much shorter than actual keys.
Formal Definition:
Given two adjacent keys K₁ and K₂ where K₁ < K₂, a valid separator S satisfies:
The separator must be:
Example: Computing a Minimum Separator
Given adjacent keys:
The minimum separator must:
Minimum separator: "electronics/m" (or any string from "electronics/laptops/dell-xps-13" up to but not including a string that would sort before "electronics/p")
Actually, more precisely: "electronics/laptops/dell-xps-13" can be separated from "electronics/phones" by "electronics/o" or simply "electronics/m" (since 'm' is between 'l' and 'p').
Even simpler: "electronics/l{...}" vs "electronics/p{...}" can be separated by "electronics/o" — just 13 characters instead of 33!
The ideal separator is the shortest string that falls between two adjacent keys. It doesn't need to exist as an actual key in the database—it's purely a routing construct. This freedom allows very aggressive compression in internal nodes.
Computing the minimum separator between two keys requires careful algorithm design. The goal is to find the shortest string S where K₁ ≤ S < K₂.
Algorithm: Minimum Separator
123456789101112131415161718192021222324252627282930313233343536373839404142
function compute_minimum_separator(left_key, right_key): """ Compute the shortest separator S where left_key <= S < right_key. This is promoted to the parent when splitting. """ # Find the common prefix length common_len = 0 min_len = min(len(left_key), len(right_key)) while common_len < min_len: if left_key[common_len] != right_key[common_len]: break common_len += 1 # Case 1: left_key is a prefix of right_key # Example: "abc" and "abcdef" -> separator is "abc" (left_key itself) if common_len == len(left_key): return left_key # Case 2: They differ at position common_len # We can use left_key truncated at common_len + 1 # But we try to find an even shorter separator left_char = left_key[common_len] right_char = right_key[common_len] # Separator character can be anything in (left_char, right_char) # We typically use left_key[0:common_len] + chr(ord(left_char) + 1) # if that's still < right_key separator = left_key[0:common_len] # Add minimal distinguishing suffix if ord(left_char) + 1 < ord(right_char): # There's room between the characters # Use left_key prefix for safety (ensures >= left_key) separator = left_key[0:common_len + 1] else: # Characters are adjacent - need to be more careful separator = left_key[0:common_len + 1] return separatorWorked Examples:
| Left Key | Right Key | Common Prefix | Minimum Separator |
|---|---|---|---|
| "apple" | "banana" | (none) | "b" or "apple" |
| "apple" | "application" | "appl" | "apple" (left is prefix of right) |
| "cat" | "dog" | (none) | "d" or "cat" |
| "prefix_aaa" | "prefix_bbb" | "prefix_" | "prefix_b" or "prefix_aaa" |
| "abc123" | "abc789" | "abc" | "abc2" or "abc123" |
Key Observations:
There are often many valid separators between two keys. The algorithm doesn't require the mathematically "optimal" shortest string—any valid separator that improves over storing the full key provides benefits. Implementations may use simple truncation heuristics rather than complex optimization.
Search in a prefix B-tree works almost identically to a standard B+-tree. The only difference is that internal node comparisons use separators instead of full keys.
Search Algorithm:
123456789101112131415161718192021222324252627282930313233
function search(root, search_key): node = root while node is not a leaf: # Binary search for correct child pointer # Compare search_key against separators in internal node child_index = binary_search_child(node.separators, search_key) node = node.children[child_index] # At leaf node - search for exact key match # Leaves store FULL keys, not separators result = binary_search(node.keys, search_key) if result.found: return node.values[result.index] else: return NOT_FOUND function binary_search_child(separators, search_key): """ Find index of child pointer to follow. Returns i where: separators[i-1] <= search_key < separators[i] """ left, right = 0, len(separators) while left < right: mid = (left + right) // 2 if separators[mid] <= search_key: left = mid + 1 else: right = mid return left # Index of child to followImportant Distinction:
This distinction is crucial: exact-match searches always reach a leaf node and compare against complete keys. The separators only guide the search path.
Prefix B-trees can actually be faster for search operations, not just more space-efficient. Shorter separators mean: (1) more separators fit in cache, (2) fewer characters to compare at each internal node, and (3) potentially smaller tree height. The combination provides measurable speedups for string-heavy indexes.
Visual Example:
["d", "m"] <- Internal: 2 separators
/ | \
["b"] ["f","j"] ["p"] <- Internal: short separators
/ \ / | \ / \
[L1] [L2] [L3][L4][L5] [L6][L7] <- Leaves: full keys
Leaf L1: ["apple", "banana"]
Leaf L2: ["carrot", "cherry"]
Leaf L3: ["date", "elderberry"]
Leaf L4: ["fig", "grape"]
Leaf L5: ["kiwi", "lemon"]
Leaf L6: ["mango", "nectarine", "orange"]
Leaf L7: ["papaya", "quince"]
Search for "grape":
1. Root: "grape" >= "d" and < "m" → middle child
2. Internal: "grape" >= "f" and < "j" → second child (L4)
3. Leaf L4: binary search finds "grape" ✓
Insertion in prefix B-trees follows the standard B+-tree pattern with one modification: when splitting nodes, we compute minimum separators to promote to the parent.
Insertion Algorithm:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
function insert(root, key, value): leaf = find_leaf(root, key) # Insert into leaf (leaves store full keys) insert_in_leaf(leaf, key, value) if leaf.is_overflow(): split_leaf(leaf) function split_leaf(leaf): # Standard B+-tree split for leaf mid = len(leaf.keys) // 2 # Create new leaf with upper half new_leaf = create_leaf_node() new_leaf.keys = leaf.keys[mid:] new_leaf.values = leaf.values[mid:] leaf.keys = leaf.keys[:mid] leaf.values = leaf.values[:mid] # Link leaves new_leaf.next = leaf.next leaf.next = new_leaf # KEY DIFFERENCE: Compute minimum separator # left_key = maximum key in left leaf # right_key = minimum key in right (new) leaf separator = compute_minimum_separator( leaf.keys[-1], # Last key in left leaf new_leaf.keys[0] # First key in right leaf ) # Promote separator to parent promote_to_parent(leaf.parent, separator, new_leaf) function promote_to_parent(parent, separator, new_child): insert_separator_and_child(parent, separator, new_child) if parent.is_overflow(): split_internal(parent) function split_internal(node): # Split internal node mid = len(node.separators) // 2 # The middle separator goes up promoted_sep = node.separators[mid] # Create new internal node new_node = create_internal_node() new_node.separators = node.separators[mid+1:] new_node.children = node.children[mid+1:] node.separators = node.separators[:mid] node.children = node.children[:mid+1] # Promote middle separator up (already minimal from original computation) promote_to_parent(node.parent, promoted_sep, new_node)Split Example:
BEFORE: Leaf overflow
┌────────────────────────────────────────────────────┐
│ "products/electronics/camera" │ "products/electronics/laptop" │
│ "products/electronics/phone" │ "products/electronics/tablet" │
│ "products/electronics/tv" │ (OVERFLOW - insert "watch") │
└────────────────────────────────────────────────────┘
AFTER: Split with minimum separator
["products/electronics/t"]
/ \
┌──────────────────────────┐ ┌──────────────────────────┐
│ camera, laptop, phone │ │ tablet, tv, watch │
└──────────────────────────┘ └──────────────────────────┘
Separator: "products/electronics/t" (only 22 chars)
Not: "products/electronics/tablet" (27 chars)
The separator "products/electronics/t" is sufficient because:
The length of computed separators varies based on key distribution. Adjacent keys with long common prefixes yield short separators, while dissimilar keys may have long separators. This variability affects node capacity in ways that standard B+-trees don't experience.
Another approach to prefix optimization is front compression (also called prefix truncation or key normalization). Instead of computing minimum separators, front compression stores the minimum unique suffix of each key within a node.
How Front Compression Works:
Within a single node, keys are sorted. Each key shares some prefix with its predecessor. Front compression stores:
Example:
123456789101112131415161718192021
BEFORE: Full key storage┌────────────────────────────────────────────────────────┐│ Key 0: "products/electronics/camera" (27 bytes) ││ Key 1: "products/electronics/laptop" (27 bytes) ││ Key 2: "products/electronics/phone" (26 bytes) ││ Key 3: "products/electronics/tablet" (27 bytes) ││ Key 4: "products/home/appliances" (24 bytes) │└────────────────────────────────────────────────────────┘Total: 131 bytes AFTER: Front compression┌────────────────────────────────────────────────────────┐│ Key 0: "products/electronics/camera" (27 bytes) ││ Key 1: (21, "laptop") → prefix 21 chars + "laptop" ││ Key 2: (21, "phone") → prefix 21 chars + "phone" ││ Key 3: (21, "tablet") → prefix 21 chars + "tablet" ││ Key 4: (9, "home/appliances") → prefix 9 + suffix │└────────────────────────────────────────────────────────┘Total: 27 + 8 + 7 + 8 + 17 + overhead ≈ 75 bytes Compression ratio: ~43% space savedComparison: Minimum Separators vs. Front Compression
| Aspect | Minimum Separators | Front Compression |
|---|---|---|
| Applied to | Internal nodes only | All nodes (leaf + internal) |
| Key reconstruction | Separators are self-contained | Requires predecessor for full key |
| Random access | O(1) for any separator | O(position) - must scan from start |
| Compression ratio | Very high for internal nodes | High for all nodes |
| Implementation | Per-key separator computation | Per-node prefix tracking |
| Maintenance | Recompute on splits | Recompute on any node change |
Modern databases often combine techniques: minimum separators in internal nodes (for maximum fanout) plus front compression in leaf nodes (for maximum data density). This hybrid approach captures benefits of both without their individual weaknesses.
A related optimization is suffix truncation—removing trailing characters from separators that aren't needed for correct routing. This is essentially what minimum separator computation does, but viewed from a different angle.
Key Insight:
A separator in an internal node only needs to:
It does NOT need to:
12345678910111213141516171819202122
EXAMPLE: URL-based keys with long common suffixes Keys in left subtree: "example.com/api/v1/users/profile" "example.com/api/v1/users/settings" Keys in right subtree: "example.com/api/v2/users/profile" "example.com/api/v2/users/settings" FULL SEPARATOR (traditional B+-tree): "example.com/api/v2/users/profile" (35 characters) MINIMUM SEPARATOR (prefix B-tree): "example.com/api/v2" (18 characters) SUFFIX TRUNCATED (aggressive): "example.com/api/v1{" (19 characters) Using a character just after 'v1' that's before 'v2' Any of these correctly distinguishes the subtrees, but shorter is better.PostgreSQL's Approach:
PostgreSQL implements suffix truncation in its B-tree indexes starting from version 12. When splitting a leaf page, the promoted separator is truncated to the minimum distinguishing prefix plus one character.
The implementation considers:
Practical Impact:
In PostgreSQL benchmarks, suffix truncation reduced index size by 15-40% for text-heavy tables, with corresponding improvements in buffer cache hit rates and query performance.
PostgreSQL combines suffix truncation with deduplication (multiple equal keys stored once with a list of row identifiers). Together, these optimizations can reduce index size dramatically—by 50% or more for certain workloads. The techniques are complementary: truncation reduces separator size, deduplication reduces leaf entry count.
Implementing prefix B-trees introduces complexities beyond standard B+-trees. Understanding these is crucial for production-quality implementations.
1. Variable-Length Key Management:
12345678910111213141516171819202122
# Variable-length keys require careful node layoutstruct LeafNode: header: node_type: byte # Leaf indicator key_count: uint16 # Number of keys free_space_offset: uint16 # Where free space begins next_leaf: pointer # Sibling pointer # Fixed-size slot directory (grows forward) slots[MAX_SLOTS]: key_offset: uint16 # Where key data starts key_length: uint16 # Key length in bytes value_pointer: pointer # Row pointer # Variable-length key data (grows backward from end) key_data: bytes[...] # Insertion must:# 1. Check if key + slot fits in remaining space# 2. Add slot entry to directory# 3. Write key data at allocation offset# 4. Update free space offset2. Split Point Calculation:
With variable-length keys, finding the optimal split point is non-trivial:
3. Separator Computation Cost:
Computing minimum separators adds CPU overhead:
4. Compression Boundaries:
Deciding compression scope:
Prefix compression provides minimal benefit for random keys (like UUIDs) with no common prefixes. In such cases, the compression overhead may exceed benefits. Modern databases detect key patterns and adaptively enable or disable prefix compression based on expected savings.
Prefix B-trees shine in specific scenarios but aren't universally superior. Understanding the ideal use cases enables informed design decisions.
Most production databases implement prefix compression as an optional optimization, automatically enabled when analysis suggests it will provide benefit. PostgreSQL, Oracle, and SQL Server all include variants of prefix/suffix truncation. MongoDB's WiredTiger engine uses sophisticated prefix compression for string keys.
Prefix B-trees represent an important optimization for string-based indexes, addressing the redundancy inherent in hierarchical or prefix-shared key spaces.
What's Next:
We've now explored two B+-tree variants focusing on space optimization: B*-trees (higher minimum occupancy) and prefix B-trees (compressed separators). Next, we'll examine bulk loading—techniques for efficiently building B+-trees from scratch when you have large amounts of data to index, avoiding the overhead of millions of individual insertions.
You now understand prefix B-trees, separator computation, front compression, and suffix truncation. These techniques are fundamental to how production databases efficiently handle string-based indexes, and the principles apply broadly to any scenario with redundant key prefixes.