Information Technology Reference
In-Depth Information
Chapter 8
B-Tree Structure Modifications
A B-tree structure modification is an update operation that changes the tree structure
of the B-tree, so that at least one index record (a parent-to-child link) is inserted,
deleted, or updated. The structure modifications are encompassed by the following
five types of primitive modifications: page split, page merge, records redistribute,
tree-height increase, and tree-height decrease. Each of these primitive modifications
modifies three B-tree pages, namely, a parent page and two child pages.
Structure modifications are triggered by insert or delete actions on leaf pages
that cannot accommodate the action: an attempt to insert into a leaf page that has no
room for the tuple to be inserted or an attempt to delete from a leaf page that would
underflow by the deletion. In such cases, to make the insertion possible, a sequence
of one or more page splits, possibly preceded by a tree-height increase, is needed,
and to make the deletion possible, a sequence of one or more page merges or records
redistributes, possibly preceded by a tree-height decrease, is needed.
In this chapter we show how B-tree structure modifications are managed in the
ARIES
-based transaction-processing environment developed in the previous chap-
ters, using the traversal algorithms presented in Chap.
7
. Following the principle of
redo-only structure modifications outlined in Sects.
3.5
and
4.11
, we give algorithms
for the five primitive structure modifications. We also show how sequences of
these modifications, when performed in a top-down fashion, retain the B-tree in a
consistent and balanced state during normal transaction processing with any number
of concurrent forward-rolling and backward-rolling transactions and that in the
event of a process failure or a system crash the B-tree is brought back to a consistent
and balanced state in the redo pass of
ARIES
recovery.
