algorithms review : tries | take #1

July 29, 2010

  • Tries represent prefix trees
  • String search in O(log(n)) is naturally obtained by adding strings to trie
  • Common case for key-value stores is “get all keys by prefix” – Trie is a natural way to achieve this. Can this be mapped to key-value store ? Indeed – we map each tree node to a entry in hashmap and store keys representing child nodes in that key’s content.
  • HashTrie – popular extension of key-value stores -> update is O(len(key)), retrieval is O(len(key)). The main problem is due to the fact that we need to update key *content* in order to maintain the tree – which makes ConcurrentHashTree relatively complex to design
  • How to iterate HashTrie ? – would require having a master-key that would act as top-level node and contain keys of all first-level child keys
  • SortedHashTrie ?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: