This documentation series provides a comprehensive, pedagogical introduction to disk-based trie data structures, culminating in the design of the Persistent Adaptive Radix Trie (PART) - a hybrid structure combining the Adaptive Radix Tree (ART) with B-trie-style bucket storage.
When dictionaries exceed available RAM, we need data structures that efficiently manage data on secondary storage (SSD/HDD). Traditional in-memory tries waste space and incur excessive I/O when naively persisted to disk. This series explores specialized techniques for building tries that minimize disk I/O while maintaining fast lookup and update operations.
The documents are numbered to indicate the recommended reading order:
| Document | Topic | Prerequisites |
|---|---|---|
| 01-foundations | Trie basics and disk I/O fundamentals | None |
| 02-b-trie | B-trie architecture (Askitis & Zobel 2009) | 01 |
| 03-adaptive-radix-tree | Adaptive Radix Tree theory (Leis et al. 2013) | 01 |
| 04-persistent-art | Disk persistence with pointer swizzling | 01, 03 |
| 05-buffer-management | Page cache, WAL, and crash recovery | 01 |
| 06-persistent-artrie-design | Our hybrid PART design | All previous |
| 07-benchmark-results | Measured throughput, recovery, and checkpoint costs | 06 |
Depending on your background and goals, consider these reading paths:
Read all documents in order: 01 → 02 → 03 → 04 → 05 → 06
Start with 01 (trie foundations), then 02 (B-trie), then 06 (design summary)
Focus on 04 (persistence techniques), 05 (buffer management), and 06 (final design)
Jump directly to 06 for a summary of the final design with references back to detailed explanations
| Structure | Description | Best For |
|---|---|---|
| B-trie | Disk-based burst trie with buckets | Balanced read/write, space efficiency |
| ART | Adaptive Radix Tree with Node4/16/48/256 | Low-latency lookups, SIMD acceleration |
| PART | Persistent ART + B-trie buckets | Our hybrid combining both strengths |
| Technique | Purpose |
|---|---|
| Pointer Swizzling | Dual memory/disk addressing in single 64-bit pointer |
| Buffer Manager | Page cache with LRU eviction and pinning |
| Write-Ahead Log (WAL) | Crash recovery through operation logging |
| Path Compression | Reduce tree height by collapsing single-child chains |
For the Persistent ARTrie design:
| Operation | Time Complexity | Disk I/Os |
|---|---|---|
| Exact lookup | $O(m)$ | 2-4 (typical) |
| Insert | $O(m + \log B)$ amortized | 2-4 + 1 write |
| Prefix search | $O(m + k)$ | Depends on $k$ |
Levenshtein ($d = 1, 2$) | $O(n\cdot m\cdot d^2)$ | Varies with pruning |
Where: $n$ = query (input) length, $m$ = term length, $B$ = bucket size (~100–500), $k$ = result count
Primary sources underlying this documentation:
B-tries for disk-based string management Askitis, N. & Zobel, J. (2009). The VLDB Journal, 18(1), 157-179. DOI: 10.1007/s00778-008-0094-1
The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases Leis, V., Kemper, A., & Neumann, T. (2013). ICDE. DOI: 10.1109/ICDE.2013.6544812 · PDF
Persistent Storage of Adaptive Radix Trees in DuckDB DuckDB Team (2022). Blog Post
SMART: A High-Performance Adaptive Radix Tree for Disaggregated Memory Luo, X. et al. (2023). OSDI. PDF
HOT: A Height Optimized Trie Index for Main-Memory Database Systems Binna, R. et al. (2018). SIGMOD. DOI: 10.1145/3183713.3196896 · PDF
Can you improve this documentation?Edit on GitHub
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |