Information Technology Reference
In-Depth Information
Fig. 7.1
Part of a B-tree of height 3
Lemma 7.2
In a consistent B-tree, the following holds:
(a) For each non-leaf page
p
in the tree, the key range covered by
p
is the union
of the key ranges covered by the child pages of
p
; in particular, low-key
.p/
D
low-key
.q
1
/
and high-key
.p/
D
high-key
.q
2
/
,where
q
1
is the eldest and
q
2
the
youngest child of
p
.
(b) The root page is the only page of the B-tree that covers the entire key space
Œ
1
;
1
/
.
(c) For any non-root page
q
,low-key
.q/
is stored in the parent of
q
; for any non-
leaf page
q
,low-key
.q/
is stored in
q
.
(d) For any non-root page
q
, either high-key
.q/
D1
and
q
is the last page at its
level or high-key
.q/
is stored in the nearest ancestor
p
of
q
with high-key
.p/ >
high-key
.q/
.
t
The above lemma readily implies the following method for accessing the data
page that covers a given key
z
:
p
the page-id of the root page
fix-and-latch
.p/
while
page p is a non-leaf page
do
q
the page-id of the child page of p that covers key
z
fix-and-latch
.q/
unlatch-and-unfix
.p/
p
q
end while
The child page q that covers
z
is the one for which page p contains an index record
.x; q/ where x is the greatest key in page p with x
z
. Also note that we use latch-
coupling in traversing the path from the root page down to the leaf page: we latch
the child first and only then release the latch on the parent.
The B-tree definition above says nothing of how many records should be stored in
a page of a consistent B-tree. The definition even allows pages to be empty. We say
that a consistent B-tree is
balanced
if it satisfies the following
balance conditions
:
