B-Tree Structure Modifications - Transaction Processing - page 199

Lemma 8.9 The latching protocol applied in the procedures start-for-page-

splits, top-down-page-splits, start-for-page-merges, and top-down-page-merges

is deadlock-free.

Proof In Algorithms 8.6 and 8.8 , only one latch (a write latch) is ever kept at a
time, and in Algorithms 8.7 and 8.9 , only write latches are acquired, and while a
page is kept latched, no latch is requested on its parent or elder sibling or cousin, by
Lemma 8.6 .

t

Lemma 8.10 The procedures start-for-page-splits and start-for-page-merges keep
at most one page latched at a time and perform at most h write-latchings in all,
where h is the height of the B-tree. The procedures top-down-page-splits and top-
down-page-merges retain the logical database indexed by, and the consistency and
balance of, an initially consistent and balanced B-tree. At most three B-tree pages
and at most two space-map pages are kept latched simultaneously at any time. In
the worst case, 3h write-latchings in all are performed in the procedure top-down-
page-splits, and 4h write-latchings in all are performed in the procedure top-down-
page-merges.

Proof The procedures start-for-page-splits and start-for-page-merges in the worst
case climb along the saved path from the leaf level up to the root, write-latching h
pages.
From Algorithm 8.7 , we see that in the procedure top-down-page-splits ,the
preconditions for the calls of tree-height-increase and page-split are satisfied,
and from Algorithm 8.9 , we see that in the procedure top-down-page-merges
the preconditions for the calls of tree-height-decrease , page-merge ,and records-
redistribute are satisfied, provided that the B-tree is consistent and balanced initially.
In particular, we note that in the procedure top-down-page-merges , the constraints
imposed in Sect. 7.1 on the prespecified constants e, d , E,andD ensure that if two
sibling pages cannot be merged, then distributing the records of those pages equally
between the pages makes both pages not about to underflow. Thus, the consistency
and balance of the B-tree at the end of the procedures follows from Lemma 8.5 .
That the logical database indexed by the B-tree remains unchanged follows from
the fact that none of the five structure modifications mentioned above changes the
set of tuples in the leaf pages of the B-tree (although tuples are moved from one leaf
page to another).
All the five structure modifications keep three B-tree pages write-latched simul-
taneously. The worst case of five simultaneous write latches occurs in the procedure
tree-height-decrease : in addition to the three B-tree pages, also two space-map
pages in the worst case must be kept write-latched. In the procedure top-down-
page-splits , one tree-height-increase and h page splits in all, and in the procedure
top-down-page-merges , one tree-height-decrease and h 1 page merges or records