In Section 21.3.1 we described an algorithm that allowed the concurrent execution of a search for a unique key and an insert of a rowin a B+ tree. Extend the algorithm to range searches and deletes.

Question

What will be an ideal response?

Answer 1

The search algorithm uses sibling pointers when it reaches the leaf level to find keys
in the range. Read latches are obtained on additional leaf nodes. The delete algorithm
upgrades the update latch on the leaf page, p1 containing the first key to be deleted
to a write latch and deletes the key(s). If the sibling node, p2, might also contain keys
in the range, the operation backs up to the parent of both, p, and then acquires an
update latch on p2. If p2 contains keys in the range the update latch is upgraded to
a write latch and the keys are deleted. The update latch on p is upgraded to a write
latch if p1 and p2 are merged.