p-fast trie, but smaller

https://dotat.at/@/2025-08-06-p-fast-trie.html

Previously, I wrote some sketchy ideas for what I call a p-fast trie, which is basically a wide fan-out variant of an x-fast trie. It allows you to find the longest matching prefix or nearest predecessor or successor of a query string in a set of names in O(log k) time, where k is the key length.

My initial sketch was more complicated and greedy for space than necessary, so here's a simplified revision.

( Read more... )