Large range lookups for Bϵ-tree

Patent metadata

Field	Value
Publication number	US-11093471-B2
Application number	US-201816000142-A
Country	US
Kind code	B2
Filing date	Jun 5, 2018
Priority date	Jun 5, 2018
Publication date	Aug 17, 2021
Grant date	Aug 17, 2021

Abstract

Embodiments herein are directed towards systems and methods for performing range lookups in Bε-trees. One example method involves receiving a request to return key-value pairs within a range of keys from the Bε-tree. The Bε-tree includes a plurality of nodes, each node being associated with a buffer that stores key-value pairs. The method further involves determining a fractional size of the range of keys. The method further involves, for each level of the Bε-tree, obtaining from within one or more buffers of one or more nodes of the level, a set of key-value pairs within the range of keys up to a size equal to the fractional size and transferring the set of key-value pairs to a result data structure. The method further involves sorting and merging all key-value pairs in the result data structure and returning the result data structure in response to the request.

First claim

We claim:

1. A method for performing a range lookup in a B ε -tree, comprising:
receiving a request to return key-value pairs within a range of keys from the B ε -tree, wherein the B ε -tree comprises a plurality of nodes comprising a root node, a plurality of branch nodes, and a plurality of leaf nodes, wherein the root node and each node of the plurality of branch nodes is associated with a buffer that stores one or more key-value pairs;
obtaining from within one or more buffers of one or more nodes of at least one level of the B ε -tree, a set of key-value pairs within the range of keys up to a size equal to a size limit, the set of key value pairs comprising less than all key-value pairs within the range of keys stored in the B ε -tree;
transferring the set of key-value pairs to a result data structure;
after the transferring the set of key-value pairs, sorting all key-value pairs in the result data structure;
after the transferring the set of key-value pairs, merging all key value pairs in the result data structure for at least one key of the range of keys;
after the merging, determining that at least one key-value pair for the at least one key remains in the one or more buffers of the one or more nodes of the at least one level;
after the determining, obtaining from within the one or more buffers of the one or more nodes of the at least one level one or more additional key-value pairs within the range of keys;
transferring the one or more additional key-value pairs to the result data structure;
after the transferring the one or more additional key value pairs, sorting all key-value pairs in the result data structure;
after the transferring the one or more additional key value pairs, merging all key value pairs in the result data structure for the at least one key of the range of keys; and
returning the result data structure in response to the request.

2. The method of claim 1 , wherein the result data structure is one of a B-tree or an array.

3. The method of claim 1 , further comprising determining the size limit by dividing the range of keys into a plurality of sections based on a number of key-value pairs that fit within a system memory, wherein the size limit is a size of a section of the plurality of sections.

4. The method of claim 1 , wherein the B ε -tree is locked during performing a range lookup to prevent modifications of the B ε -tree.

5. The method of claim 1 , wherein obtaining the set of key-value pairs comprises:
determining a first key-value pair within the one or more buffers of the one or more nodes associated with a particular key of the range of keys is one of:
a delete message;
an insert message; or
a modification of a value associated with the particular key to a fixed value; and

not including in the set of key-value pairs any key-value pairs associated with the particular key having an earlier ordering than the first key-value pair.

6. The method of claim 1 , further comprising:
storing an indicator in the result data structure indicating key-value pairs within the range of keys have not been fully transferred from the at least one level.

7. The method of claim 6 , wherein determining that at least one key-value pair for the at least one key remains in the one or more buffers of the one or more nodes of the at least one level comprises:
determining that the indicator is stored within the result data structure associated with a first key-value pair of the at least one key-value pair.

8. A computer system, wherein system software for the computer system is programmed to execute a method for performing a range lookup in a B ε -tree, the method comprising:
receiving a request to return key-value pairs within a range of keys from the B ε -tree, wherein the B ε -tree comprises a plurality of nodes comprising a root node, a plurality of branch nodes, and a plurality of leaf nodes, wherein the root node and each node of the plurality of branch nodes is associated with a buffer that stores one or more key-value pairs;
obtaining from within one or more buffers of one or more nodes of at least one level of the B ε -tree, a set of key-value pairs within the range of keys up to a size equal to a size limit, the set of key value pairs comprising less than all key-value pairs within the range of keys stored in the B ε -tree;
transferring the set of key-value pairs to a result data structure;
after the transferring the set of key-value pairs, sorting all key-value pairs in the result data structure;
after the transferring the set of key-value pairs, merging all key value pairs in the result data structure for at least one key of the range of keys;
after the merging, determining that at least one key-value pair for the at least one key remains in the one or more buffers of the one or more nodes of the at least one level;
after the determining, obtaining from within the one or more buffers of the one or more nodes of the at least one level one or more additional key-value pairs within the range of keys;
transferring the one or more additional key-value pairs to the result data structure;
after the transferring the one or more additional key value pairs, sorting all key-value pairs in the result data structure;
after the transferring the one or more additional key value pairs, merging all key value pairs in the result data structure for the at least one key of the range of keys; and
returning the result data structure in response to the request.

9. The computer system of claim 8 , wherein the result data structure is one of a B-tree or an array.

10. The computer system of claim 8 , wherein the method further comprises determining the size limit by dividing the range of keys into a plurality of sections based on a number of key-value pairs that fit within a system memory, wherein the size limit is a size of a section of the plurality of sections.

11. The computer system of claim 8 , wherein the B ε -tree is locked during performing a range lookup to prevent modifications of the B ε -tree.

12. The computer system of claim 8 wherein obtaining the set of key-value pairs comprises:
determining a first key-value pair within the one or more buffers of the one or more nodes associated with a particular key of the range of keys is one of:
a delete message;
an insert message; or
a modification of a value associated with the particular key to a fixed value; and

not including in the set of key-value pairs any key-value pairs associated with the particular key having an earlier ordering than the first key-value pair.

13. The computer system of claim 8 , the method further comprising:
storing an indicator in the result data structure indicating key-value pairs within the range of keys have not been fully transferred from the at least one level.

14. The computer system of claim 13 , wherein determining that at least one key-value pair for the at least one key remains in the one or more buffers of the one or more nodes of the at least one level comprises:
determining that the indicator is stored within the result data structure associated with a first key-value pair of the at least one key-value pair.

15. A non-transitory computer readable medium comprising instructions to be executed in a computer system, wherein the instructions when executed in the computer system cause the computer system to perform a method for performing a range lookup in a B ε -tree, the method comprising:
receiving a request to return key-value pairs within a range of keys from the B ε -tree, wherein the B ε -tree comprises a plurality of nodes comprising a root node, a plurality of branch nodes,

Assignees

• Vmware Inc

Inventors

• Gupta Abhishek
• Spillane Richard P
• Johnson Robert T
• Wang Wenguang
• Chowksey Kapil
• Guerra Delgado Jorge
• Rangaswamy Sandeep
• Premachandran Srinath

Classifications

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F7/16

  Combined merging and sorting · CPC title