Trie-based indices for databases
A database system uses byte ordering for keys and a trie index to reference stored data. The keys of a database are converted into byte-comparable sequences of byte values. The trie index is generated including nodes connected by edges defining paths from a root node to leaf nodes. Each edge is associated with at least one byte value such that each path from the root node to a leaf node through one or more edges defines a unique byte prefix for a byte-comparable sequence of byte values. The leaf node of each path is associated with a database location value. A record is accessed in the database using a database location value determined from referencing the trie index using a byte-comparable sequence of byte values of the record generated from a key of the record. A trie structure and byte ordered keys may be used for partition or row indices.
1. A database system, comprising:
a cluster of database nodes that stores a distributed database, each database node storing one or more partitions of the distributed database, each partition including a set of database rows, each database node including:
one or more processors; and
a memory storing instructions that, when executed by the one or more processors, cause the one or more processors to:
access a key for a record including a partition key and a clustering key;
convert the key into a byte-comparable sequence of byte values comprising a first portion of the byte-comparable sequence of bytes obtained from the partition key and a second portion of the byte-comparable sequence of bytes obtained from the clustering key;
reference a partition trie index using the byte-comparable sequence of byte values of the record generated from the key to determine a partition of the distributed database; and
access the record from the partition of the distributed database.
2. The database system of claim 1 , wherein the instructions when executed by the one or more processors, cause the one or more processors to:
access the partition trie index using the first portion of the byte-comparable sequence.
3. The database system of claim 1 , wherein the instructions when executed by the one or more processors, cause the one or more processors to:
access a row trie index using the second portion of the byte-comparable sequence.
4. The database system of claim 3 , wherein the partition trie index and the row trie index provide an index of records stored in the rows and columns of a partition.
5. The database system of claim 3 , wherein the partition trie index and the row trie index each comprise a trie data structure that describes a mapping between sequences of byte values and database location values of the database.
6. The database system of claim 3 , wherein the partition trie index maps to database location values of the row trie index.
7. The database system of claim 6 , wherein the row trie index maps to database location values of the rows.
8. A non-transitory computer readable memory storing instructions that, when executed by one or more processors, cause the one or more processors to:
store a distributed database in a cluster of database nodes, each database node storing one or more partitions of the distributed database, each partition including a set of database rows, each database node including:
access a key for a record including a partition key and a clustering key;
convert the key into a byte-comparable sequence of byte values comprising a first portion of the byte-comparable sequence of bytes obtained from the partition key and a second portion of the byte-comparable sequence of bytes obtained from the clustering key;
reference a partition trie index using the byte-comparable sequence of byte values of the record generated from the key to determine a partition of the distributed database; and
access the record from the partition of the distributed database.
9. The computer readable memory of claim 8 , wherein the instructions when executed by the one or more processors, cause the one or more processors to:
access a partition trie index using the first portion of the byte-comparable sequence.
10. The computer readable memory of claim 8 , wherein the instructions when executed by the one or more processors, cause the one or more processors to:
access a row trie index using the second portion of the byte-comparable sequence.
11. The computer readable memory of claim 10 , wherein the partition trie index and the row trie index provide an index of records stored in the rows and columns of a partition.
12. The computer readable memory of claim 10 , wherein the partition trie index and the row trie index each comprise a trie data structure that describes a mapping between sequences of byte values and database location values of the database.
13. The computer readable memory of claim 10 , wherein the partition trie index maps to database location values of the row trie index.
14. The computer readable memory of claim 13 , wherein the row trie index maps to database location values of the rows.
15. A method, comprising:
storing a distributed database in a cluster of database nodes, each database node storing one or more partitions of the distributed database, each partition including a set of database rows, each database node including:
accessing a key for a record including a partition key and a clustering key;
converting the key into a byte-comparable sequence of byte values comprising a first portion of the byte-comparable sequence of bytes obtained from the partition key and a second portion of the byte-comparable sequence of bytes obtained from the clustering key;
referencing a partition trie index using the byte-comparable sequence of byte values of the record generated from the key to determine a partition of the distributed database; and
accessing the record from the partition of the distributed database.
16. The method of claim 15 , further comprising:
accessing a partition trie index using the first portion of the byte-comparable sequence.
17. The method of claim 15 , further comprising:
accessing a row trie index using the second portion of the byte-comparable sequence.
18. The method of claim 17 , wherein the partition trie index and row trie index provide an index of records stored in the rows and columns of a partition.
19. The method of claim 17 , wherein the partition trie index and the row trie index each comprise a trie data structure that describes a mapping between sequences of byte values and database location values of the database.
20. The method of claim 17 , wherein the partition trie index maps to database location values of the row trie index and the row trie index maps to database location values of the rows.