Merges using key range data structures

1. A method for performing a multi-level merge operation that involves at least three levels of a log-structured merge tree (LSM tree), the method comprising:

storing, by a computer system, files across a plurality of levels included in the LSM tree, wherein a given file stores a set of records associated with a set of database keys;

determining, by the computer system, to perform the multi-level merge operation for a particular merge key range; and

performing, by the computer system, the multi-level merge operation, including:

identifying levels of the LSM tree from which to copy records that fall within the particular merge key range into a target level of the LSM tree, wherein the identifying includes assessing a number of records contributed by ones of the plurality of levels for the particular merge key range and selecting sufficient levels for the multi-level merge operation to merge at least a threshold number of records into the target level, and wherein the identified levels include the at least three levels of the LSM tree; and

copying, from the identified levels, a set of records that fall within the particular merge key range into a file at the target level.

2. The method of claim 1 , wherein the multi-level merge operation is determined to be performed in place of a merge operation involving two levels in response to the computer system determining that a number of records contributed by two particular levels for the merge operation does not satisfy a threshold number of records.

3. The method of claim 1 , further comprising:

storing, by the computer system, a database key structure in association with a particular one of the identified levels, wherein the database key structure indicates, for a particular file of the particular identified level, a set of key ranges derived from a set of records stored in the particular file,

wherein the assessing includes determining a number of records that is contributed by the particular identified level based on an overlap between the particular merge key range and the set of key ranges identified by the database key structure.

4. The method of claim 3 , wherein the database key structure is a trie that includes a plurality of branches, a given one of which includes a set of linked nodes corresponding to a set of character values of a database key associated with a database record included in the particular file.

5. The method of claim 1 , further comprising:

assigning, by the computer system, a first priority level to the multi-level merge operation and a second priority level to a merge operation involving two levels of the LSM tree, wherein the first priority level and the second priority level are different priorities.

6. The method of claim 5 , further comprising:

creating, by the computer system, a work item to be processed to perform the multi-level merge operation, wherein the work item is associated with the first priority level that is assigned to the multi-level merge operation; and

enqueueing, by the computer system, the work item in a priority queue that orders work items according to priority level.

7. The method of claim 1 , wherein the particular merge key range corresponds to a key range of a particular file included in the identified levels of the LSM tree.

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

storing files across a plurality of levels included in an LSM tree, wherein a given file stores a set of records associated with a set of database keys;

determining to perform a multi-level merge operation for a particular merge key range; and

performing the multi-level merge operation, including:

identifying levels of the LSM tree from which to copy records that fall within the particular merge key range into a target level of the LSM tree, wherein the identifying includes assessing a number of records contributed by ones of the plurality of levels for the particular merge key range and selecting sufficient levels for the multi-level merge operation to merge at least a threshold number of records into the target level, and wherein the identified levels include at least three levels of the LSM tree; and

copying, from the identified levels, a set of records that fall within the particular merge key range into a file at the target level.

9. The non-transitory computer-readable medium of claim 8 , wherein the multi-level merge operation is determined to be performed in place of a merge operation involving two levels in response to the computer system determining that a number of records contributed by two particular levels for the merge operation does not satisfy a threshold number of records.

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

determining, for a particular level of the levels, a number of records contributed by the particular level based on an overlap between the particular merge key range and a set of key ranges identified by a database key structure stored for the particular level.

11. The non-transitory computer-readable medium of claim 8 , wherein the operations further comprise:

assigning a first priority level to the multi-level merge operation; and

based on the first priority level, performing at least one other merge operation before the multi-level merge operation.

12. The non-transitory computer-readable medium of claim 8 , wherein the particular merge key range corresponds to a key range of a particular file included in the identified levels of the LSM tree.

13. A system, comprising:

at least one processor; and

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

storing files across a plurality of levels included in an LSM tree, wherein a given file stores a set of records associated with a set of database keys;

determining to perform a multi-level merge operation for a particular merge key range; and

performing the multi-level merge operation, including:

identifying levels of the LSM tree from which to copy records that fall within the particular merge key range into a target level of the LSM tree, wherein the identifying includes assessing a number of records contributed by ones of the plurality of levels for the particular merge key range and selecting sufficient levels for the multi-level merge operation to merge at least a threshold number of records into the target level, and wherein the identified levels include at least three levels of the LSM tree; and

copying, from the identified levels, records that fall within the particular merge key range into a file at the target level.

14. The system of claim 13 , wherein the multi-level merge operation is determined to be performed in place of a merge operation involving two levels in response to the system determining that a number of records contributed by two particular levels for the merge operation does not satisfy a threshold number of records to be contributed to the target level.

15. The system of claim 13 , wherein the operations further comprise:

assigning a first priority level to the multi-level merge operation and a second priority level to a merge operation involving two levels of the LSM tree, wherein the multi-level merge operation and the merge operation are performed in an order defined by priority level.

16. The system of claim 13 , wherein the particular merge key range corresponds to a key range of a particular file included in the identified levels of the LSM tree.