Tries are a very interesting data structure. Tries are designed to compress string prefixes to allow the storage of large string datasets in a memory-efficient manner. Tries are built as trees of substrings. In fact, the word "trie" was selected because the word "tree" was already taken; initially trie was pronounced identicially as tree, but spelled differently to differentiate the two structures.

There are many different flavors of trie, each with different trade offs.

Static Tries

Dynamic Tries

• Array Trie

• Patricia array

• Burst Trie

• HAT Trie

• Judy

• B-Trie

• Suffix Trees

• LOUDS-Sparse / LOUDS-Dense / Surf

• Radix Trie

• Compact Trie

• R-way Trie

• De la Briandais Trie

• List Trie

• Ternary Search Trie

• Double-array

Node Label Map

In practice, most tries don't actually store the characters on each node, but instead store them in a Node Label Map, which is a data structure mapping from unique integer IDs to substrings.

There are different NLM implementations, each again offering different trade-offs.

• m-Bonsai

• FK-hash