Cache-conscious concurrency control scheme for database systems

摘要

An optimistic, latch-free index traversal (“OLFIT”) concurrency control scheme is disclosed for an index structure for managing a database system. In each node of an index tree, the OLFIT scheme maintains a latch, a version number, and a link to the next node at the same level of the index tree. Index traversal involves consistent node read operations starting from the root. To ensure the consistency of node read operations without latching, every node update operation first obtains a latch and increments the version number after update of the node contents. Every node read operation begins with reading the version number into a register and ends with verifying if the current version number is consistent with the register-stored version number. If they are the same, the read operation is consistent. Otherwise, the node read is retried until the verification succeeds. The concurrency control scheme of the present invention is applicable to many index structures such as the B+-tree and the CSB+-tree.

主权项

1. A device for searching a database, the device comprising:
a memory configured to store an index tree that has one or more nodes including a root node, each node associated with a latch governing concurrent access to the node and each node having contents including one or more keys including a high key, the high key denoting the upper bound of the one or more keys, a version number indicating a sequence of updates of the node contents, a link pointer pointing to a right sibling of the node at the same level, and one or more pointers pointing to data items in the database in the case of a leaf node and to child nodes in the case of a non-leaf node; and a concurrency controller operatively coupled to the memory, the concurrency controller configured to: lock the latch of a first node of the one or more nodes that is traversed; update, within the memory, the contents of the first node after the latch of the first node is locked, the updating of the contents including updating at least one of the one or more keys, the link pointer, or the one or more pointers; increment the version number included in the first node based on the updating of the at least one of the one or more keys, the link pointer, or the one or more pointers within the memory; and release the latch of the first node after the version number is incremented.