Information Technology Reference
In-Depth Information
a page split logged with
h
page-split
;p;q;x
0
;q
0
;:::
i
, the page-id p of the parent
page is assigned to the parent-link fields of the child pages q and q
0
, and the page-id
of the parent page p
0
of page p, taken from the saved path, is assigned to the parent-
linkfieldofp. Initially, when a page is allocated for the B-tree, the parent-link field
is set to null.
To aid the reconstruction of the parent information in the redo pass of restart
recovery, when performing a forward-rolling single-tuple or bulk insert or delete
on a leaf page, the value assigned to the parent-link field can be included into
the log record written for the update, such as in
h
T; I; p; x;
v
;p
0
;n
0
i
,wherep
0
is the page-id of the parent of the updated page p (as of the saved path that
existed during the update). Now when the update logged with such a log record
is redone, also the update on the parent-link field can be redone. Similarly, the
page-id of grandparent p
0
of the split page q could be included in the log record:
h
page-split
;p;q;x
0
;q
0
;p
0
;:::
i
.
When a modified B-tree page q is to be relocated and flushed, the page p whose
page-id appears in the parent-link field is fixed and write-latched. The contents of
pages p and q are inspected so as to check if both pages still belong to the same
B-tree and that q still is a child page of p. If so, page q can be relocated and flushed.
Otherwise, this cannot be done for now. The correctness of this decision heavily
relies on correct maintenance (in the page header) of the page type and internal
identifier of the structure the page belongs to, as discussed in Sect.
2.2
and shown in
detail in the structure-modification algorithms (Algorithms
8.1
-
8.4
) that allocate or
deallocate B-tree pages.
The procedure call
relocate-and-flush-pages
.M / (Algorithm
15.3
)isusedbythe
buffer manager when it wants to relocate and flush M least-recently used modified
B-tree pages using a single disk write of M pages. If the parent of one of these
pages is not buffered or cannot be resolved using the information stored in the
parent-link field, then the next page in the
LRU
chain is tried, and so on. The
changing in the parent page p of the page-id q to q
0
is logged with the redo-only log
record
h
page-id-change
;p;x;q;q
0
i
:
(15.1)
Naturally, we apply the write-ahead-logging protocol, so that first are flushed onto
the log disk all log records up to and including the one with the greatest
LSN
in the
P
AGE
-LSN
s of the pages to be relocated.
Observe that the page-id change on the parent page must be logged after, not
before, the flushing of the page. If a crash occurs after the flushing and before the
first
page-id-change
log record goes to the log disk, all the flushed pages just remain
as garbage. The previous disk versions of the flushed pages, the shadow pages,
remain in their locations in the physical database, and they are used to recover the
pages in the redo pass of
ARIES
. If some but not all of the
page-id-change
log records
happen to reach the log disk before the failure, the redo pass sees the relocated page
for some of the pages and the shadow page for the rest.
