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.