Dynamic preconditioning of a b+ tree

Abstract

Various approaches for processing a B+ tree data structure are described. In one approach, in a first transaction a first insert operation to a first data page of a first index page in the B+ tree data structure is detected, and then it is determined whether performing the first insert operation would block a second insert operation in a second transaction concurrent with the first transaction. At least one empty second data page is created in response to determining that the second insert operation would be blocked by the first insert operation. The B+ tree data structure is updated to include the at least one second data page in the B+ tree data structure, and the updated index pages and second data page are committed to retentive storage. Thereafter, the first insert can be completed.

1 . A processor-implemented method for processing a B+ tree data structure for data records of a database, comprising:
 detecting in a first transaction a first insert operation to a first data page of a first index page in the B+ tree data structure;   
       determining whether performing the first insert operation would block a second insert operation in a second transaction concurrent with the first transaction, wherein said determining includes determining whether a first set of conditions is present, the first set of conditions being that the database is defined with a multi-column key, data records are added in key-sequential order to the database relative to the multi-column key, and the first data page is the only data page referenced by the first index page, and in response to the first set of conditions being present
   determining a number of a plurality of divisions defined by the multi-column key;   creating a respective index page for each of the divisions;   creating as the at least one empty second data page a respective plurality of empty data pages for each of the divisions;   updating each respective index page with references to the respective plurality of empty data pages of a division corresponding to the index page   updating the first index page with references to the respective index pages for each of the divisions; and   committing the updated first index page, the respective index pages for the divisions, and the respective pluralities of empty data pages for the divisions to retentive storage;   
 creating at least one empty second data page in response to determining that the second insert operation would be blocked by the first insert operation; 
 updating one or more index pages in the B+ tree data structure to include the at least one second data page in the B+ tree data structure; 
 committing the updated one or more index pages and at least one second data page to retentive storage; 
 writing data specified in the first transaction to the first data page after committing the one or more index pages; and 
 committing the first data page to retentive storage after writing the data to the first data page. 
 
     
     
         2 . The method of  claim 1 , wherein the determining step includes determining whether a second set of conditions is present, the second set of conditions being that the database is defined with a multi-column key, data records are added in key-sequential order to the database relative to the multi-column key, and the first data page is a last data page of a division, and in response to the second set of conditions being present
 creating as the at least one empty second data page a plurality of empty data pages;   creating a new second index page and a new third index page;   updating the second index page with references to the plurality of empty data pages;   updating the third index page with references to the first index page and the second index page; and   committing the plurality of empty data pages and the second and third index pages to retentive storage.   
     
     
         3 . The method of  claim 2 , wherein each data page is limited to storage of one data record. 
     
     
         4 . An apparatus for processing database operations, comprising:
 means for establishing a B+ tree data structure in a memory for data records of a database;   means for determining whether performing a first insert operation to a first data page of a first index page of the B+ tree data structure would block a second insert operation in a second transaction concurrent with the first transaction;   means for allocating at least one empty second data page in response to determining that the second insert operation would be blocked by the first insert operation;   means for modifying one or more index pages in the B+ tree data structure to include the at least one second data page in the B+ tree data structure;   means for committing the modified one or more index pages and the at least one second data page to retentive storage;   means for modifying a first data page with data specified in the first transaction after committing the one or more index pages; and   means for committing the first data page to retentive storage after writing the data to the first data page.   
     
     
         5 . A database management system, comprising:
 a processor arrangement;   a memory coupled to the processor arrangement, the memory configured with instructions executable by the processor arrangement for processing a B+ tree data structure for data records of a database;   a mass storage arrangement coupled to the memory for retentive storage of the B+ tree data structure;   wherein the processor arrangement, in executing the instructions,
 determines whether performing a first insert operation in a first transaction to a first data page of a first index page would block a second insert operation in a second transaction concurrent with the first transaction, 
 generates at least one empty second data page in response to determining that the second insert operation would be blocked by the first insert operation, 
 links one or more index pages in the B+ tree data structure to the at least one second data page in the B+ tree data structure, 
 commits the one or more index pages and at least one second data page to the mass storage arrangement, 
 writes data specified in the first transaction to a first data page after committing the one or more index pages, and 
 commits the first data page to the mass storage arrangement after writing the data to the first data page. 
   
     
     
         6 . The system of  claim 5 , wherein each data page is limited to storage of one data record. 
     
     
         7 . The system of  claim 5 , wherein the processor arrangement, in executing the instructions, determines whether a first set of conditions is present, the first set of conditions being that the database is defined with a multi-column key, data records are added sequentially to the database relative to the multi-column key, and the first data page is the only data page referenced by the first index page, and in response to the first set of conditions being present, the instructions cause the processor arrangement to
 determine a number of a plurality of divisions defined by the multi-column key;   allocate a respective index page for each of the divisions;   allocate a respective plurality of empty data pages for each of the divisions;   update each respective index page with references to the respective plurality of empty data pages of a division corresponding to the index page;   update the first index page with references to the respective index pages for each of the divisions; and   commit the updated first index page, the respective index pages for the divisions, and the respective pluralities of empty data pages for the divisions to the mass storage arrangement.   
     
     
         8 . The system of  claim 7 , wherein the processor arrangement, in executing the instructions, determines whether a second set of conditions is present, the second set of conditions being that the database is defined with a multi-column key, data records are added in key-sequential order to the database relative to the multi-column key, and the first data page is a last data page of a division, and in response to the second set of conditions being present, the instructions cause the processor arrangement to
 allocate a plurality of empty data pages;   allocate a new second index page and a new third index page;   update the second index page with references to the plurality of empty data pages;   update the third index page with references to the first index page and the second index page; and   commit the plurality of empty data pages and the second and third index pages to the mass storage arrangement.   
     
     
         9 . The system of  claim 8 , wherein each data page is limited to storage of one data record.