Operations on the Physical Database - Transaction Processing - page 38

p 1 : p 2 : p n− 1 : p n :

...

Fig. 2.5 A unidirectional chain of pages

contains an empty link to terminate the chain (Fig. 2.5 ). A process thread holds the
page id of page p 1 , and it wants to read the pages in the order in which they are
chained. To be sure that the link from page p i to page p iC1 stays valid while the
link is traversed, the process must use a latching protocol in which the latch on p i
is released only after the latch on p iC1 has been obtained.

t

This latching protocol is called latch-coupling or crabbing .Itisused,for
instance, when searching for a record in a B-tree: on the search path from the root of
the B-tree down to the leaf that contains the record, the parent page is kept latched
until the latch on the child page has been acquired.

2.8 Modifications on the Physical Structure

When data is inserted into the database, new pages must be allocated to store that
data, and those pages must be linked as part of the physical database structure. A
split of a full B-tree page involves allocating a new empty page and linking it as a
part of the B-tree structure. Deleting data from the database may similarly shrink
the database structure, and emptied pages are detached from the structure. Such
operations that modify the structure of the physical database but leave the logical
database intact are called structure modifications .
The entire database structure must be maintained in a consistent state even when
there are many structure modifications caused by concurrently running transactions.
We have to require atomicity of the structure modifications.
During normal transaction processing, a safe method for guaranteeing the
consistency of the physical database is to hold all the pages involved in a structure
modification write-latched for the duration of the modification. For example, when
a full child page q of a B-tree page p is split by allocating a new empty page q 0 ,
then all these three pages are held write-latched during the split, that is, until page
q 0 has been linked as a child of page p and a half of the records in page q has been
moved to page q 0 (and the modification has been logged).

Example 2.5 Assume that the logical database (or one of its relations) is imple-
mented as a heap, that is, an unordered sequential file, for which new pages are
allocated as new tuples are inserted into the database (Fig. 2.6 ). The pages in the
heap are linked so that the next-page field in the header of a page contains the page
id of the next page in the heap. In addition, we assume that the header of the first
page f in the heap also contains the identifier of the last page in the heap.