Patent ID: 7809759

Claim:
A processor-implemented method for processing a B+tree data structure of a database, comprising: determining a pattern of multi-column key values; in response to an insert transaction into the database that requires a new index page and before performing the insert transaction, performing the steps including: generating a plurality of new multi-column key values based on the pattern; storing one or more of the plurality of multi-column key values in one or more new index pages; linking each of the plurality of multi-column key values to a respective one of a plurality of new data pages, and linking the one or more new index pages and the new data pages to the B+tree data structure; and committing to retentive storage the one or more new index pages and new data pages; after committing the one or more new index pages and new data pages, performing the steps including: storing data specified in the insert transaction to one of the new data pages; and committing the one of the new data pages to retentive storage after storing the data in the one of the new data pages.