Leveraging hierarchy in a tree data structure to dynamically allocate keys

Patent metadata

Field	Value
Publication number	US-10067966-B2
Application number	US-201514869024-A
Country	US
Kind code	B2
Filing date	Sep 29, 2015
Priority date	Sep 29, 2015
Publication date	Sep 4, 2018
Grant date	Sep 4, 2018

Abstract

Techniques for dynamically allocating keys in an instance of a tree data structure are provided. In one embodiment, a computer system can, at a time of instantiating each non-root node in the instance, determine a key space to be addressed by the non-root node, where the key space is based on a key subinterval in a parent node of the non-root node that is associated with a pointer to the non-root node. The computer system can further calculate a number of bits to allocate to each key of the non-root node in view of the determined key space. The computer system can then allocate the keys of the non-root node in accordance with the calculated number of bits.

First claim

What is claimed is:

1. A method for dynamically allocating keys in an instance of a tree data structure, the method comprising:
instantiating, by the computer system, a new non-root node for the instance of the tree data structure in a memory of the computer system, the instantiating including:
determining, by the computer system, a minimum key space to be addressed by the non-root node, the minimum key space being based on a key subinterval in a parent node of the non-root node in the instance that is associated with a pointer to the non-root node;
calculating, by the computer system, a number of bits to allocate to each key of a plurality of keys of the non-root node in view of the minimum key space; and
allocating, by the computer system, the plurality of keys of the non-root node in the memory of the computer system in accordance with the calculated number of bits.

2. The method of claim 1 wherein the minimum key space is less than a key space addressed by the parent node.

3. The method of claim 1 wherein calculating the number of bits to allocate to each key of the non-root node comprises:
determining a number of unique key values in the minimum key space; and
computing the logarithm in base 2 of the number of unique key values.

4. The method of claim 1 wherein the determining, the calculating, and the allocating are performed in a response to a node split operation that results in instantiation of the non-root node.

5. The method of claim 1 wherein the determining, the calculating, and the allocating are performed in response to a node merge operation that results in instantiation of the non-root node.

6. The method of claim 1 further comprising, at a time of executing a search for a particular key in the instance:
navigating to the non-root node;
determining a function to be applied to the key, wherein the function is capable of transforming the key into a format suitable for comparison with encoded key values of the non-root node;
applying the function to the key to generate a transformed key; and
comparing the transformed key with the encoded key values of the non-root node.

7. The method of claim 1 further comprising:
receiving an expected key space value for the instance of the tree data structure, the expected key space value indicating a key space to be addressed by the instance as a whole; and
allocating keys for a root node of the instance based on the expected key space value.

8. A non-transitory computer readable storage medium having stored thereon program code executable by a computer system, the program code embodying a method for dynamically allocating keys in an instance of a tree data structure, the method comprising:
instantiating a new non-root node for the instance of the tree data structure in a memory of the computer system, the instantiating including:
determining a minimum key space to be addressed by the non-root node, the minimum key space being based on a key subinterval in a parent node of the non-root node in the instance that is associated with a pointer to the non-root node;
calculating a number of bits to allocate to each key of a plurality of keys of the non-root node in view of the minimum key space; and

allocating the plurality of keys of the non-root node in the memory of the computer system in accordance with the calculated number of bits.

9. The non-transitory computer readable storage medium of claim 8 wherein the minimum key space is less than a key space addressed by the parent node.

10. The non-transitory computer readable storage medium of claim 8 wherein calculating the number of bits to allocate to each key of the non-root node comprises:
determining a number of unique key values in the minimum key space; and
computing the logarithm in base 2 of the number of unique key values.

11. The non-transitory computer readable storage medium of claim 8 wherein the determining, the calculating, and the allocating are performed in a response to a node split operation that results in instantiation of the non-root node.

12. The non-transitory computer readable storage medium of claim 8 wherein the determining, the calculating, and the allocating are performed in response to a node merge operation that results in instantiation of the non-root node.

13. The non-transitory computer readable storage medium of claim 8 wherein the method further comprises, at a time of executing a search for a particular key in the instance:
navigating to the non-root node;
determining a function to be applied to the key, wherein the function is capable of transforming the key into a format suitable for comparison with encoded key values of the non-root node;
applying the function to the key to generate a transformed key; and
comparing the transformed key with the encoded key values of the non-root node.

14. The non-transitory computer readable storage medium of claim 8 wherein the method further comprises:
receiving an expected key space value for the instance of the tree data structure, the expected key space value indicating a key space to be addressed by the instance as a whole; and
allocating keys for a root node of the instance based on the expected key space value.

15. A computer system comprising:
a processor; and
a non-transitory computer readable medium having stored thereon program code for dynamically allocating keys in an instance of a tree data structure, the program code causing the processor to:
instantiate a new non-root node for the instance of the tree data structure in a memory of the computer system, the instantiating including:
determining a minimum key space to be addressed by the non-root node, the minimum key space being based on a key subinterval in a parent node of the non-root node that is associated with a pointer to the non-root node;
calculating a number of bits to allocate to each key of a plurality of keys of the non-root node in view of the minimum key space; and
allocating the plurality of keys of the non-root node in the memory of the computer system in accordance with the calculated number of bits.

16. The computer system of claim 15 wherein the minimum key space is less than a key space addressed by the parent node.

17. The computer system of claim 15 wherein calculating the number of bits to allocate to each key of the non-root node comprises:
determining a number of unique key values in the minimum key space; and
computing the logarithm in base 2 of the number of unique key values.

18. The computer system of claim 15 wherein the determining, the calculating, and the allocating are performed in a response to a node split operation that results in instantiation of the non-root node.

19. The computer system of claim 15 wherein the determining, the calculating, and the allocating are performed in response to a node merge operation that results in instantiation of the non-root node.

20. The computer system of claim 15 wherein the program code further causes the processor to, at a time of executing a search for a particular key in the instance:
navigate to the non-root node;
determine a function to be applied to the key, wherein the function is capable of transforming the key into a format suitable for comparison with encoded key values of the non-root node;
apply the function to the key to generate a transformed key; and
compare the transformed key with the encoded key values of the non-root node.

21. The computer system of claim 15 wherein the program code further causes

Assignees

• Vmware Inc

Inventors

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

Classifications

• G06F16/9027

  Trees · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/2246 Primary

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

• G06F17/30961

  Physics · mapped topic

• G06F17/30958

  Physics · mapped topic