Merges using key range data structures

A non-transitory computer readable medium having program instructions stored thereon that are executable by a computer system to cause the computer system to perform operations comprising:

• storing, in a database:
• a plurality of files as part of a log-structured merge-tree (LSM tree);
• and
• a plurality of database key structures, wherein a given one of the plurality of database key structures indicates, for a corresponding file, a set of database keys derived from database records included in the corresponding file;
• determining, using ones of the plurality of database key structures, a key range overlap that is indicative of an extent of overlap of key ranges from a set of the plurality of files with respect to a particular key range;
• and
• based on the determined key range overlap, assigning a first priority level to a first merge operation that involves the set of files;
• and
• assigning a second priority level to a second merge operation that involves a different set of files, wherein the key range overlap associated with the first merge operation involves more overlapping keys than a key range overlap that is associated with the second merge operation, and wherein the first priority level is a higher priority than the second priority level.

A method, comprising:

• storing, by a computer system, in a database:
• a plurality of files as part of a log-structured merge-tree (LSM tree);
• and
• a plurality of trie data structures, wherein a given trie data structure indicates, for a corresponding one of the plurality of files, a set of database keys that is associated with the corresponding file;
• generating, by the computer system, a first merge work item to be performed to merge, into a file included in a target level, content from a set of other files included in at least two levels of the LSM tree, wherein the first merge work item is assigned a first priority level that is determined based on a key range overlap of the set of other files with respect to a particular key range, and wherein the key range overlap calculated using ones of the plurality of trie data structures;
• and
• storing, by the computer system, the first merge work item in a priority queue that orders merge work items according to priority level;
• and
• assigning, by the computer system, a second priority level to a second merge work item that involves a different set of files, wherein the key range overlap associated with the first merge work item involves more overlapping keys than a key range overlap that is associated with the second merge work item, and wherein the first priority level is a higher priority than the second priority level.