This document introduces the foundational concepts needed to understand disk-based trie data structures: the trie data structure itself, the external memory model for disk I/O, and the challenges of adapting in-memory data structures for secondary storage.
A trie (from "retrieval," pronounced either "try" or "tree"; introduced by Fredkin 1960, DOI: 10.1145/367390.367400) is a tree-based data structure for storing strings where each edge is labeled with a character (or more generally, a symbol from an alphabet). The path from the root to any node spells out a prefix of the stored strings.
root
/ | \
a b c
/|\ | |
p n t e a
/ | \ \ \
p d e a r
/ | | \
l y r* t*
/ |
e* s*
Stores: {apple, andy, ate, bear, bears, cart}
* marks word endings (final states)
A trie T over alphabet $\Sigma$ is a rooted tree where:
\sigma \in \Sigma$Time Complexity:
O(m)$ where $m$ is the length of the query stringO(m)$O(m)$O(m + k)$ where $k$ is the number of matchesSpace Complexity:
O(n \times m \times \lvert \Sigma \rvert)$ where $n$ is the number of strings and $\lvert \Sigma \rvert$ is the alphabet size| Structure | Lookup | Insert | Space | Notes |
|---|---|---|---|---|
| Sorted Array | $O(m \log n)$ | $O(n)$ | $O(N)$ | Binary search, $N$ = total chars |
| Hash Table | $O(m)$ expected | $O(m)$ | $O(N)$ | No prefix queries, hash collisions |
| Trie | $O(m)$ | $O(m)$ | Variable | Prefix queries, deterministic |
| BST of strings | $O(m \log n)$ | $O(m \log n)$ | $O(N)$ | Balanced variants |
The key advantage of tries is that lookup time depends only on query length, not the number of stored strings.
Several trie variants optimize for specific use cases:
The basic trie as described above. Each node has up to $\lvert \Sigma \rvert$ children, stored in some collection (array, hash map, linked list).
Alphabet array representation:
struct TrieNode {
children: [Option<Box<TrieNode>>; 256], // For ASCII
is_final: bool,
}
This wastes space when nodes have few children.
A Patricia trie (Practical Algorithm To Retrieve Information Coded In Alphanumeric; Morrison 1968, DOI: 10.1145/321479.321481) compresses chains of single-child nodes by storing edge labels as strings rather than single characters.
Standard Trie: Patricia Trie:
root root
| / \
t "test" "toast"
| |
e "er"
/ \ / \
s o "s" "ing"
| |
t a
| |
e s
| |
r t
Benefits:
Trade-off:
A burst trie (Heinz et al. 2002) adapts its structure based on access patterns. It starts with simple bucket containers and "bursts" them into trie structure when they become too large or too frequently accessed.
Initial (bucket): After burst:
[cat, car, cup] c
/ \
a u
/ \ \
t r p
A DAWG — also called the directed acyclic word graph or minimal acyclic finite-state automaton (Blumer et al. 1985, DOI: 10.1016/0304-3975(85)90157-4; minimized incrementally by Daciuk et al. 2000, DOI: 10.1162/089120100561601) — shares suffixes in addition to prefixes, creating a DAG rather than a tree. This minimizes space but complicates some operations.
Succinct data structures use space close to the information-theoretic minimum. Examples include:
These are typically read-only after construction.
When data exceeds RAM, we must consider the cost of disk I/O. The external memory model (also called the I/O model or disk access model) quantifies this.
| Parameter | Description | Typical Value |
|---|---|---|
| M | Main memory size (bytes) | 16-256 GB |
| B | Block size (bytes) | 4 KB - 256 KB |
| N | Problem size (data items or bytes) | > M |
In this model, we count the number of I/O operations (block transfers between disk and memory), not CPU operations. Each I/O transfers one block of B bytes.
Key insight: reading 1 byte costs the same as reading B bytes, because disk access has high latency but good throughput. We must read/write in blocks.
Hard Disk Drives (HDD):
Solid State Drives (SSD):
\times$ faster than randomB-trees exemplify disk-optimized design:
[M]
/ \
[D, H] [T, X]
/ | \ / | \
[A-C][E-G][I-L][N-S][U-W][Y-Z]
O(B)$ children, reducing tree heightO(\log_{B} N)$, so only $O(\log_{B} N)$ I/Os per operationFor N = 1 billion items and B = 4 KB pages holding 400 keys:
\log_{400}(10^9) \approx 4$ levels\log_2(10^9) \approx 30$ levelsNaively persisting a standard trie to disk performs poorly:
Consider looking up "international" (13 characters) in a naive disk trie:
Compare to a B-tree with fanout 256:
\approx$ 3–4 for most dictionaries| Approach | Description | Examples |
|---|---|---|
| Burst/Bucket | Store leaves in buckets, burst when full | B-trie, HAT-trie |
| Adaptive Nodes | Use different node types based on fanout | ART, HOT |
| Block Packing | Pack multiple nodes per disk block | String B-tree |
| Serialized DAG | Serialize DAWG with offset-based pointers | FST on disk |
When evaluating disk-based tries, consider these metrics:
When comparing disk tries, measure:
This foundation establishes the core concepts:
O(m)$ lookup independent of dictionary sizeO(\log_{B} N)$ I/Os; our goal is similar for triesThe following documents explore specific solutions:
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 |