trie

The problem is that a trie is a very cache-loose data structure.

The database is doing row caching, though, and isn't going to be caching lower levels of the trie in close proximity to the higher ones.

The gold standard for a trie is probably the Judy array[1], which I've heard has some patents on it, but I can't confirm.

The result was that it was much more space-efficient than the trie implementation from TFA (only slightly larger than the hash table), but about 1.8x slower than the trie implementation.

By the time you hash a key, you could have likely already inserted it into a trie.

It seems you'd get more mileage out of a trie if you also compared it with a sort of zipper approach.

My intuition is that a Radix tree trie would make a lot more sense and is more maintainable than such a hack.

Any problem where there's a lot of suffix/prefix reusage benefits from a proper trie implementation (or suffix array/tree as alternative) - ex.

If you are using the data in order, the trie may be faster because the next entry will likely already be cached.

Nope I didn't - I did this work in 2006, and the HAT trie didn't come out until 2007.

Skip lists for a suitable sized prefix would likely be more space efficient than a trie, but some trie types such as radix-trees [3] with a sufficiently high radix value, could also be quite efficient.

I think the biggest problem with this trie implementation is the amount of pointer-chasing due to the low branching factor.

Depending on how you order the trie, you can only get the first k completions by lexicographic ordering, which could be very far from the "best" completions.

The idea being that if I type "a", I should just focus the trie around "A".

It's a quirk of analysis that a hash table is allowed to take the modulo (for example) of an arbitrarily large number, producing an arbitrarily large number, in "constant time", while a trie is not allowed to descend to an arbitrary depth in constant time.

And even if you did just care about "in practice" limitations, you're stuck with the problem of the hash computation taking longer than any realizable trie lookup would (as another poster mentioned is common), meaning that the O(1) claim misrepresents performance relative to another data structure.

Trie) that contains every Wikipedia title and the byte-offset within the wiki.xml where the title was found.