Algorithm for tree traversals using left links

• US 20060026188A1
• Filed: 09/01/2005
• Published: 02/02/2006
• Est. Priority Date: 12/02/2002
• Status: Active Grant

• Current Assignee: Callahan Cellular LLC (Intellectual Ventures LLC)
• Original Assignee: Microsoft Corporation
• Inventors: Najork, Marc A., Thekkath, Chandramohan A.
• Granted Patent: US 7,082,438 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: Y10S 707/918 Location
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

An information management system includes a computer and a database comprising a B-Tree data structure comprising a plurality of nodes associated with disk blocks and handles stored in the nodes. At least one left-link handle, h_left, stored in each node points to a left sibling of that node. A mechanism for performing a lookup operation with respect to a key, k, traverses the B-Tree and refers to the left-link handle, h_left, of a node to access a left sibling of the node if the key k is less than or equal to a value k_min stored in the node. Mechanisms are also provided for performing insert and delete operations, and the lookup, insert, and delete operations detect if the key range of an index node, A, does not include the key k that the operation is trying to locate, and follow a handle A.h_left to the left sibling when k≦A.k_min.

Claims

1. An information management system, comprising:

a computer; and

a database operatively connected to said computer, wherein said database comprises a B-Tree data structure comprising a plurality of nodes associated with disk blocks and handles stored in said nodes, wherein at least one left-link handle stored in each of said plurality of nodes points to a left sibling of that node.

2. An information management system as recited in claim 1, further comprising a computer implemented mechanism for performing a lookup operation with respect to a key, k.

3. An information management system as recited in claim 2, wherein, in traversing the B-Tree at a given node, said lookup operation refers to a left-link handle, h_left, of that node to access a left sibling of the node if the key k is less than or equal to a value k_min stored in the node.

4. An information management system as recited in claim 2, further comprising a mechanism for performing an insert operation.

5. An information management system as recited in claim 4, wherein the insert operation detects if the key range of an index node, A, does not include the key k that the operation is trying to locate, and wherein said operation follows a handle A.h_left to the left sibling when k≦

A.k_min.

6. An information management system as recited in claim 1, further comprising a mechanism for performing a delete operation.

7. An information management system as recited in claim 6, wherein the delete operation detects if the key range of an index node, A, does not include the key k that the operation is trying to locate, and wherein said operation follows a handle A.h_left to the left sibling when k≦

A.k_min.

8. An information management system as recited in claim 2, further comprising mechanisms for performing insert and delete operations, wherein said lookup, insert and delete operations detect if the key range of an index node, A, does not include the key k that the operation is trying to locate, and wherein said operations follow a handle A.h_left to the left sibling when k≦

A.k_min.

9. An information management system as recited in claim 1, wherein the B-Tree data structure comprises at least one index node having the following structure:

<

h_left, k_min, h₀, k₀, h₁, k₁, . . . , h_n-1, k_n-1, h_n, k_max, h_right>

wherein h_left is a handle of a left sibling and the remaining data elements (k_min, h₀, k₀, h₁, k₁, . . . , h_n-1, k_n-1, h_n, k_max, h_right) are handles and keys according to a B-Link Tree data structure.

10. A B-Tree data structure stored on a computer readable medium, comprising a plurality of nodes associated with disk blocks and handles stored in said nodes, wherein at least one left-link handle stored in each node points to a left sibling of that node.

11. A data structure as recited in claim 10, comprising at least one index node having the following structure:

<

h_left, k_min, h₀, k₀, h₁, k₁, . . . , h_n-1, k_n-1, h_n, k_max, h_right>

wherein h_left is a left-link handle of a left sibling and the remaining data elements (k_min, h₀, k₀, h₁, k₁, . . . , h_n-1, k_n-1, h_n, k_max, h_right) are handles and keys according to a B-Link Tree data structure.

12. A computer-implemented method, comprising maintaining, in a computer readable medium, a data structure comprising a plurality of nodes and handles stored in said nodes, wherein at least one left-link handle stored in each of said plurality of nodes points to a left sibling of that node.

13. A method as recited in claim 12, wherein the method further comprises performing a lookup operation with respect to a key, k, wherein the lookup operation involves traversing the data structure and, at a given node, referring to a left-link handle, h_left of that node to access a left sibling of the node if the key k is less than or equal to a value k_min stored in the node.

14. A method as recited in claim 12, further comprising performing an insert operation.

15. A method as recited in claim 14, wherein the insert operation detects if the key range of an index node, A, does not include the key k that the operation is trying to locate, and wherein said operation follows a handle A.h_left to the left sibling when k≦

A.k_min.

16. A method as recited in claim 12, further comprising a mechanism for performing a delete operation.

17. A method as recited in claim 16, wherein the delete operation detects if the key range of an index node, A, does not include the key k that the operation is trying to locate, and wherein said operation follows a handle A.h_left to the left sibling when k≦

A.k_min.

18. A method as recited in claim 13, further comprising performing insert and delete operations, wherein said lookup, insert and delete operations detect if the key range of an index node, A, does not include the key k that the operation is trying to locate, and wherein said operations follow a handle A.h_left to the left sibling when k≦

A.k_min.

19. A method as recited in claim 12, wherein the data structure comprises at least one index node having the following structure:

<

h_left, k_min, h₀, k₀, h₁, k₁, . . . , h_n-1, k_n-1, h_n, k_max, h_right>

wherein h_left is a handle of a left sibling and the remaining data elements (k_min, h₀, k₀, h₁, k₁, . . . , h_n-1, k_n-1, h_n, k_max, h_right) are handles and keys according to a B-Link Tree data structure.