Patent ID: 8868926

Claim:
A computer-implemented method for bursting a hash table of a key-value database, the method comprising: receiving a key and a value associated with the key; traversing trie nodes of the key-value database from a root node to a leaf node by recursively dividing the key into a prefix and a suffix, wherein with every iteration, the key is attributed a value associated with the suffix and compared to a value of a current node of the key-value database; reaching the leaf node of the key-value database, the leaf node being the hash table, the hash table being a pure hash table reachable by a single prefix, the keys for all key-value pairs stored in the hash table beginning with the single prefix; determining that the key is not stored in the hash table; determining that the hash table is not able to store the key and the value; removing the hash table; associating a new trie node with a parent trie node; associating two or more new hash tables with the new trie node, one of the two or more new hash tables being able to store the key and the value; moving all keys and associated values from the hash table into one of the two or more new hash tables; and inserting the key and the associated value into one of the two or more new hash tables.