Dynamic preconditioning of A B+tree
View Patent ↗Various approaches for processing a B+tree data structure of a database are disclosed. In one approach a method determines 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, the method generates a plurality of new multi-column key values based on the pattern and stores one or more of the plurality of multi-column key values in one or more new index pages. Before performing the insert, the method further commits to retentive storage of the one or more new index pages and new data pages as linked to the B+tree. After committing the one or more new index pages and new data pages, the method then proceeds to processes and commits the insert transaction.
1. 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.
2. The method of claim 1 , wherein the determining the pattern of multi-column key values includes determining whether a left side of each multi-column key value is constant for a plurality of successive data records in the database, and responsive to the left side of each multi-column key value being constant for a plurality of successive data records in the database, the generating of the plurality of new multi-column key values includes using equal values for the left sides of the plurality of new multi-column key values.
3. The method of claim 2 , wherein the equal values for the left sides of the plurality of new multi-column key values are equal to the left sides of the multi-column key values of the successive data records in the database.
4. The method of claim 2 , wherein the equal values for the left sides of the plurality of new multi-column key values are equal to a value that succeeds the left side the multi-column key value of the last record in the database.
5. The method of claim 2 , wherein the pattern of multi-column key values is determined to have right sides of multi-column key values that change sequentially for a plurality of successive data records in the database, and the generating of the plurality of new multi-column key values includes generating right sides of the plurality of new multi-column key values, wherein the right sides of each successive pair of new multi-column key values covers a sequential range of right sides of the new multi-column key values.
6. The method of claim 2 , wherein the pattern of multi-column key values is determined to have right sides of multi-column key values that do not change sequentially for a plurality of successive data records in the database, and the generating of the plurality of new multi-column key values includes copying a plurality of right sides of multi-column key values from a plurality of successive index records that includes the last index record in the database to the right sides of the plurality of new multi-column key values.
7. The method of claim 1 , wherein the plurality of new multi-column key values is equal to a maximum number of index records that the new index page can store.
8. The method of claim 1 , wherein the B+tree has a plurality of levels of index pages and index pages at the first level reference data pages and index pages at a second level reference index pages at the first level, the method further comprising:
storing one of the plurality of new multi-column key values per each new index page at the first level; and
storing the plurality of new multi-column key values in one or more index pages at the second level.
9. The method of claim 1 , wherein the B+tree has a plurality of levels of index pages and index pages at the first level reference data pages and index pages at a second level reference index pages at the first level, the method further comprising:
storing a random number of the plurality of new multi-column key values per each new index page at the first level; and
storing the plurality of new multi-column key values in one or more index pages at the second level.
10. The method of claim 1 , wherein the B+tree has a plurality of levels of index pages and index pages at the first level reference data pages and index pages at a second level reference index pages at the first level, the method further comprising:
storing one of the plurality of new multi-column key values per each new index page at the first level;
storing the plurality of new multi-column key values in one or more index pages at the second level; and
wherein each new index page above index pages at the first level has empty space available for new index records.
11. 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 a pattern of multi-column key values from column data types and multi-column key values in the database, wherein the plurality of new multi-column key values is equal to a maximum number of index records that the new index page can store;
in response to an insert transaction into the database that requires a new index page and before performing the insert transaction, the processor:
obtains one or more new index pages;
generates a plurality of new multi-column key values based on the pattern;
stores the new multi-column key values in the new index pages;
obtains one or more new data pages;
stores in the one or more new index pages in association with each of the plurality of multi-column key values, references to respective ones of the one or more new data pages, and links the one or more new index pages in the B+tree data structure; and
commits 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, the processor:
stores data specified in the insert transaction to one of the new data pages; and
commits the one of the new data pages to retentive storage after storing the data in the one of the new data pages.
12. 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 B+tree has a plurality of levels of index pages and index pages at the first level reference data pages and index pages at a second level reference index pages at the first level;
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 a pattern of multi-column key values from column data types and multi-column key values in the database;
in response to an insert transaction into the database that requires a new index page and before performing the insert transaction, the processor:
obtains one or more new index pages;
generates a plurality of new multi-column key values based on the pattern;
stores the new multi-column key values in the new index pages;
obtains one or more new data pages;
stores in the one or more new index pages in association with each of the plurality of multi-column key values, references to respective ones of the one or more new data pages, and links the one or more new index pages in the B+tree data structure;
stores a random number of the plurality of new multi-column key values per each new index page at the first level;
stores the plurality of new multi-column key values in one or more index pages at the second level; and
commits 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, the processor:
stores data specified in the insert transaction to one of the new data pages; and
commits the one of the new data pages to retentive storage after storing the data in the one of the new data pages.