Tuning key space at the time of instantiation of a tree data structure

Patent metadata

Field	Value
Publication number	US-10262016-B2
Application number	US-201514869099-A
Country	US
Kind code	B2
Filing date	Sep 29, 2015
Priority date	Sep 29, 2015
Publication date	Apr 16, 2019
Grant date	Apr 16, 2019

Abstract

Techniques for tuning the key space of an instance of a tree data structure are provided. In one embodiment, a computer system can receive a request to create the instance, where the request includes an expected key space value indicating an expected range of key values to be addressed by the instance. The computer system can further calculate a number of bits to allocate to each key of each node of the instance based on the expected key space value. The computer system can then, at a time of instantiating each node of the instance, allocate the keys for the node in accordance with the calculated number of bits.

First claim

What is claimed is:

1. A method for tuning a key space of an instance of a tree data structure, the method comprising:
receiving, by a computer system from an application running on the computer system, an invocation of an application programming interface (API) for creating the instance of the tree data structure in a memory of the computer system, the invocation of the API including an expected key space value indicating an expected range of key values needed by the application in view of the application's expected use of the instance of the tree data structure; and
in response to the invocation of the API:
calculating, by the computer system, a number of bits to allocate to each key of each node of the instance based on the expected key space value; and
instantiating, by the computer system, the instance of the tree data structure in the memory of the computer system, wherein the instantiating includes, at a time of instantiating each node of the instance, allocating a portion of the memory of the computer system to each key of the node, wherein the allocated memory portion has a size equaling the calculated number of bits.

2. The method of claim 1 wherein the expected key space value is less than a maximum possible key space supported or allowed by the application.

3. The method of claim 1 wherein calculating the number of bits to allocate to each key of each node comprises computing the logarithm in base 2 of the expected key space value.

4. The method of claim 1 wherein the tree data structure is a B+ tree.

5. The method of claim 1 further comprising:
receiving a request to extend the key space of the instance by an extension value;
creating a second instance of the tree data structure having a key space that covers a range of key values from zero to the extension value; and
chaining the second instance to the instance, such that tree operations associated with keys in a range between the expected key space value and the extension value are directed to the second instance.

6. The method of claim 5 further comprising:
receiving a request to reduce the key space of the instance back to the expected key space value; and
deleting the second instance of the tree data structure.

7. A non-transitory computer readable storage medium having stored thereon program code executable by a computer system, the program code embodying a method for tuning a key space of an instance of a tree data structure, the method comprising:
receiving, from an application running on the computer system, an invocation of an application programming interface (API) for creating the instance of the tree data structure in a memory of the computer system, the invocation of the API including an expected key space value indicating an expected range of key values needed by the application in view of the application's expected use of the instance of the tree data structure; and
in response to the invocation of the API:
calculating a number of bits to allocate to each key of each node of the instance based on the expected key space value; and
instantiating the instance of the tree data structure in the memory of the computer system, wherein the instantiating includes, at a time of instantiating each node of the instance, allocating a portion of the memory of the computer system to each key of the node, wherein the allocated memory portion has a size equaling the calculated number of bits.

8. The non-transitory computer readable storage medium of claim 7 wherein the expected key space value is less than a maximum possible key space supported or allowed by the application.

9. The non-transitory computer readable storage medium of claim 7 wherein calculating the number of bits to allocate to each key of each node comprises computing the logarithm in base 2 of the expected key space value.

10. The non-transitory computer readable storage medium of claim 7 wherein the tree data structure is a B+ tree.

11. The non-transitory computer readable storage medium of claim 7 wherein the method further comprises:
receiving a request to extend the key space of the instance by an extension value;
creating a second instance of the tree data structure having a key space that covers a range of key values from zero to the extension value; and
chaining the second instance to the instance, such that tree operations associated with keys in a range between the expected key space value and the extension value are directed to the second instance.

12. The non-transitory computer readable storage medium of claim 11 wherein the method further comprises:
receiving a request to reduce the key space of the instance back to the expected key space value; and
deleting the second instance of the tree data structure.

13. A computer system comprising:
a memory;
a processor; and
a non-transitory computer readable medium having stored thereon program code for tuning a key space of an instance of a tree data structure, the program code causing the processor to:
receive, from an application running on the computer system, an invocation of an application programming interface (API) for creating the instance of the tree data structure in the memory of the computer system, the invocation of the API including an expected key space value indicating an expected range of key values needed by the application in view of the application's expected use of the instance of the tree data structure; and
in response to the invocation of the API:
calculate a number of bits to allocate to each key of each node of the instance based on the expected key space value; and
instantiate the instance of the tree data structure in the memory of the computer system, wherein the instantiating includes, at a time of instantiating each node of the instance, allocating a portion of the memory of the computer system to each key of the node, wherein the allocated memory portion has a size equaling the calculated number of bits.

14. The computer system of claim 13 wherein the expected key space value is less than a maximum possible key space supported or allowed by the application.

15. The computer system of claim 13 wherein calculating the number of bits to allocate to each key of each node comprises computing the logarithm in base 2 of the expected key space value.

16. The computer system of claim 13 wherein the tree data structure is a B+ tree.

17. The computer system of claim 13 wherein the program code further causes the processor to:
receive a request to extend the key space of the instance by an extension value;
create a second instance of the tree data structure having a key space that covers a range of key values from zero to the extension value; and
chain the second instance to the instance, such that tree operations associated with keys in a range between the expected key space value and the extension value are directed to the second instance.

18. The computer system of claim 17 wherein the program code further causes the processor to:
receive a request to reduce the key space of the instance back to the expected key space value; and
delete the second instance of the tree data structure.

Assignees

• Vmware Inc

Inventors

• Shukla Ritesh
• Pashenkov Serge
• Ding Li
• Needle Bret
• Rawat Mayank

Classifications

• G06F16/2246 Primary

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

• G06F17/30327 Primary

  Physics · mapped topic