Information Technology Reference
In-Depth Information
Fig. 8.11
Transaction T
3
wants to insert into the full page q
4
and is therefore splitting pages up
along the insertion path
Meanwhile, the thread executing T
1
performs the action WŒx;
u
;
v
on page p
4
,
writes the log record
n
9
Wh
T
1
;W;p
4
;x;
u
;
v
;n
1
i
and unlatches page p
4
. Now the thread executing T
2
gets a latch on page p
4
.The
tuple .y;
v
0
/ to be inserted does not fit into page p
4
, so the page must be split.
Therefore T
2
allocates a new page p
0
4
, moves half of the tuples on page p
4
to this
page, inserts the tuple, and commits (thus flushing the log). The tuple .x;
v
/ is among
those that were moved (see Fig.
8.12
). The following log records are written:
n
10
Wh
S
0
;
begin-smo
i
,
n
11
Wh
S
0
;
page-split
;p
4
;y
0
4
;p
0
4
;s
0
;V
0
;1;n
10
i
,
n
12
Wh
S
0
;
insert-index-record
;p
3
;y
0
4
;p
0
4
;n
11
i
,
n
13
Wh
S
0
;
commit-smo
i
,
n
14
Wh
T
2
;I;p
4
;y;
v
0
;n
2
i
,
n
15
Wh
T
2
;C
i
.
Transactions T
1
and T
3
are still active. At this point, a failure occurs. As a result
of the redo pass of recovery, the B-tree will be in the same state as it was at the time
of failure—but this state is inconsistent: there is no way to reach page p
0
2
from the
root p
1
, and thus also pages p
3
, p
4
,andp
0
4
are unreachable.
The undo pass of recovery should roll back transactions T
1
and T
3
and the
incomplete structure modification S . The action WŒx;
u
;
v
by T
1
has been logged
later than the splits by S . Thus, the undo action W
1
Œx;
u
;
v
is performed before
the splits are undone.
The action W
1
Œx;
u
;
v
is first attempted physically on page p
4
, which is the
page mentioned in the log record for WŒx;
u
;
v
. This is not possible, because after