Information Technology Reference
In-Depth Information
is about to be executed, and then the algorithm retains the B-tree as consistent
and balanced, provided that it is so initially. Thus, the same holds for any
sequence of such operations that can be run on an initially consistent and balanced
B-tree.
t
Lemma 8.6
The latching protocol applied in procedures tree-height-increase,
page-split, tree-height-decrease, page-merge, and records-redistribute is deadlock-
free.
Proof
In Algorithms
8.1
-
8.5
, only write latches are acquired, and while a page is
kept latched, no latch is requested on its parent or elder sibling or cousin. We also
assume that in Algorithm
8.3
, where we have to latch two space-map pages, those
pages are latched in some prespecified order.
t
8.4
Sequences of Redo-Only Modifications
The preconditions stated for the structure modifications defined in the previous
sections imply that if more than one page on an insertion path has to be split or
more than one page on a deletion path has to be merged or its records redistributed,
then those splits or merges or redistributes must be performed in top-down order
along the path, and if a tree-height increase or decrease is needed, it must be the first
modification to be performed.
As we have already noted, on the insertion path shown in Fig.
8.1
a, where pages
p
3
and p
4
are full but page p
2
has room for an index record, page p
3
must be
split first, thus making space for the index record pointing to the new sibling page
resulting from the split of child page p
4
. Similarly, on the deletion path shown in
Fig.
8.2
a, where pages p
3
and p
4
are about to underflow but page p
2
is not, page
p
3
and its sibling p
0
3
are first merged, thus ensuring that page p
3
will not underflow
when the index record pointing to child page p
0
1
is deleted in merging p
0
1
with its
sibling p
1
.
When in the procedure
find-page-for-insert
(Algorithm
7.8
) it is found that the
page covering the key x of the tuple .x;
v
/ to be inserted has no room for the tuple,
the procedure call
start-for-page-splits
.p; x;
v
/ (Algorithm
8.6
) is issued so as to
determine the starting page for page splits, that is, the highest-level page p on the
path down to the page covering x that needs a structure modification (tree-height
increase or page split) in order to accommodate the insertion. That page must satisfy
the following conditions:
1.
P
AGE
-LSN
.p/
D
path
Œi :
page-lsn
and
path
Œi :
low-key
x<
path
Œi :
high-key
or
p is a B-tree page with x
1
x
x
2
for the keys x
1
and x
2
of some records in
page p.
