But How would we store Trie in DB?


#1

But How would we store Trie in DB ?


#2

Maintain a shard of 26 nodes for 26 characters. Each node in this shard maintains words from a to z respectively and also acts as a parent/routing node.


#3

As the count for a prefix (say "as") goes beyond a threshold, a new shard is added and the corresponding trie is moved there. What parent maintains is a reference to this shard now corresponding to its key.


#4

As per other answers: trie can be design as multi level hashtable. thus, the k v data store is the choice.