B-Tree Traversals - Transaction Processing - page 163

In general, in search for a key x, the saved path is used as follows. First the least
index i with path Œi : low-key x< path Œi : high-key is determined, and the page
p D path Œi : page-id is latched. Then the contents of page p are examined so as
to check whether or not this page is still a correct page for starting the traversal.
If P AGE -LSN .p/ has not advanced from the saved value path Œi : page-lsn , we can be
sure that the saved information is still valid, and we can search for x in the subtree
rooted at p.Otherwise,if P AGE -LSN .p/ has advanced, we can no longer trust the
saved information. However, inspecting the current contents of page p may still
reveal that it is safe to start at p. For example, if we see from the page header that
page p is still part of the B-tree index of our relation r and if x 1 x x 2 where x 1
is the least and x 2 the greatest key currently in page p, then certainly p is a correct
place to start at. Otherwise, we have to unlatch p and try the page at the next higher
level on the saved path, and so on, in the worst case arriving at the root.

7.3 Traversals for Read Actions

In this section and in the sections that follow, we present in detail how the B-tree
is traversed when executing the forward-rolling actions RŒx, IŒx and DŒx or the
backward-rolling actions I 1 Œx and D 1 Œx of our transaction model. To make the
traversals to work correctly and efficiently, several problems have to be solved. First
we must take care that the traversals are deadlock-free. This means that B-tree pages
must be latched in a prespecified order, which is the following:

1. If both a parent page and a child page must be kept latched simultaneously, the
parent is latched first.
2. If two sibling or cousin pages, that is, two pages at the same level of the tree,
must be kept latched simultaneously, the elder one is latched first.

With traversals for read actions RŒx; z ; v , we have the problem that the tuple
.x; v / to be read may not reside in the page p that covers the key z given as the input
argument of the action: it may reside in the leaf page p 0 next to page p (Fig. 7.3 b).
(Because, by the balance conditions, there are no non-root empty pages, we know
however for sure that .x; v / must reside in p 0 if it does not reside in p.) In this case
we must begin the traversal at a page that is an ancestor to both p and p 0 and the
traversal must end with both pages being latched.
As it is however less common that the tuple .x; v / to be read does not reside in
the page that covers the key z given as the input argument, we always start the search
for x optimistically assuming that .x; v / resides in the page covering z , and only in
the case that the assumption turns out to be false, we perform a pessimistic traversal
that locates both the page that covers z and the one that covers x.
The procedure call read .T;x; z ; v / (Algorithm 6.6 ) implements the read action
RŒx; z ; v of transaction T . The call find-page-for-read .p; p 0 ;x; z / is used to
locate and read-latch the leaf page p that covers key z and the leaf page p 0 that
contains the least key x with x z if such a key exists. The procedure find-page-