Information Technology Reference
In-Depth Information
a
b
p
1
:
p
1
:
·
·
·
·
p
n
−
1
:
p
n
−
1
:
p
n
:
p
n
:
p
n
:
x
Fig. 2.7
Inserting a tuple with key x into a full leaf page p
n
of a B-tree; (
a
) before insertion, (
b
)
after insertion
Example 2.6
Assuming that the physical database is a sparse B-tree index (Fig.
2.7
),
a read action RŒx is mapped to a sequence
RŒp
1
RŒp
2
:::RŒp
n
of reads of pages p
1
;p
2
;:::;p
n
on the path from the root page p
1
down to the leaf
page p
n
that contains the tuple with key x.
Similarly, an insert action IŒx is mapped to a sequence
RŒp
1
RŒp
2
:::RŒp
n1
W Œp
n
of reads of non-leaf pages p
1
;p
2
;:::;p
n1
and a read and write of the leaf page p
n
,
assuming that page p
n
has room for the tuple to be inserted.
If the page p
n
has no room for the tuple, the corresponding page-wise operation
sequence might look like
RŒp
1
RŒp
2
:::RŒp
n1
W Œp
n
W Œp
0
n
W Œp
n1
W Œp
n
W Œp
0
n
;
where the first WŒp
n
is only a read and the subsequence WŒp
0
n
W Œp
n1
W Œp
n
represents the split of page p
n
, involving an allocation of a new page p
0
n
,moving
the upper half of tuples in p
n
to p
0
n
and linking p
0
n
as a child of p
n1
;thefinal
WŒp
0
n
represents the insertion of the tuple into page p
0
n
. The page split represented
by the sequence WŒp
0
n
W Œp
n1
W Œp
n
“commits” and thus persists as soon as it
is completed, even if the logical-level transaction that performed the action IŒx
eventually aborts and rolls back.
t
