Wormhole: A Fast Ordered Index for In-memory Data Management

1 Introduction

• In-memory database indexes reportedly consume 14–94% of query execution time, while ordered indexes can require 30 or more key comparisons for billion-key indexes.Comparison-based ordered-index lookup costs O(logN) comparisons, making large indexes much slower than hash tables in the examples described.Source: §1 · p. 1
• Tries search in O(L), independent of index size, but long keys—including 20–40-byte keys common in Facebook Memcached workloads —can make searches costly, while space inflation and fragmentation remain concerns.Path compression may help, but its effectiveness depends on key contents and does not guarantee reducing the O(L) cost.Source: §1 · p. 2
• Wormhole combines B+ tree node packing, a trie replacing B+ tree non-leaves, and a hash table that reduces trie lookup to O(logL).It supports lookup, insertion, deletion, and range queries with space comparable to a B+ tree and often below a trie; for bounded key lengths such as 1000 bytes, lookup can be considered O(1).Source: §1 · p. 2
• Up to 8.4×, 4.9×, 4.3×, and 6.6× higher key lookup throughput than B+ tree, skip list, ART, and Masstree, respectively.When range queries are unnecessary, Wormhole reaches 30–92% of a highly optimized Cuckoo hash table’s point-lookup throughput.Source: §1 · p. 2

2.1 Background: Lookup in the B+ Tree

• B+ tree leaf searches take O(1) because leaf size is bounded, but its MetaTree costs O(logN), motivating a replacement whose search cost is independent of key count.In a B+ tree, internal nodes direct searches to sorted leaf nodes, which are linked for range scans.Source: §2.1 · pp. 2–3

2.2 Replacing the MetaTree with a Trie

• A trie replaces the MetaTree with MetaTrie, indexing leaf anchors that satisfy ordering and prefix conditions so the structure remains ordered without indexing every key.Anchor formation aims to minimize anchor length; the leftmost leaf uses the smallest token as its anchor, while other anchors are chosen from the common prefix and next token of adjacent keys, with adjustments to preserve the prefix condition.Source: §2.2 · pp. 3–4

2.3 Performing Search on MetaTrie

• MetaTrie search identifies the target leaf whose anchor bounds the search key, using trie matches or neighboring subtrees when matching fails; worst-case search remains O(L).The target leaf is where an indexed key must reside, and the composite structure saves space versus a conventional trie by keeping multiple keys in each leaf and usually shorter anchors in the trie.Source: §2.3 · pp. 4–5, §2.4 · p. 6

2.4 Accelerating Search with a Hash Table

• Wormhole’s O(logL) lookup combines binary search over anchor-prefix lengths with constant-time sibling and subtree-boundary navigation; it stores multiple keys per leaf, with the same number of leaves as a B+ tree.The hash table indexes all anchor prefixes, so the longest prefix match takes O(log(min(Lanc,Lkey))) lookups; bitmaps locate siblings and pointers identify subtree boundary leaves. The paper says internal-node space determines the relative space cost versus a B+ tree.Source: §2.4 · pp. 5–6

2.5 Concurrency Support

• Per-leaf reader-writer locks protect leaf changes, while QSBR RCU lets readers access MetaTrieHT without locks as writers update a second table and atomically publish it.Version checks make lookups restart if they reach a leaf updated after the MetaTrieHT version they began with; only writers need the MetaTrieHT mutex.Source: §2.5 · p. 7

3.1 Improving Operations in MetaTrieHT

• Incremental hashing reduces average tokens hashed per lookup from L^2 log2 L to L by reusing the hash of a matched prefix when extending it.The implementation uses CRC-32c.Source: §3.1 · p. 8
• Cache-line hash slots and optimistic tag matching reduce prefix comparisons, with a final full-key check detecting false positives and restarting on mismatch.Each 64-byte slot holds eight 16-bit tags and 48-bit pointers; the reported error probability is 0.0153% for 1024-byte keys.Source: §3.1 · p. 8

3.2 Improving Operations in Leaf Node

• Leaf searches compare compact 16-bit hash tags first and read original keys only for matching tags, reducing memory references.Direct speculative positioning usually completes the tag search in 1 to 3 comparisons for a node of 128 keys; sorting appended keys can be deferred until a range search or split.Source: §3.2 · pp. 8–9

3.3 Wormhole with Any Key Tokens

• To support keys containing the minimal token, Wormhole permits a fat leaf node when no split can produce an anchor satisfying the prefix condition.With maximal node size N, the case requires at least N + 1 keys sharing a prefix and differing in trailing zeroes; for N of 64 or 128, the paper says it is unlikely in real datasets.Source: §3.3 · p. 9

