Scalable data structures

摘要

The technology is directed to providing sequential access to data using scalable data structures. In some embodiments, the scalable data structures include a first data structure, e.g., hash map, and a second data structure, e.g., tree data structure (“tree”). The technology receives multiple key-value pairs representing data associated with an application. A key includes a prefix and a suffix. While the suffixes of the keys are distinct, some of the keys can have the same prefix. The technology stores the keys having the same prefix in a tree, and stores the root node of the tree in the first data structure. To retrieve values of a set of input keys with a given prefix, the technology retrieves a root node of a tree corresponding to the given prefix from the first data structure using the given prefix, and traverses the tree to obtain the values in a sequence.

主权项

1. A method performed by a computing system, comprising:
receiving multiple keys and corresponding values for the keys, each of the keys being a combination of a prefix and a suffix; generating multiple tree data structures, wherein the multiple tree data structures include a tree data structure for storing a subset of the keys having a first prefix of distinct prefixes of the keys, wherein all keys in the tree data structure share the first prefix, and wherein each of the multiple tree data structures stores keys that share a specified prefix of the distinct prefixes; and storing, in a first data structure having multiple root nodes of the multiple tree data structures, a root node of the tree data structure wherein the root node is indexed in the first data structure based on the first prefix, wherein each of the root nodes is indexed based on a specified prefix shared by keys stored in the corresponding tree data structure, the storing including storing the subset of the keys as child nodes of the root node in the tree data structure, the child nodes stored in a specified order.