Trie-based indices for databases

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.

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.