Information Technology Reference
In-Depth Information
buffer onto disk as part of a large sequential disk write, the page goes to a new
disk location and, accordingly, gets a new page-id. The changed page-id of the page
replaces the old page-id in the index record stored in the parent page, thus avoiding
the overhead of indirect addressing involved in logical-to-physical mappings.
Conventional in-place updates remain to be possible on the write-optimized B-
tree. Of the B-tree pages, at least the root page should retain its original page-id and
not be relocated. Note that relocating the root page would involve updating some
system-catalog pages and would also violate our assumption made previously in
Sect.
7.1
that the page-id of the root page never changes during the lifetime of the
index.
Because of the online maintenance of changed page-ids within the index, the
write-optimized B-tree makes sense only if the parent-to-child links are the only
links that appear between the B-tree pages. Observe that if, for example, the leaf
pages were linked from left to right, as is usual in many B-tree implementations, an
update on the rightmost leaf page would cause sequences of updates that eventually
propagate through the entire tree. Moreover, if two-way linking were used at the
leaf level, which is also common, then a single update on any leaf page would cause
infinite sequences of updates through the tree. This is our main motivation for not
using sideways linking in the B-tree.
When a modified child page q of a page p is to be relocated, the parent page p
must also be buffered and write-latched, so that the page-id q in the index record
.x; q/ in the parent page pointing to the child page can be replaced by the new
page-id q
0
of the child page. The problem here is how to keep track of the parent
pages.
The write-optimized B-tree employs an inexpensive method to maintain approxi-
mate information about the page-ids of parents of modified B-tree pages. We assume
each page q carries a
parent-link
field that stores the page-id of the parent of q as
it was observed when the page was last updated. The parent information is not kept
strictly up to date, and hence it cannot be trusted. The parent-link field is updated
only when the page itself is updated in an ordinary update action by a transaction
or in a structure modification. No separate log record is written for the parent-link
update.
The parent links can turn invalid in several ways. The parent-links of all child
pages of a relocated page are left to point to the old location of the parent. Whenever
a structure modification occurs on a non-leaf page, the parent links of at least a half
of the children remain to point to an incorrect parent. For example, when a page q
is split, the parent links in the child pages of q whose index records are moved from
q to its new sibling q
0
continue to point to q.
The parent-link field of a B-tree leaf page is updated when the page is held
write-latched for updating some tuple in it, by one of the single-tuple-update
Algorithms
3.1
,
3.2
,
4.8
,or
4.10
, or by one of the bulk-update Algorithms
10.4
or
10.5
. The page-id of the parent page of the updated page is taken from the saved
path, if one is available; otherwise, the parent-link field remains unchanged. A B-
tree page q that is involved as a modified child page in a structure modification gets
its parent-link updated as a part of the modification. For example, when performing
