Index for multi-level data structures

1 . A method, comprising:

storing, by a computer system, a set of records associated with a set of keys;

creating, by the computer system, a plurality of tries that facilitate key range counts, wherein a given trie of the plurality of tries encodes a respective subset of the set of keys using a plurality of vector structures;

creating, by the computer system, index metadata usable to access the plurality of tries, wherein the index metadata specifies for the given trie:

a marker key corresponding to one of the respective subset of keys that was encoded in the given trie;

a location of the given trie; and

a key count indicative of a number of keys encoded in the given trie; and

performing, by the computer system, a key range count to determine a count value that is indicative of a number of keys within a particular key range, wherein the performing includes:

accessing the index metadata and at least two of the plurality of tries, wherein the at least two tries include a first trie corresponding to a start key of the particular key range and a second trie corresponding to an end key of the particular key range;

counting keys, of the at least two tries by traversing the plurality of vector structures of the at least two tries, that are within the particular key range to determine respective numbers of keys; and

deriving the count value based on the respective numbers of keys counted and one or more key counts specified in the index metadata.

2 . The method of claim 1 , wherein the first trie is associated with a marker key that is closest to, but sequentially before, the start key of the particular key range relative to marker keys of other ones of the plurality of tries, and wherein the second trie is associated with a marker key that is closest to, but sequentially before, the end key of the particular key range relative to the marker keys of the other tries.

3 . The method of claim 1 , wherein the marker key corresponds to a start key of the given trie, and wherein the index metadata further specifies an end key for the given trie.

4 . The method of claim 1 , wherein the index metadata is a trie that forms a part of a top level of a trie hierarchy, and wherein the plurality of tries form a bottom level of the trie hierarchy.

5 . The method of claim 1 , wherein the index metadata further specifies, for the given trie, one or more index block numbers identifying index blocks that store pointers to records corresponding to the subset of keys encoded in the given trie.

6 . A non-transitory computer readable medium having program instructions stored thereon that are capable of causing a computer system to perform operations comprising:

storing a set of records associated with a set of keys;

creating a plurality of tries that facilitate key range counts, wherein a given trie of the plurality of tries encodes a respective subset of the set of keys using a plurality of vector structures;

creating index metadata usable to access the plurality of tries, wherein the index metadata specifies for the given trie:

a marker key corresponding to one of the respective subset of keys that was encoded in the given trie;

a location of the given trie; and

a key count indicative of a number of keys encoded in the given trie; and

performing a key range count to determine a count value indicative of a number of keys within a particular key range, wherein the performing includes:

accessing the index metadata and at least two of the plurality of tries, wherein the at least two tries include a first trie corresponding to a start key of the particular key range and a second trie corresponding to an end key of the particular key range;

counting keys, of the at least two tries by traversing the plurality of vector structures of the at least two tries, that are within the particular key range to determine respective numbers of keys; and

deriving the count value based on the respective numbers of keys counted and one or more key counts specified in the index metadata.

7 . The non-transitory computer readable medium of claim 6 , wherein the first trie is associated with a marker key that is closest to, but sequentially before, the start key of the particular key range relative to marker keys of other ones of the plurality of tries, and the second trie is associated with a marker key that is closest to, but sequentially before, the end key of the particular key range relative to the marker keys of the other tries.

8 . The non-transitory computer readable medium of claim 6 , wherein the performing includes:

determining that a key range associated with a particular one of the plurality of tries is encompassed by the particular key range; and

deriving the count value without accessing the particular trie to count keys of the particular trie.

9 . The non-transitory computer readable medium of claim 8 , wherein the index metadata specifies a number of keys contributed to the count value by the particular trie.

10 . A system, comprising:

at least one processor; and

memory having program instructions stored thereon that are executable by the at least one processor to cause the system to perform operations comprising:

storing a set of records associated with a set of keys;

creating a plurality of tries that facilitate key range counts, wherein a given trie of the plurality of tries encodes a respective subset of the set of keys using a plurality of vector structures;

creating index metadata usable to access the plurality of tries, wherein the index metadata specifies for the given trie:

a marker key corresponding to one of the respective subset of keys that was encoded in the given trie;

a location of the given trie; and

a key count indicative of a number of keys encoded in the given trie; and

performing a key range count to determine a count value indicative of a number of keys within a particular key range, wherein the performing includes:

accessing the index metadata and at least two of the plurality of tries, wherein the at least two tries include a first trie corresponding to a start key of the particular key range and a second trie corresponding to an end key of the particular key range;

counting keys, of the at least two tries by traversing the plurality of vector structures of the at least two tries, that are within the particular key range to determine respective numbers of keys; and

deriving the count value based on the respective numbers of keys counted and one or more key counts specified in the index metadata.

11 . The system of claim 10 , wherein the first trie is associated with a marker key that is closest to, but sequentially before, the start key of the particular key range relative to marker keys of other ones of the plurality of tries, and the second trie is associated with a marker key that is closest to, but sequentially before, the end key of the particular key range relative to the marker keys of the other tries.

12 . The system of claim 10 , wherein creating the given trie includes:

computing rank and select values for the given trie; and

storing the computed rank and select values in the given trie to be used for traversing the given trie.

13 . The system of claim 10 , wherein the set of records are maintained in a particular region of a database, and wherein the operations further comprise storing the plurality of tries in the particular region.

14 . The method of claim 1 , wherein each of the plurality of tries is created to have a fixed size corresponding to a single cache block of a block cache of the computer system.

15 . The method of claim 1 , wherein the plurality of vector structures includes a prefix vector, a suffix vector, a Level-Order Unary Degree Sequence vector, and a has-child vector.

16 . The method of claim 15 , wherein the prefix vector stores prefix characters identified by determining a difference between a first overlap of a current key and a previous key and a second overlap of the current key and a next key.

17 . The method of claim 1 , wherein the creating of the plurality of tries includes:

determining rank and select values for at least one of the plurality of vector structures; and

storing the rank and select values in the given trie to facilitate traversing of the plurality of vector structures.