Why would two-phase locking not be an appropriate concurrency control scheme for indexes? Discuss a more appropriate locking scheme for tree-based indexes.

Question

What will be an ideal response?

Answer 1

Concurrency control for an index structure can be managed by treating each page of the index
as a data item and applying the 2PL protocol. However, since indexes are likely to be
frequently accessed, particularly the higher levels of trees (as searching occurs from the root
downwards), this simple concurrency control strategy may lead to high lock contention.
Therefore, a more efficient locking protocol is required for indexes.
Can use the following locking strategy:
(1) For searches, obtain shared locks on nodes starting at the root and proceeding downwards
along the required path. Release the lock on a node once a lock has been obtained on the
child node.
(2) For insertions, a conservative approach would be to obtain exclusive locks on all nodes
as we descend the tree to the leaf node to be modified. This ensures that a split in the leaf
node can propagate all the way up the tree to the root. However, if a child node is not full
the lock on the parent node can be released. A more optimistic approach would be to
obtain shared locks on all nodes as we descend to the leaf node to be modified, where we
obtain an exclusive lock on the leaf node itself. If the leaf node has to split, we upgrade
the shared lock on the parent node to an exclusive lock. If this node also has to split, we
continue to upgrade the locks at the next higher level. In the majority of cases, a split is
not required making this a better approach.