Information Technology Reference
In-Depth Information
Chapter 7
B-Tree Traversals
The
B-tree
, or, more specifically, the B
C
-tree, is the most widely used physical
database structure for primary and secondary indexes on database relations. Because
of its balance conditions that must be maintained under all circumstances, the B-tree
is a highly dynamic structure in which records are often moved from one page to
another in structure modifications such as page splits caused by insertions and page
merges caused by deletions. In a transaction-processing environment based on fine-
grained concurrency control, this means that a data page can hold uncommitted
updates by several transactions at the same time and an updated tuple can migrate
from a page to another while the updating transaction is still active.
In this chapter we show how the B-tree is traversed when performing a read,
insert, or delete action under the key-range locking protocol described in Sect.
6.4
.
The traversal algorithms to be presented augment the read, insert, and delete
algorithms presented in Sect.
6.7
. The latching protocol applied in the B-tree
traversals is deadlock-free, ensuring that no deadlocks can occur between latches
held by different process threads and that no deadlock can occur between a latch
and a lock. Repeated work done for the traversals is minimized by heavy use of
saved paths
, which often make it possible to start a new traversal by the same thread
at some lower-level page in the previously traversed path, rather than at the root
page. Saved paths thus provide a simple means of shortening the access-path-length
of database actions.
The B-tree structure we consider is the very basic one in which no sideways
links are maintained and in which deletions are handled uniformly with insertions.
The management of this basic B-tree structure seems to be the most challenging as
compared to some B-tree variants such as those with sideways links maintained at
the leaf level or to those in which the balance conditions are relaxed by allowing
pages to become empty until they are detached from the B-tree and deallocated.
One motivation of our approach is that for write-optimized B-trees (to be discussed
in Chap.
15
), sideways-linking is not feasible at all.
