4 years ago

Category: PHP

Tries are composite types that do not necessarily have the same prominence in programming parlance as say, an array or record/tuple but have significant viability that stems from their uniqueness. A trie is a tree structure with a single empty parent node and multiple character descendants that each share a common prefix.

Storage of data in a trie is such that key-constituting characters exist in branching character hierarchies — as individual nodes that descend from one another.

The solution to the space and caching inefficiencies of the most primitive trie structure is another entry in the line of trie — the HAT trie.

All in all, it is safe to posit that the HAT trie is just a more efficient burst trie: one that combines the compression achievable from burst mechanics, and cache-consciousness of array hashes.