Database index modification

Patent metadata

Field	Value
Publication number	US-11645254-B2
Application number	US-202117448882-A
Country	US
Kind code	B2
Filing date	Sep 25, 2021
Priority date	Sep 25, 2021
Publication date	May 9, 2023
Grant date	May 9, 2023

Abstract

Modifying an index for a database is provided. An index tree for the database is traversed by: identifying a next node in the index tree, requesting a lock of the next node in the index tree, responsive to locking of the next node in the index tree, releasing a lock of a current node of the index tree, and making the next node in the index tree the current node of the index tree, until the current node of the index tree is a leaf node of the index tree. Responsive to determining to split the leaf node, the lock of the leaf node is released and, after releasing the lock of the leaf node, a lock of a non-leaf node parent of the leaf node in the index tree is requested.

First claim

What is claimed is:

1. A computer-implemented method of modifying an index for a database, comprising:
(A) traversing, by a process operating on a computer, an index tree for the database, by:
(A.1) identifying a next node in the index tree,
(A.2) preventing other processes from changing the next node by requesting a lock of the next node in the index tree,
(A.3) responsive to locking of the next node in the index tree, allowing other processes to change a current node of the index tree by releasing a lock of the current node,
(A.4) responsive to releasing the lock of the current node, making the next node in the index tree the current node of the index tree,
(A.5) responsive to making the next node the current node, determining whether the current node of the index tree is a leaf node of the index tree, and
(A.6) responsive to the process determining that the current node of the index tree is not a leaf node, repeating steps (A.1) through (A.6);

(B) responsive to the process determining that the current node of the index tree is the leaf node, determining, by the process, whether to split the leaf node;
(C) responsive to the process determining to split the leaf node, splitting the leaf node, by the process, by:
(C.1) allowing other processes to change the leaf node by releasing the lock of the leaf node,
(C.2) after releasing the lock of the leaf node, preventing other processes from changing a non-leaf node parent of the leaf node in the index tree by requesting a lock of the non-leaf node parent of the leaf node in the index tree,
(C.3) after obtaining the lock of the non-leaf node parent of the leaf node, splitting the leaf node, and
(C.4) after splitting the leaf node, allowing other processes to change the non-leaf node parent of the leaf node by releasing the lock of the non-leaf node parent of the leaf node; and

(D) using the index, by a computer process, to access the database,
wherein traversing the index tree for the database further comprises adding, by the process, node information for the current node to a footprint stack,
wherein the node information added to the footprint stack includes node information for the current node selected from:
a page buffer of the current node;
a page free size of the current node; and
a page modified timestamp indicating a last time that the current node was changed,
wherein the method further comprises, before requesting the lock of the non-leaf node parent of the leaf node in the index tree:
determining, by the process, using the page modified timestamp in the footprint stack for the non-leaf node parent of the leaf node, whether the non-leaf node parent of the leaf node has changed; and
responsive to determining, by the process, that the non-leaf node parent of the leaf node has changed, re-traversing, by the process, the index tree for the database starting at the non-leaf node parent of the leaf node.

2. The computer-implemented method of claim 1 further comprising identifying, by the process, the non-leaf node parent of the leaf node from the footprint stack.

3. The computer-implemented method of claim 1 , wherein the database is a distributed database with data shared by a plurality of databases, and further comprising using, by the process, node clusters to reduce contention against space map pages access when new pages are allocated.

4. The computer-implemented method of claim 1 , wherein the database is a distributed database with data shared by a plurality of databases, wherein lock requests to lock nodes of index trees for the plurality of databases are stored in a lock waiting queue, and further comprising reprioritizing the lock requests in the lock waiting queue so that the lock requests to lock nodes of an index tree for a database in the plurality of databases are processed together in a batch operation.

5. A computer for modifying an index for a database, comprising:
a bus system;
a storage device connected to the bus system, wherein the storage device stores program instructions; and
a processor connected to the bus system, wherein the processor executes the program instructions to cause a process to:
(A) traverse an index tree for the database, by:
(A.1) identifying a next node in the index tree,
(A.2) requesting a lock of the next node in the index tree,
(A.3) responsive to locking of the next node in the index tree, releasing a lock of a current node of the index tree,
(A.4) responsive to releasing the lock of the current node of the index tree, making the next node in the index tree the current node of the index tree,
(A.5) responsive to making the next node the current node, determining whether the current node of the index tree is a leaf node of the index tree, and
(A.6) responsive to determining that the current node of the index tree is not a leaf node, repeating steps (A.1) through (A.6);

(B) responsive to determining that the current node of the index tree is the leaf node, determine whether to split the leaf node;
(C) responsive to determining to split the leaf node, split the leaf node by:
(C.1) release the lock of the leaf node,
(C.2) after releasing the lock of the leaf node, request a lock of a non-leaf node parent of the leaf node in the index tree,
(C.3) after obtaining the lock of the non-leaf node parent of the leaf node, split the leaf node, and
(C.4) after splitting the leaf node, release the lock of the non-leaf node parent of the leaf node; and

(D) use the index to access the database,
wherein the processor executes the program instructions to cause the process to further add node information for the current node to a footprint stack,
wherein the node information added to the footprint stack includes node information for the current node selected from:
a page buffer of the current node;
a page free size of the current node; and
a page modified timestamp indicating a last time that the current node was changed,
wherein the determination of whether the non-leaf node parent has changed comprises causing the process to determine, using the page modified timestamp in the footprint stack for the non-leaf node parent of the leaf node, whether the non-leaf node parent of the leaf node has changed.

6. The computer of claim 5 , wherein the processor executes the program instructions to cause the process to identify the non-leaf node parent of the leaf node from the footprint stack.

7. The computer of claim 5 , wherein the database is a distributed database with data shared by a plurality of databases, and wherein the processor executes the program instructions to cause the process to further use node clusters to reduce contention against space map pages access when new pages are allocated.

8. The computer of claim 5 , wherein the database is a distributed database with data shared by a plurality of databases, wherein lock requests to lock nodes of index trees for the plurality of databases are stored in a lock waiting queue, and wherein the processor executes the program instructions to cause the process to reprioritize the lock requests in the lock waiting queue so that the lock requests to lock nodes of an index tree for a database in the plurality of databases are processed together in a batch operation.

9. A computer program product for modifying an index for a database, the computer program product comprising a computer-readable storage medium having program instructions embodied therewith, the program instructions executable by a process operating on a computer to cause the process to perform a method of:
(A) traversing an index tree for the database, by:
(A.1) identifying a next node in the index tree,
(A.2) requesting a lock of the next node in the index tree,
(A.3) responsive to loc

Assignees

• IBM

Inventors

• Li Shuo
• Wang Xiaobo
• Sun sheng yan
• Zhang Hong Mei
• Wan Meng

Classifications

• G06F16/2246 Primary

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

• G06F16/182

  Distributed file systems · CPC title

• G06F16/2228 Primary

  Indexing structures · CPC title