Information Technology Reference
In-Depth Information
Fig. 8.8
The B-tree of Fig.
7.1
after the tree height has been increased and pages p
3
and p
6
have
been split
Next the call
top-down-page-splits
.p; 16;
v
0
/ with p
D
p
1
is performed, resulting
in the B-tree of Fig.
8.8
. Here the height of the tree is increased by the call
tree-
height-increase
.p
1
;q;x
0
;q
0
/ that returns with q
D
p
0
1
, x
0
D
65 and q
0
D
p
0
1
.
Page p
3
is split by the call
page-split
.p
0
1
;p
3
;x
0
;q
0
/ that returns with x
0
D
25 and
q
0
D
p
0
3
.Pagep
6
is split by the call
page-split
.p
3
;p
6
;x
0
;q
0
/ that returns with
x
0
D
12 and q
0
D
p
0
6
. The following log records are written:
n
1
Wh
tree-height-increase
;p
1
;p
0
1
; 65; p
0
1
;s
1
;V
1
;V
2
;3
i
n
2
Wh
page-split
;p
0
1
;p
3
; 25; p
0
3
;s
2
;V
3
;2
i
n
3
Wh
page-split
;p
3
;p
6
;12;p
0
6
;s
3
;V
4
;1
i
where p
0
1
and p
0
1
are the new children of the root page p
1
; p
0
3
is the new sibling of
page p
3
; p
0
6
is the new sibling of page p
6
; s
1
, s
2
,ands
3
are the space-map pages
that record the allocation of p
0
1
and p
0
1
,andp
0
3
and p
0
6
, respectively; and the sets of
records moved are:
V
1
Df
.
1
;p
2
/; .8; p
3
/; .50; : : :/
g
, from page p
1
to page p
0
1
.
V
2
Df
.65; : : :/; .80; : : :/; .99; : : :/
g
, from page p
1
to page p
0
1
.
V
3
Df
.25; p
9
/; .35; : : :/; .40; : : :/
g
, from page p
3
to page p
0
3
.
V
4
Df
.12; : : :/; .14; : : :/; .15; : : :/
g
, from page p
6
to page p
0
6
.
The call
top-down-page-splits
.p; 16;
v
0
/ saves the path p
1
!
p
0
1
!
p
3
!
p
0
6
and
returns with p
D
p
0
6
.
Page p
D
p
0
6
has now room for the tuple .16;
v
0
/, but it does not contain
the key next to 16. Hence, the page is unlatched and the call
find-page-for-
insert
.p; p
0
; 16; true/ is performed. This call returns with page p
D
p
0
6
write-
