Index Locking and Splitting
Original Publication Date: 1982-Dec-01
Included in the Prior Art Database: 2005-Feb-10
This article describes a method for controlling read and write access to an index having leaf and non-leaf pages without requiring readers to obtain locks on non-leaf pages.
Index Locking and Splitting
This article describes a method for controlling read and write access to an index having leaf and non-leaf pages without requiring readers to obtain locks on non-leaf pages. The method comprises the steps of: for a read operation, obtaining a shared lock on a root page;
searching the index to locate the leaf page;
shared locking the leaf page;
releasing the shared lock on the root page; and thereafter
releasing the lock on the leaf page; and for a write operation, obtaining a shared lock on the root page;
locating the leaf page;
exclusive locking the leaf page;
releasing the shared lock on the root page;
making the update to the index selectively:
(1) at the locked leaf page, if possible, without updating a
non-leaf page, otherwise,
(2) exclusive locking the root and non-leaf page;
(3) updating the non-leaf page;
(4) releasing any exclusive lock held on a root page;
(5) repeating steps (2), (3), and (4) for every non-leaf
page that needs to be updated; and
(6) at commit time, releasing all other exclusive locks.
A table in a data base management system (DBMS) of the type herein described can have one or more indexes defined on it, each of which is an ordering of parts (keys) of the row of the table and is used to access certain rows when the keys are known.
An index is implemented with a "tree" structure consisting of leaf pages and non-leaf pages. A page is a physical unit of transfer between main storage and secondary storage (DASD).
A non-leaf page contains a list of page numbers of other index pages, along with the highest key values for those pages.
A leaf page is the lowest level in the index tree. It consists of keys and their associated row addresses (pointers to the rows in the table that have the given key value). A physical leaf page can be divided into pieces called "mini-pages" or "logical pages".
A user of DBMS can use CREATE INDEX to make an index available to the system. The DBMS responds by controlling when and how that index is used and maintaining the index. The user has no control over when an index is used to service any given request.
Multiple tasks can access the same index at the same time. Tasks that are reading data can share all parts of the index. Tasks that update a leaf page in
the index must lock out all other tasks from that leaf page, including read-only tasks. Normally this is done by locking leaf pages in the "Exclusive" state. Readers lock pages in the "Shared" state. If someone already holds an exclusive page lock, no one else is allowed to acquire an exclusive or shared lock on that page until the exclusive lock is released. If someone already holds a shared page lock, anyone requesting an exclusive lock on that page will wait until all shared locks have been released.
A leaf page split occurs when updates to non-leaf pages occur when a leaf page is too full to accept an insert.
A lock request can be an expensive operation in terms of execution time. I...