B-Tree Structure Modifications - Transaction Processing - page 210

Fig. 8.14 Finding out when a parent-to-child link is missing in a B-link tree. Here y D
high-key .p/ D low-key .p 0 / and x 0 D high-key .q/ D low-key .q 0 /

The advantage of the relaxed consistency of a B-link tree is that the structure
modifications can be made smaller atomic units, namely, ones that modify only a
single level of the tree, as opposed to the structure modifications in our top-down
approach which modify pages at two adjacent levels. For example, the split of a page
q can be made to consist only of the allocation of a new sibling page q 0 ,moving
the upper half of the records in page q to page q 0 andinsertingintopageq the
sideways-link record .y; q 0 /,wherey is least key moved to page q 0 . The insertion
of the parent-to-child record .y; q 0 / into the parent of page q is a separate structure
modification (an atomic unit), which can be performed later, for instance, when a
traversal for some insertion or deletion next time visits page q 0 via the sideways
link from the sibling page q, then the parent-to-child link .y; q 0 / is inserted into the
parent page.
Different issues pertaining to B-link trees are considered in the Problems section.

8.8 Loading of a B-Tree

A database is often initialized by loading data from an external source file to an
initially empty relation. Although it is always possible to implement the load process
using the standard tuple-wise insert actions, we wish to make the load more efficient
by inserting more tuples at a time and by exploiting the natural assumption that
during the load process user transactions may not access the relation, which is made
visible only after the load has been completed.
We view the load process as a task initialized and controlled by the database
administrator rather than executed as a part of user transactions. We also note that
the data coming from the source file may have to be cleansed and filtered before it
can be loaded into the database—an issue we will not discuss here.
When the physical structure of the relation is a B-tree, we may also wish that
the pages are populated using a preset fill-factor , stating, for example, that each leaf
page should filled 75% full of records. Note that when a set of tuples is inserted
using the algorithms thus far presented, the result is a B-tree with all leaf pages
except the last filled only to 50%.