Granted Patent B1

US 7,941,451 · App. 11/506,224 · Granted May 10, 2011

Assignee: Unisys Corporation

Abstract

Claims (37)

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 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.

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 data records are added in key-sequential order to the database, and the first data page is a last data page referenced by the first index page, 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. 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 storing one data record, of a first index page would block a second insert operation in a second transaction concurrent with the first transaction, wherein the first insert operation references a right-most data page of the first index page, and the processor arrangement, in executing the instructions, determines 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 the instructions cause the processor arrangement to:

generates 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,

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,

commits the first data page to the mass storage arrangement after writing the data to the first data page;

allocates a plurality of empty data pages for the at least one empty second data page;

updates the first index page with references to the plurality of empty data pages;

commits the plurality of empty data pages and the updated first index page to retentive storage; and

writes the data specified in the first transaction to the first data page referenced by the first index page.

4. The system of claim 3 , wherein the processor arrangement, in executing the instructions, determines whether a second set of conditions is present, the second set of conditions being that data records are added in key sequential order to the database, and the first data page is a last data page referenced by the first index page, 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;

allocated 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.

Assignments (13)