Enhanced B-Trees with Record Merging

Abstract

In some implementations, a B+tree (b plus tree) can provide concurrent access to data while modifying nodes of the B+tree. In some implementations, a top-down B+tree can be provided where nodes of the B+tree can be proactively merged, rebalanced and split to prevent recursive operations moving up the B+tree. In some implementations, node (or page) record data can be merged to consolidate record entries within nodes of the B+tree while only locking 1-3 nodes of the tree at the same time. In some implementations, record data can be merged across multiple nodes of the B+tree. In some implementations, ranges of data can be removed from the tree while only locking 1-3 nodes of the tree at the same time. In some implementations, range of data can be replaced with new data while only locking 1-3 nodes of the tree at the same time.

What is claimed is:  
     
         1 . A method comprising:
 storing records in a B-tree data structure;   receiving a new record for insertion into the B-tree data structure;   in response to receiving the new record for insertion,
 traversing the B-tree based on a value of a key in the new record; 
 proactively merging, rebalancing, and splitting nodes while traversing the B-tree; and 
 inserting the new record in a leaf node of the B-tree by
 determining that the new record corresponds to the first or last record in the leaf node; 
 identifying an adjacent node; 
 determining that the new record can be merged with an existing record in the adjacent node; 
 identifying the closest common ancestor node of the leaf node and the adjacent node; 
 obtaining an exclusive lock on the closest common ancestor node, and the path of nodes leading to and including the leaf node, the adjacent node; and 
 merging the new record with the existing record. 
 
   
     
     
         2 - 9 . (canceled) 
     
     
         10 . A non-transitory computer-readable medium including one or more sequences of instructions which, when executed by one or more processors, cause the one or more processors to perform operations comprising:
 storing records in a B-tree data structure;   receiving a new record for insertion into the B-tree data structure;   in response to receiving the new record for insertion,
 traversing the B-tree based on a value of a key in the new record; 
 proactively merging, rebalancing, and splitting nodes while traversing the B-tree; and 
 inserting the new record in a leaf node of the B-tree by
 determining that the new record corresponds to the first or last record in the leaf node; 
 identifying an adjacent node; 
 determining that the new record can be merged with an existing record in the adjacent node; 
 identifying the closest common ancestor node of the leaf node and the adjacent node; 
 obtaining an exclusive lock on the closest common ancestor node, and the path of nodes leading to and including the leaf node, the adjacent node; and 
 merging the new record with the existing record. 
 
   
     
     
         11 - 18 . (canceled) 
     
     
         19 . A system comprising:
 one or more processors; and   a computer-readable medium including one or more sequences of instructions which, when executed by the one or more processors, cause the system to perform operations comprising:
 storing records in a B-tree data structure; 
 receiving a new record for insertion into the B-tree data structure; 
 in response to receiving the new record for insertion,
 traversing the B-tree based on a value of a key in the new record; 
 proactively merging, rebalancing, and splitting nodes while traversing the B-tree; and 
 inserting the new record in a leaf node of the B-tree by
 determining that the new record corresponds to the first or last record in the leaf node; 
 identifying an adjacent node; 
 determining that the new record can be merged with an existing record in the adjacent node; 
 identifying the closest common ancestor node of the leaf node and the adjacent node; 
 obtaining an exclusive lock on the closest common ancestor node, and the path of nodes leading to and including the leaf node, the adjacent node; and 
 merging the new record with the existing record. 
 
 
   
     
     
         20 - 27 . (canceled) 
     
     
         28 . The method of  claim 1 , further comprising starting the traversing of the B-tree data structure from a root of the B-tree data structure. 
     
     
         29 . The method of  claim 1 , wherein the identifying of the common closest ancestor comprises:
 analyzing each entry of a traversed interior node of the B-tree data structure; and   determining, based on the analyzing, whether the entry occupies a right most position in the traversed interior node.   
     
     
         30 . The method of  claim 1 , further comprising:
 mapping logical address to physical address for a file system based on the B-tree data structure, and   initiating the inserting of the new record when a storage location is allocated for a file of the file system.   
     
     
         31 . The non-transitory computer-readable medium of  claim 10 , wherein the operations further comprise starting the traversing of the B-tree data structure from a root of the B-tree data structure. 
     
     
         32 . The non-transitory computer-readable medium of  claim 10 , wherein the operation of identifying of the common closest ancestor comprises:
 analyzing each entry of a traversed interior node of the B-tree data structure; and   determining, based on the analyzing, whether the entry occupies a right most position in the traversed interior node.   
     
     
         33 . The non-transitory computer-readable medium of  claim 10 , wherein the operations further comprise:
 mapping logical address to physical address for a file system based on the B-tree data structure, and   initiating the inserting of the new record when a storage location is allocated for a file of the file system.   
     
     
         34 . The system of  claim 19 , wherein the operations further comprise starting the traversing of the B-tree data structure from a root of the B-tree data structure. 
     
     
         32 . The system of  claim 19 , wherein the operation of identifying of the common closest ancestor comprises:
 analyzing each entry of a traversed interior node of the B-tree data structure; and   determining, based on the analyzing, whether the entry occupies a right most position in the traversed interior node.   
     
     
         33 . The system of  claim 19 , wherein the operations further comprise:
 mapping logical address to physical address for a file system based on the B-tree data structure, and   initiating the inserting of the new record when a storage location is allocated for a file of the file system.