Index B-tree maintenance for linear sequential insertion

Patent metadata

Field	Value
Publication number	US-10664460-B2
Application number	US-201715811742-A
Country	US
Kind code	B2
Filing date	Nov 14, 2017
Priority date	Jul 29, 2016
Publication date	May 26, 2020
Grant date	May 26, 2020

Abstract

An approach for index B-tree page creation associated with linear sequential insertions in database management systems (DBMS). A linear pre-splitter receives a current index leaf page for linear sequential insertion. The linear pre-splitter asynchronously creates index leaf pages where the current index leaf page is in a predetermined position at least one page away from a last index leaf page. The linear pre-splitter updates index leaf page position identifiers associated with the index leaf pages where the index leaf page position identifiers link the index leaf pages and the last index leaf page and the linear pre-splitter inserts index leaf page identifiers and index key metadata associated with each of the index leaf pages into index non-leaf pages.

First claim

What is claimed is:

1. A method for index B-tree page creation associated with linear sequential insertions in database management systems (DBMS), the method comprising:
receiving, by a linear pre-splitter, a current index leaf page for linear sequential insertion;
asynchronously creating, by the linear pre-splitter, one or more index leaf pages wherein the current index leaf page is in a predetermined position at least one page away from a last index leaf page, without transferring data from existing leaf pages to the created one or more index leaf pages during the linear sequential insertion;
updating, by the linear pre-splitter, one or more index leaf page position identifiers associated with the one or more index leaf pages wherein the one or more index leaf page position identifiers link the one or more index leaf pages and the last index leaf page; and
inserting, by the linear pre-splitter, one or more index leaf page identifiers and index key metadata associated with each of the one or more index leaf pages into one or more index non-leaf pages.

2. The method of claim 1 , further comprising:
detecting, by the linear pre-splitter, the linear sequential insertion wherein the linear sequential insertion is based on identifying at least one of a predetermined column index definition and a DBMS insert operation.

3. The method of claim 1 , wherein, the index key metadata comprises at least one of a high key and a low key associated with a respective minimal key value and a maximal key value of each of the one or more index leaf pages.

4. The method of claim 1 , wherein asynchronously creating the one or more index leaf pages is based on at least one of a predetermined quantity of the one or more index leaf pages and determining the quantity of the one or more index leaf pages based a quantity of B-Tree leaves inserts.

5. The method of claim 4 , wherein determining the quantity of the one or more index leaf pages is based on receiving the quantity of B-Tree leaves inserts and calculating a quantity of the one or more index leaf pages comprising a quantity of B-Tree leaves.

6. The method of claim 1 , wherein the predetermined position at least one page away from a last index leaf page is based on determining a position of the current index leaf page and a position of the last index leaf page.

7. The method of claim 1 , wherein each of the one or more index leaf pages comprise an index leaf page identifier and the one or more index leaf page position identifiers.

Assignees

• IBM

Inventors

• Fang Min
• Jin Di
• Shi zhen yu
• Slinger Nigel G
• Wang Shu
• Zheng li fei
• Zhu wen jie

Classifications

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title