But How would we store Trie in DB?


But How would we store Trie in DB ?


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.


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.


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