The eternal quest for optimal key-value storage takes a fascinating turn with a new data structure proposal: the p-fast trie. Unlike conventional trie implementations that use tree structures with internal pointers, this experimental approach leverages hash maps organized by key prefix lengths, coupled with popcount-compressed bitmaps for navigation. The design promises intriguing asymptotic improvements but introduces significant memory trade-offs.

Breaking the Trie Mold

Traditional qp-tries use tree structures where each node branches based on key chunks. The p-fast trie radically reimagines this by:
- Storing all strict key prefixes in a hash map, with each prefix mapping to an interior node
- Using 64-bit popcount bitmaps at each node to indicate valid next chunks
- Maintaining leaf objects in a circular linked list for successor/predecessor traversal
- Splitting keys into fixed-size chunks (e.g., 6-bit segments)

As the anonymous author notes:

"Exact-match lookups are normal O(1) hash map lookups. Predecessor/successor searches use binary chop on the length of the key."

Performance Trade-Offs

The p-fast trie offers compelling theoretical advantages:
- O(1) exact matches via direct hash lookups
- O(log k) predecessor searches via binary chop across key lengths
- Elimination of pointer-chasing in successful lookups

Yet significant questions remain:

// Rust implementation challenges include:
let leaf_ownership = hash_map.entry(prefix).or_insert_with(|| {
    // Interior nodes must reference leaves without ownership issues
    InteriorNode::new()
});
  • Memory overhead: All prefixes require hash entries, potentially bloating storage
  • Cache behavior: Long prefix lookups may exhibit poor locality versus qp-trie's root-proximal searches
  • Concurrency complexity: Multi-hashmap updates during inserts/deletes complicate thread safety

The Practical Verdict

While the O(log k) bound theoretically beats qp-trie's O(k) for predecessor searches, real-world performance depends heavily on memory access patterns. Qp-tries benefit from compact storage and cache-friendly root-level operations, while p-fast tries might suffer from hash collisions and scattered long-prefix accesses. The author acknowledges uncertainty:

"It isn’t obvious how a p-fast trie might compare to a qp-trie in practice... Many steps of a qp-trie search are checking short prefixes of the key near the root of the tree, which should be well cached."

This proposal exemplifies how rethinking fundamental structures can yield novel approaches—even if they ultimately serve as thought experiments rather than production solutions. For developers working on high-performance key stores, the design sparks valuable conversations about the physics of data structure efficiency in modern hardware environments.

_Source: Dotat.at_