Append-only b-tree cursor

Patent metadata

Field	Value
Publication number	US-9594786-B2
Application number	US-201414155315-A
Country	US
Kind code	B2
Filing date	Jan 14, 2014
Priority date	Dec 26, 2013
Publication date	Mar 14, 2017
Grant date	Mar 14, 2017

Abstract

Existing algorithms to build balanced tree structures (“b-trees”) compare a data element (e.g., a key) to be inserted with the data elements that have already been inserted to find the correct position to insert the data element. Additionally, the algorithms balance and/or rebalance the b-tree when any individual node gets over-filled. As part of this balancing, data elements stored in the various nodes are moved to other nodes. These operations can incur both time and resource costs. We propose an algorithm to build a b-tree in a bottom up manner and a technique to modify trees built using the aforementioned algorithm so that they are balanced. We also propose a method to allow for adding more data into the thus-built b-tree as long as it follows a certain set of pre-conditions.

First claim

What is claimed is:

1. A method, comprising:
receiving, by a controller, a data element for storage in a memory comprising a b-tree structure, wherein the data element is part of an ordered set of data elements;
determining, by the controller, that a first node in the b-tree is filled to capacity and that a parent node of first node does not exist;
creating the parent node and a second node;
storing, by the controller, the data element in the parent node of the first node;
associating, by the controller, the second node with the parent node, wherein the parent node exists on a level above the first node in the b-tree; and
storing, by the controller, a subsequent data element in the second node.

2. The method of claim 1 , wherein the first node is filled to capacity with a plurality of ordered data elements.

3. The method of claim 1 , further comprising finalizing the b-tree after storing the subsequent data element in the second node.

4. The method of claim 3 , wherein finalizing comprises:
building a balancing binary tree from data elements already inserted into the b-tree.

5. The method of claim 3 , further comprising:
removing the data elements that form the balancing binary tree from the b-tree; and
re-inserting the data elements that form the balancing binary tree into the b-tree.

6. The method of claim 5 , further comprising adding an additional data element to the b-tree.

7. The method of claim 1 , further comprising:
receiving a second data element for storage in the b-tree;
creating a second child node associated with the parent node; and
storing the second data element in the second child node.

8. A system, comprising:
a memory; and
a controller configured to:
receive a data element for storage in the memory comprising a b-tree structure, wherein the data element is part of an ordered set of data elements;
determine that a first node in the b-tree is filled to capacity and that a parent node of first node does not exist;
create the parent node and a second node;
store the data element in the parent node of the first node;
associate the second node with the parent node, wherein the parent node exists on a level above the first node in the b-tree; and
store a subsequent data element in the second node.

9. The system of claim 8 , wherein the first node is filled to capacity with a plurality of ordered data elements.

10. The system of claim 8 , wherein the controller is further configured to finalize the b-tree after storing the subsequent data element in the second node.

11. The system of claim 10 , wherein the controller is configured to finalize by:
building a balancing binary tree from data elements already inserted into the b-tree.

12. The system of claim 3 , further comprising undoing the finalizing.

13. The system of claim 12 , wherein the controller is configured to undo the finalizing by:
removing the data elements that form the balancing binary tree from the b-tree; and
re-inserting the data elements that form the balancing binary tree into the b-tree.

14. A non-transitory computer readable medium containing computer instructions that, when executed by the computer, cause the computer to perform steps comprising:
receiving a data element for storage in a memory comprising a b-tree structure, wherein the data element is part of an ordered set of data elements;
determining that a first node in the b-tree is filled to capacity and that a parent node of first node does not exist;
creating the parent node and a second node;
storing the data element in the parent node of the first node;
associating the second node with the parent node, wherein the parent node exists on a level above the first node in the b-tree; and
storing a subsequent data element in the second node.

Assignees

• Marathe Nandan
• French Blaine
• Sybase Inc

Inventors

• Marathe Nandan
• French Blaine

Classifications

• G06F16/2246 Primary

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

• G06F16/9027

  Trees · CPC title

• G06F17/30327 Primary

  Physics · mapped topic

• G06F17/30961

  Physics · mapped topic