This document presents our hybrid design for the Persistent Adaptive Radix Trie (PART), combining Adaptive Radix Tree (ART) nodes with B-trie-style buckets for leaf storage. This design is optimized for Levenshtein automata traversal in the liblevenshtein-rust library.
| Requirement | Priority | Notes |
|---|---|---|
| Levenshtein automata support | Critical | Must implement DictionaryNode for traversal |
| Large dictionary support | Critical | 10GB-1TB datasets exceeding RAM |
| Balanced read/write | High | Not write-only or read-only |
| Crash recovery | High | Durability without data loss |
| Low latency lookups | High | 2-4 disk I/Os for exact match |
We combine the best features of both structures:
From ART:
From B-trie:
| Alternative | Reason for Rejection |
|---|---|
| Pure B-trie | ART's adaptive nodes better match automata traversal |
| Pure persistent ART | Single-string leaves waste I/O for dense regions |
| LSM-trie | Write-optimized, poor for balanced workloads |
| FST/LOUDS | Read-only, no updates |
| HAT-trie (in-memory) | Not designed for disk |
┌─────────────────────────────────────────────────────────────────────┐
│ API Layer │
│ ┌─────────────┐ ┌──────────────┐ ┌────────────────────────────┐ │
│ │ Dictionary │ │ MappedDict │ │ MutableMappedDictionary │ │
│ │ trait │ │ trait │ │ trait (insert/remove) │ │
│ └─────────────┘ └──────────────┘ └────────────────────────────┘ │
└───────────────────────────────┬─────────────────────────────────────┘
│
┌───────────────────────────────┴─────────────────────────────────────┐
│ Index Layer (ART) │
│ ┌──────────────────────────────────────────────────────────────┐ │
│ │ Adaptive Nodes with Swizzled Pointers │ │
│ │ ┌────────┐ ┌────────┐ ┌────────┐ ┌──────────┐ │ │
│ │ │ Node4 │ │ Node16 │ │ Node48 │ │ Node256 │ │ │
│ │ │(linear)│ │ (SIMD) │ │(index) │ │ (direct) │ │ │
│ │ └────────┘ └────────┘ └────────┘ └──────────┘ │ │
│ │ │ │
│ │ Path Compression: Collapse single-child chains │ │
│ └──────────────────────────────────────────────────────────────┘ │
└───────────────────────────────┬─────────────────────────────────────┘
│
┌───────────────────────────────┴─────────────────────────────────────┐
│ Leaf Layer (B-trie Buckets) │
│ ┌──────────────────────────────────────────────────────────────┐ │
│ │ String Buckets (8KB pages) │ │
│ │ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │ │
│ │ │ Bucket A │ │ Bucket B │ │ Bucket C │ │ │
│ │ │ ~100 strs │ │ ~100 strs │ │ ~100 strs │ │ │
│ │ │ sorted │ │ sorted │ │ sorted │ │ │
│ │ └─────────────┘ └─────────────┘ └─────────────┘ │ │
│ └──────────────────────────────────────────────────────────────┘ │
└───────────────────────────────┬─────────────────────────────────────┘
│
┌───────────────────────────────┴─────────────────────────────────────┐
│ Storage Layer │
│ ┌─────────────────┐ ┌─────────────────┐ ┌──────────────────┐ │
│ │ Buffer Manager │ │ WAL │ │ Disk Manager │ │
│ │ (256KB blocks) │ │ (redo logging) │ │ (file I/O) │ │
│ └─────────────────┘ └─────────────────┘ └──────────────────┘ │
└─────────────────────────────────────────────────────────────────────┘
The transition between ART nodes and buckets follows these rules:
Dense subtree?
│
┌─────────────┴─────────────┐
↓ Yes ↓ No
Use ART nodes Check fanout
(many branches) │
┌────────────┴────────────┐
↓ Few children ↓ Many children
Use bucket Use ART nodes
(store strings) (continue trie)
Heuristic: Use buckets when:
┌────────────────────────────────────────────────────────────────────┐
│ Bit 63 (MSB): Swizzle Flag │
│ 1 = Swizzled (memory pointer) │
│ 0 = Unswizzled (disk reference) │
├────────────────────────────────────────────────────────────────────┤
│ When swizzled (memory pointer): │
│ Bits 62-0: Memory address (mask off MSB) │
│ Valid because user-space addresses have bit 63 = 0 │
├────────────────────────────────────────────────────────────────────┤
│ When unswizzled (disk reference): │
│ Bits 62-40: Block ID (23 bits = 8M blocks) │
│ Bits 39-18: Offset in block (22 bits = 4MB offset) │
│ Bits 17-0: Node type + flags (18 bits) │
│ │
│ With 256KB blocks: 8M × 256KB = 2TB addressable │
└────────────────────────────────────────────────────────────────────┘
use std::sync::atomic::{AtomicU64, Ordering};
const SWIZZLE_FLAG: u64 = 1 << 63;
const BLOCK_ID_SHIFT: u64 = 40;
const OFFSET_SHIFT: u64 = 18;
const BLOCK_ID_MASK: u64 = 0x7FFFFF; // 23 bits
const OFFSET_MASK: u64 = 0x3FFFFF; // 22 bits
const FLAGS_MASK: u64 = 0x3FFFF; // 18 bits
#[derive(Debug)]
pub struct SwizzledPtr(AtomicU64);
impl SwizzledPtr {
/// Create unswizzled pointer to disk location
pub fn disk(block_id: u32, offset: u32, node_type: NodeType) -> Self {
debug_assert!(block_id <= BLOCK_ID_MASK as u32);
debug_assert!(offset <= OFFSET_MASK as u32);
let encoded = ((block_id as u64 & BLOCK_ID_MASK) << BLOCK_ID_SHIFT)
| ((offset as u64 & OFFSET_MASK) << OFFSET_SHIFT)
| (node_type as u64);
Self(AtomicU64::new(encoded))
}
/// Create swizzled pointer to memory
pub fn memory(ptr: *const Node) -> Self {
let addr = ptr as u64;
debug_assert!(addr & SWIZZLE_FLAG == 0);
Self(AtomicU64::new(addr | SWIZZLE_FLAG))
}
/// Check if pointer is in memory
#[inline]
pub fn is_swizzled(&self) -> bool {
self.0.load(Ordering::Acquire) & SWIZZLE_FLAG != 0
}
/// Get memory pointer (fast path)
#[inline]
pub unsafe fn as_ptr_unchecked(&self) -> *const Node {
let val = self.0.load(Ordering::Acquire);
(val & !SWIZZLE_FLAG) as *const Node
}
/// Decode disk location (slow path)
pub fn disk_location(&self) -> Option<(u32, u32, NodeType)> {
let val = self.0.load(Ordering::Acquire);
if val & SWIZZLE_FLAG != 0 {
return None;
}
let block_id = ((val >> BLOCK_ID_SHIFT) & BLOCK_ID_MASK) as u32;
let offset = ((val >> OFFSET_SHIFT) & OFFSET_MASK) as u32;
let node_type = NodeType::from_u8((val & FLAGS_MASK) as u8)?;
Some((block_id, offset, node_type))
}
/// Atomically swizzle disk reference to memory pointer
pub fn swizzle(&self, ptr: *const Node) -> Result<(), SwizzleError> {
let old = self.0.load(Ordering::Acquire);
if old & SWIZZLE_FLAG != 0 {
return Err(SwizzleError::AlreadySwizzled);
}
let new = (ptr as u64) | SWIZZLE_FLAG;
self.0.compare_exchange(old, new, Ordering::AcqRel, Ordering::Acquire)
.map(|_| ())
.map_err(|_| SwizzleError::RaceCondition)
}
}
All node types share a header for polymorphic handling:
#[repr(C)]
pub struct NodeHeader {
node_type: u8, // Node4=4, Node16=16, Node48=48, Node256=0
num_children: u8, // Current child count
partial_len: u8, // Compressed path length
_padding: u8, // Alignment
partial: [u8; 12], // Compressed path bytes (up to 12)
}
#[repr(C, align(64))] // Cache line aligned
pub struct Node4 {
header: NodeHeader, // 16 bytes
keys: [u8; 4], // 4 bytes (unsorted)
_key_padding: [u8; 12], // Alignment
children: [SwizzledPtr; 4], // 32 bytes
}
// Total: 64 bytes (1 cache line)
Lookup: Linear scan of 4 keys.
#[repr(C, align(64))]
pub struct Node16 {
header: NodeHeader, // 16 bytes
keys: [u8; 16], // 16 bytes (sorted, 16-byte aligned for SIMD)
children: [SwizzledPtr; 16], // 128 bytes
}
// Total: 160 bytes (2.5 cache lines)
Lookup: SIMD parallel comparison (SSE4.1).
#[cfg(target_arch = "x86_64")]
pub fn find_child_simd(&self, key: u8) -> Option<usize> {
use std::arch::x86_64::*;
unsafe {
let search = _mm_set1_epi8(key as i8);
let keys = _mm_load_si128(self.keys.as_ptr() as *const __m128i);
let cmp = _mm_cmpeq_epi8(search, keys);
let mask = _mm_movemask_epi8(cmp) & ((1 << self.header.num_children) - 1);
if mask != 0 {
Some(mask.trailing_zeros() as usize)
} else {
None
}
}
}
#[repr(C)]
pub struct Node48 {
header: NodeHeader, // 16 bytes
child_index: [u8; 256], // 256 bytes (key → slot, 255 = empty)
children: [SwizzledPtr; 48], // 384 bytes
}
// Total: 656 bytes
Lookup: Two array accesses: index[key] → children[slot].
#[repr(C)]
pub struct Node256 {
header: NodeHeader, // 16 bytes
children: [SwizzledPtr; 256], // 2048 bytes
}
// Total: 2064 bytes
Lookup: Direct array access: children[key].
| Type | Capacity | Lookup | Size | Best For |
|---|---|---|---|---|
| Node4 | 1-4 | 𝒪(4) linear | 64 B | Sparse leaf-adjacent |
| Node16 | 5-16 | 𝒪(1) SIMD | 160 B | Common inner nodes |
| Node48 | 17-48 | 𝒪(1) indexed | 656 B | Moderately dense |
| Node256 | 49-256 | 𝒪(1) direct | 2064 B | Dense (rare) |
Buckets store multiple strings with a shared prefix (determined by their position in the trie):
#[repr(C)]
pub struct LeafBucket {
header: BucketHeader, // 32 bytes
directory: [StringEntry; 256], // 2048 bytes (sorted)
data: [u8; 5952], // Remaining space in 8KB
}
#[repr(C)]
pub struct BucketHeader {
magic: u32, // Validation
num_entries: u16, // Current string count
free_offset: u16, // Next free byte in data
min_key: u8, // First byte of smallest suffix
max_key: u8, // First byte of largest suffix
flags: u16, // Is_pure, is_sorted, etc.
prefix_len: u16, // Shared prefix length (implicit from path)
lsn: u64, // Last modification LSN
checksum: u64, // CRC of contents
}
#[repr(C)]
pub struct StringEntry {
offset: u16, // Offset in data section
length: u8, // Suffix length
flags: u8, // Is_final, has_value, etc.
value_offset: u16, // Offset to value (if any)
value_length: u16, // Value length
}
Search (binary search within bucket):
impl LeafBucket {
pub fn search(&self, suffix: &[u8]) -> Option<&StringEntry> {
let entries = &self.directory[..self.header.num_entries as usize];
entries.binary_search_by(|entry| {
let stored = self.get_suffix(entry);
stored.cmp(suffix)
}).ok().map(|i| &entries[i])
}
fn get_suffix(&self, entry: &StringEntry) -> &[u8] {
let start = entry.offset as usize;
let end = start + entry.length as usize;
&self.data[start..end]
}
}
Insert:
impl LeafBucket {
pub fn insert(&mut self, suffix: &[u8], value: &[u8]) -> Result<(), BucketError> {
if !self.has_space(suffix.len() + value.len()) {
return Err(BucketError::Full);
}
// Find insertion position
let pos = self.directory[..self.header.num_entries as usize]
.binary_search_by(|e| self.get_suffix(e).cmp(suffix))
.unwrap_or_else(|i| i);
// Shift entries to make room
let n = self.header.num_entries as usize;
self.directory.copy_within(pos..n, pos + 1);
// Write suffix to data section
let suffix_offset = self.header.free_offset;
self.data[suffix_offset as usize..][..suffix.len()]
.copy_from_slice(suffix);
// Write value
let value_offset = suffix_offset + suffix.len() as u16;
self.data[value_offset as usize..][..value.len()]
.copy_from_slice(value);
// Create entry
self.directory[pos] = StringEntry {
offset: suffix_offset,
length: suffix.len() as u8,
flags: StringEntryFlags::IS_FINAL,
value_offset,
value_length: value.len() as u16,
};
self.header.num_entries += 1;
self.header.free_offset = value_offset + value.len() as u16;
Ok(())
}
}
When a bucket is full, split it:
pub fn split_bucket(bucket: &LeafBucket) -> (LeafBucket, LeafBucket, u8) {
// Find median to balance split
let mid = bucket.header.num_entries / 2;
let split_key = bucket.directory[mid as usize].first_byte();
let mut left = LeafBucket::new();
let mut right = LeafBucket::new();
for entry in bucket.entries() {
if entry.first_byte() < split_key {
left.insert_entry(entry);
} else {
right.insert_entry(entry);
}
}
(left, right, split_key)
}
After split, the parent ART node gets a new child pointer for the right bucket.
impl<V: DictionaryValue> Dictionary for PersistentARTrie<V> {
type Node = PersistentARTrieNode<V>;
fn root(&self) -> Self::Node {
PersistentARTrieNode {
ptr: self.root_ptr.clone(),
buffer_mgr: self.buffer_mgr.clone(),
depth: 0,
}
}
fn contains(&self, term: &str) -> bool {
self.get(term.as_bytes()).is_some()
}
fn len(&self) -> Option<usize> {
Some(self.entry_count.load(Ordering::Acquire))
}
fn sync_strategy(&self) -> SyncStrategy {
SyncStrategy::InternalSync // Thread-safe via atomic swizzling
}
}
This is critical for Levenshtein automata traversal:
impl<V: DictionaryValue> DictionaryNode for PersistentARTrieNode<V> {
type Unit = u8;
fn is_final(&self) -> bool {
match self.load_node() {
LoadedNode::Inner(node) => node.header().is_final,
LoadedNode::Bucket(bucket) => {
// Check if empty suffix exists in bucket
bucket.contains_suffix(&[])
}
}
}
fn transition(&self, label: u8) -> Option<Self> {
match self.load_node() {
LoadedNode::Inner(node) => {
node.find_child(label).map(|child_ptr| {
PersistentARTrieNode {
ptr: child_ptr,
buffer_mgr: self.buffer_mgr.clone(),
depth: self.depth + 1,
}
})
}
LoadedNode::Bucket(bucket) => {
// In a bucket, transition means moving to next suffix byte
if bucket.has_suffix_starting_with(label) {
Some(self.bucket_child_node(label))
} else {
None
}
}
}
}
fn edges(&self) -> Box<dyn Iterator<Item = (u8, Self)> + '_> {
match self.load_node() {
LoadedNode::Inner(node) => {
Box::new(node.children().map(move |(label, child_ptr)| {
(label, PersistentARTrieNode {
ptr: child_ptr,
buffer_mgr: self.buffer_mgr.clone(),
depth: self.depth + 1,
})
}))
}
LoadedNode::Bucket(bucket) => {
// Iterate unique first bytes of suffixes
Box::new(bucket.first_bytes().map(move |b| {
(b, self.bucket_child_node(b))
}))
}
}
}
}
impl<V: DictionaryValue> MappedDictionary for PersistentARTrie<V> {
type Value = V;
fn get_value(&self, term: &str) -> Option<V> {
self.get(term.as_bytes())
}
}
impl<V: DictionaryValue> MutableMappedDictionary for PersistentARTrie<V> {
fn insert(&mut self, term: &str, value: V) -> Result<bool, Error> {
// ... insert implementation with WAL logging
}
fn remove(&mut self, term: &str) -> Result<Option<V>, Error> {
// ... remove implementation with WAL logging
}
}
Levenshtein automata traversal has predictable patterns:
Prefetch children while processing current node:
impl<V: DictionaryValue> PersistentARTrieNode<V> {
pub fn prefetch_children(&self) {
if let LoadedNode::Inner(node) = self.load_node() {
for child_ptr in node.child_pointers() {
if !child_ptr.is_swizzled() {
let (block_id, _, _) = child_ptr.disk_location().unwrap();
self.buffer_mgr.prefetch_async(block_id);
}
}
}
}
}
// Integration with transducer
impl<D: Dictionary> QueryIterator<D> {
fn advance_with_prefetch(&mut self) {
if let Some(node) = self.current_node() {
// Prefetch before processing
if let Some(art_node) = node.as_persistent_art() {
art_node.prefetch_children();
}
}
// ... normal advance logic
}
}
For buckets, we can batch-check Levenshtein candidates:
impl LeafBucket {
/// Check all strings in bucket against Levenshtein automaton
pub fn levenshtein_matches<A: LevenshteinAutomaton>(
&self,
automaton: &A,
prefix: &[u8], // Path to this bucket
) -> Vec<(String, usize)> {
let mut matches = Vec::new();
for entry in self.entries() {
let suffix = self.get_suffix(entry);
let full_term: Vec<u8> = prefix.iter()
.chain(suffix.iter())
.copied()
.collect();
if let Some(distance) = automaton.eval(&full_term) {
matches.push((
String::from_utf8_lossy(&full_term).into_owned(),
distance,
));
}
}
matches
}
}
Pin frequently-accessed nodes:
pub struct PersistentARTrie<V> {
// ...
hot_nodes: RwLock<Vec<PageId>>, // Permanently pinned pages
}
impl<V: DictionaryValue> PersistentARTrie<V> {
pub fn warm_cache(&self, depth: usize) {
// Pin root and first `depth` levels
let mut hot = Vec::new();
self.collect_hot_pages(&self.root, depth, &mut hot);
for page_id in &hot {
self.buffer_mgr.pin_permanent(*page_id);
}
*self.hot_nodes.write() = hot;
}
}
persistent_artrie.db
├── Header (4KB)
│ ├── Magic number
│ ├── Version
│ ├── Root pointer
│ ├── Entry count
│ └── Metadata
├── Index blocks (ART nodes)
│ └── 256KB blocks packed with nodes
├── Leaf blocks (Buckets)
│ └── 8KB buckets
└── Free list
└── Available block IDs
#[repr(C)]
pub struct FileHeader {
magic: [u8; 8], // "PART_v01"
version: u32, // Format version
flags: u32, // Compression, etc.
root_block: u32, // Root node block ID
root_offset: u32, // Root node offset in block
entry_count: u64, // Total strings stored
block_count: u64, // Total blocks allocated
index_block_count: u64, // ART node blocks
leaf_block_count: u64, // Bucket blocks
checksum: u64, // Header checksum
created_at: u64, // Unix timestamp
modified_at: u64, // Unix timestamp
reserved: [u8; 4008], // Pad to 4KB
}
Block ID allocation:
0 : Header
1..1M : Index blocks (ART nodes)
1M..8M : Leaf blocks (Buckets)
8M+ : Overflow (if needed)
Files to create:
src/dictionary/persistent_artrie/mod.rssrc/dictionary/persistent_artrie/swizzled_ptr.rssrc/dictionary/persistent_artrie/buffer_manager.rsTasks:
Files to create:
src/dictionary/persistent_artrie/nodes.rssrc/dictionary/persistent_artrie/node_ops.rsTasks:
Files to create:
src/dictionary/persistent_artrie/bucket.rsTasks:
Files to create:
src/dictionary/persistent_artrie/dict_impl.rssrc/dictionary/persistent_artrie/node_impl.rsTasks:
PersistentARTrieNode implementing DictionaryNodeDictionary, MappedDictionary implementationsMutableMappedDictionary for insert/removeTasks:
Files to create:
src/dictionary/persistent_artrie_char/Tasks:
PersistentARTrieChar for char units| Operation | Time Complexity | Expected Disk I/Os |
|---|---|---|
| Exact lookup | 𝒪(m) | 2-4 |
| Insert | 𝒪(m + log B) amortized | 2-4 + 1 write |
| Delete | 𝒪(m + log B) | 2-4 + 1 write |
| Prefix search | 𝒪(m + k) | 𝒪(m/fanout + k/B) |
| Levenshtein (d=1) | 𝒪(n·m) | Varies with pruning |
| Levenshtein (d=2) | 𝒪(n·m·d) | Varies with pruning |
Where:
The Persistent ARTrie design combines:
This hybrid approach provides:
Askitis, N. & Zobel, J. (2009). "B-tries for disk-based string management." VLDB Journal.
Leis, V., Kemper, A., & Neumann, T. (2013). "The Adaptive Radix Tree." ICDE.
DuckDB Team. (2022). "Persistent Storage of Adaptive Radix Trees in DuckDB."
Luo, X. et al. (2023). "SMART: A High-Performance Adaptive Radix Tree for Disaggregated Memory." OSDI.
Binna, R. et al. (2018). "HOT: A Height Optimized Trie Index." SIGMOD.
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 |