| 摘要 |
Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for storing data on in a storage medium. In one aspect, a method includes receiving a key-value pair including a key k and a value v. The method further includes encoding the key-value pair as (i) a first key-value pair including a first key k1 and first value v1, and (ii) a second key-value pair including a second key k2. The method further includes inserting the first key-value pair and the second key-value pair in a trie. |
| 主权项 |
1. A computer-implemented method comprising:
receiving, by a computing device, an original, unencoded key k for which a particular value v from among multiple values that are stored for the original, unencoded key k is to be obtained; generating, by the computing device, a trie key that includes an encoded representation of the original, unencoded key k; retrieving, from a computer-readable medium of the computing device, a trie value v1 by accessing a trie using the trie key that includes the encoded representation of the original, unencoded key k, wherein the trie is configured to store a given key-value pair as both (i) a first trie key-trie value pair comprising a first trie key that includes a first encoded representation of the given key and a first trie value that includes an encoded representation of the given value, and (ii) a second trie key-trie value pair comprising a second trie key that includes a second encoded representation of the given key and a second trie value that includes an integer; generating, by the computing device, a portion of a trie key k1 based on the trie value v1; extracting, from the computer readable medium, a remaining portion of the trie key k1 by accessing the trie using the portion of the trie key k1; and outputting, by the computing device, the remaining portion of the trie key k1 as the particular value v from among the multiple values that are stored for the original, unencoded key k. |
