Information Technology Reference
In-Depth Information
n
25
Wh
T
3
;C
i
,
n
26
Wh
T
1
;C
i
.
Undoing the action WŒx;
u
;
v
logically (on page p
0
4
) succeeds, because the B-tree
is in a consistent state after the rollback of S .
t
Instead of using two scans of the log during the undo pass, we can also solve
the problem of Example
8.17
by preventing the scenario from occurring altogether.
The problem is that two structure modifications triggered by different transactions
are ongoing at the same time. This can be prevented by requiring that every process
thread that starts a structure modification on the B-tree must acquire an exclusive
tree latch
on the B-tree and hold that latch until the structure modification commits.
8.7
B-Link Trees
A
B-link tree
is a B-tree with the addition that the pages at each level of the tree
are
sideways linked
with unidirectional links from left to right. Accompanied with
this addition, it is convenient to also store the high key of each page explicitly in
the page, as suggested in Problem
7.7
. The sideways link in page p can then be
represented as a record .y; p
0
/,wherep
0
is the page-id of the page next to p at the
same level and y
D
high-key
.p/
D
low-key
.p
0
/. For the last page at each level, this
record is .
1
;
?
/,where
?
denotes the null link. An example of such a B-link tree
is shown in Fig.
8.13
, which indexes the set of tuples with keys 1, 3, 5, 6, 7, 9, 10,
11, 15, 16, 17, 19, 26, 27, 28, and 29.
Because of the sideways links, the consistency condition of B-link trees can
be relaxed, so that we do not require explicit parent-to-child links to exist at all
times, except for the parent-to-child link for the eldest child, which must always
be present. The B-link tree of Fig.
8.13
exemplifies this relaxation in that the index
record .5; p
5
/ is missing from page p
2
and that the index record .15; p
7
/ is missing
from page p
3
. Note that in search for, say, key 6, we arrive at leaf page p
4
,where
we find that the searched key, if it exists, must reside in the sibling page p
5
, because
6
5
D
high-key
.p
4
/ and 6<8
D
high-key
.p
2
/ (cf. Fig.
8.14
).
Fig. 8.13
A B-link tree
