Patent ID: 7941451

Claim:
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 storing one data record, of a first index page in the B+ tree data structure, wherein the first insert operation references a right-most data page of the first index page, and the determining step includes determining whether a first set of conditions is present, the first set of conditions being that data records are added in key-sequential order to the database under the first index page 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 whether performing the first insert operation would block a second insert operation in a second transaction concurrent with the first transaction; creating at least one empty second data page storing one data record 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; committing the first data page to retentive storage after writing the data to the first data page; creating as the at least one empty second data page a plurality of empty data pages; updating the first index page with references to the plurality of empty data pages; and committing the plurality of empty data pages and the updated first index page to retentive storage.