Append-Only B-Tree Cursor

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.

What is claimed is: 
     
         1 . A method, comprising:
 receiving, by a controller, a data element for storage in a b-tree, 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;   storing, by the controller, the data element in a parent node of the first node;   associating, by the controller, a second node with the parent node; and   storing, by the controller, a subsequent data element in the second node.   
     
     
         2 . The method of  claim 1 , further comprising creating the second node prior to associating the second node with the parent node. 
     
     
         3 . The method of  claim 1 , further comprising determining that the parent node for the first node does not exist after determining that the first node is filled to capacity. 
     
     
         4 . The method of  claim 3 , further comprising creating the parent node in response to determining that the parent node does not exist. 
     
     
         5 . The method of  claim 1 , wherein the first node is filled to capacity with a plurality of ordered data elements. 
     
     
         6 . The method of  claim 1 , further comprising finalizing the b-tree after storing the subsequent data element in the second node. 
     
     
         7 . The method of  claim 6 , wherein finalizing comprises:
 building a balancing binary tree from data elements already inserted into the b-tree.   
     
     
         8 . The method of  claim 6 , further comprising undoing the finalizing. 
     
     
         9 . The method of  claim 8 , wherein undoing the finalizing comprises:
 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.   
     
     
         10 . The method of  claim 8 , further comprising adding an additional data element to the b-tree. 
     
     
         11 . A system, comprising:
 a memory; and   a controller configured to:
 receive a data element for storage in a b-tree, 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; 
 store the data element in a parent node of the first node; 
 associate a second node with the parent node; and 
 store a subsequent data element in the second node. 
   
     
     
         12 . The system of  claim 11 , wherein the controller is further configured to create the second node prior to associating the second node with the parent node. 
     
     
         13 . The system of  claim 11 , wherein the controller is further configured to determine that the parent node for the first node does not exist after determining that the first node is filled to capacity. 
     
     
         14 . The system of  claim 13 , wherein the controller is further configured to create the parent node in response to determining that the parent node does not exist. 
     
     
         15 . The system of  claim 11 , wherein the first node is filled to capacity with a plurality of ordered data elements. 
     
     
         16 . The system of  claim 11 , wherein the controller is further configured to finalize the b-tree after storing the subsequent data element in the second node. 
     
     
         17 . The system of  claim 16 , wherein the controller is configured to finalize by:
 building a balancing binary tree from data elements already inserted into the b-tree.   
     
     
         18 . The system of  claim 6 , further comprising undoing the finalizing. 
     
     
         19 . The system of  claim 18 , 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.   
     
     
         20 . 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 b-tree, 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;   storing the data element in a parent node of the first node;   associating a second node with the parent node; and   storing a subsequent data element in the second node.