Source of truth for the theory: the complete treatment of disk-based tries — B-tries, the Adaptive Radix Tree (ART), pointer swizzling, buffer management, and the hybrid Persistent Adaptive Radix Trie (PART) design — lives in the libdictenstein crate that owns the structure:
libdictenstein/docs/theory/disk-tries/. This page covers only how liblevenshtein uses it. The earlier in-repo deep-dive chapters duplicated that treatment and are preserved underdocs/archive/theory/disk-tries/.
When a dictionary exceeds available RAM, liblevenshtein reaches for a disk-persisted backend.
The PersistentARTrie (libdictenstein) is a hybrid of the Adaptive Radix Tree (ART) of
Leis et al. [2] — whose adaptive Node4/16/48/256 layout keeps exact lookup at
$\mathcal{O}(m)$ for a term of length $m$ — with B-trie-style bucket storage on disk
(Askitis & Zobel [1]), memory-mapped and reached through a lock-free CAS overlay.
"Persistent" here means non-volatile (durable on SSD/HDD), not immutable: the
Persistent* family is fully dynamic, supporting atomic concurrent insert/remove.
liblevenshtein's transducer walks any Dictionary in lock-step with a simulated Levenshtein
automaton. When the backend is a PersistentARTrie (or the disk-persisted PersistentScdawg,
PersistentSuffixAutomaton, PersistentSuffixTree, PersistentVocabARTrie), that lock-step walk
runs directly over the memory-mapped, lock-free structure — so a dictionary far larger than RAM
is fuzzy-searched with the same $\mathcal{O}(\lvert W\rvert)$ per-query setup and $\mathcal{O}(k)$
per-transition cost as an in-memory backend, the difference being page-cache-bounded disk I/O rather
than resident memory. The ART node handles are the disk analogue of the in-memory TrieRef snapshot
that makes traversal $\mathcal{O}(1)$ per byte from the focus (see
docs/design/pathmap-trieref-rework.md).
| Operation (PersistentARTrie) | Time | Disk I/Os (typical) |
|---|---|---|
| Exact lookup | $\mathcal{O}(m)$ | 2–4 |
| Insert | $\mathcal{O}(m + \log B)$ amortized | 2–4 + 1 write |
| Prefix search | $\mathcal{O}(m + r)$ | depends on $r$ |
Levenshtein ($k = 1, 2$) | $\mathcal{O}(n \cdot m \cdot k^{2})$ before pruning | varies with pruning |
where $m$ = term length, $B$ = bucket size (~100–500), $r$ = result count, $n$ = dictionary size.
libdictenstein/docs/theory/disk-tries/.user-guide/backends.md.docs/archive/theory/disk-tries/.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 |