Information Technology Reference
In-Depth Information
B-tree pages, namely, a parent page and two child pages. In the basic solution
presented below, the allocation of pages (in tree-height increase and page split) and
the deallocation of pages (in tree-height decrease and page merge) are included in
the modifications, so that they also involve the updating of the space-map pages
that keep up a record of currently allocated pages. The modifications also include
the formatting of the allocated or deallocated pages. The
LSN
of the log record is
stamped into the
P
AGE
-LSN
s of all the (three, four or five) modified pages, which are
kept write-latched during the modification and its logging. Each modification retains
the consistency and balance of the B-tree, provided that the B-tree is consistent and
balanced initially and the precondition specified for the modification holds.
8.2
Tree-Height Increase and Page Split
A
tree-height increase
may be needed when the root page p of a B-tree is full, so
that it has no room for a record of maximum length. Then two pages, q and q
0
,are
allocated and formatted as B-tree pages of the height of p, the records in page p are
distributed between q and q
0
such that the records with keys greater than or equal
to some key x
0
go to page q
0
, the height of p is incremented, and the index records
.
1
;q/ and .x
0
;q
0
/ are inserted to page p thus making q and q
0
the only children
of p, as illustrated in Fig.
8.3
.
The tree-height-increase modification is performed by the procedure call
tree-
height-increase
.p;q;x
0
;q
0
/, where the page-id p is given as an input parameter
(Algorithm
8.1
). The precondition for this modification is that the root page p is
write-latched and contains enough records so that when these are distributed equally
between the two children, neither of them will underflow. The modification is logged
with the redo-only log record
n
Wh
tree-height-increase
;p;q;x
0
;q
0
;s;V;V
0
;h
i
;
(8.1)
a
b
Fig. 8.3
Increasing the height of the B-tree. The records in the root page p are evenly distributed
at key x
0
between two new pages q and q
0
, which become the only children of p.(
a
) Root before
height increase (
b
) After height increase