4.1 Lookup Performance

• Across eight keysets, using 16 threads unless noted, Wormhole improves lookup throughput by 1.3× to 4.2× over the best results among competing indexes for each keyset.On Az1, it achieves 1.266 MOPS with one thread and 19.5 MOPS with 16 threads; all reported optimizations improve throughput by up to 4.9×.Source: §4.1 · pp. 10–11
• With a 100 Gb/s network link, Wormhole retains its advantage on most datasets, but K10 throughput falls to 37.5% of its local result and is 30% higher than B+ tree.For most datasets, networked peak throughput decreases by 5% to 20%; K10's 1 KB requests make network bandwidth the bottleneck.Source: §4.1 · p. 11, Figure 12 · p. 11

4.2 Comparing with Hash Tables

• For the first seven keysets, Wormhole reaches about 31% to 67% of Cuckoo hash-table throughput, while K10 throughput is close to the hash table.Longer anchors lower Wormhole throughput on Klong versus Kshort, while Cuckoo shows little difference; filling the first L − 4 bytes with “0” creates the longer-anchor keys.Source: §4.2 · p. 12, Figure 13 · p. 12, Figure 14 · p. 12

4.3 Performance of other Operations

• In insertion-only workloads, Wormhole matches skip list throughput on most keysets, while Wormhole and Masstree outperform comparison-based indexes on short keys but slow on longer keys.The insertion comparison uses one thread because several competing indexes lack built-in concurrency control.Source: §4.3 · p. 12, Figure 15 · p. 12
• Wormhole's memory use is comparable to B+ tree and skip list in most cases, while Masstree uses substantially more memory except on K3 and ART uses more on K3 and K4.Wormhole's small trie organizes anchors and stores keys in large leaves; ART's path compression reduces its relative space cost for longer keys.Source: Figure 16 · p. 12, §4.3 · p. 13
• With 5%, 50%, and 95% insertions in 16-thread mixed workloads, Wormhole's advantage over Masstree shrinks as insertions increase but remains substantial.Large leaves mean most insertions do not update MetaTrieHT, and Wormhole's concurrency control lets such updates impose minimal constraint on lookup concurrency.Source: §4.3 · p. 13, Figure 17 · p. 13
• For range scans of up to 100 keys, Wormhole improves throughput by 1.05× to 1.59× over B+ tree, while Masstree is much slower than the other indexes.Sequential scanning diminishes Wormhole's advantage in reaching the first key; ART is omitted because its evaluated source code does not implement range scans.Source: §4.3 · p. 13, Figure 18 · p. 13

5 Related Work

• Comparison-based indexes such as B-trees and skip lists retain O(log N) lookup, while Wormhole reduces the asymptotic cost to O(log L) and adds implementation optimizations.Prior work improves comparison-based indexes through latch-free operations, cache- and TLB-aware layouts, or hardware accelerators, rather than changing the underlying data structure.Source: §5 · p. 13
• ART’s O(L) lookup can be costly for long keys; Masstree reduces trie height with fanout 264 but large B+ tree nodes can slow access, while Wormhole uses O(log L) lookup and a small trie.Wormhole uses large leaf nodes to host keys and a small trie to manage anchors, yielding better space efficiency than a trie.Source: §5 · pp. 13–14
• Caching helps localized workloads but not cold data; Bε-Tree and FloDB buffers add lookup or range-query costs, whereas Wormhole’s leaf identification and hashed-key sorting keep writes consistently low-cost.FloDB’s hash table must be fully flushed to serve a range operation, potentially delaying range queries; Wormhole’s low lookup cost benefits both reads and writes.Source: §5 · p. 14
• Wormhole combines fine-grained locking, RCU, and version numbers for thread safety, with only a slight slowdown versus its thread-unsafe version; other concurrency-control choices remain future work.Related approaches include version-based lock-free readers in MemC3 and Masstree, atomic operations, RCU, transactional memory, and delegation.Source: §5 · p. 14

• Lookup throughput improves by up to 8.4× over skip list, 4.9× over B+ tree, 4.3× over ART, and 6.6× over Masstree.Source: §6 · p. 14
• Wormhole is presented as the first ordered key-value index with O(log L) lookup cost, versus O(log N) or O(L) for other ordered indexes when L is much smaller than N.Source: §6 · p. 14
• Insertion, deletion, and range-query performance is higher than or comparable to that of other indexes.Source: §6 · p. 14
• Wormhole’s space demand is as low as B+ tree’s, and an implementation’s source code is publicly available.Source: §6 · p. 14