Information Technology Reference
In-Depth Information
common prefix x of
low-key
.p/ and
high-key
.p/ once in the page, and for every
record .xy;
v
/ with key xy in the page, we store the truncated record .y;
v
/.When
the key range of a page changes in a B-tree structure modification, the compression
within the page must be recomputed. In a structure modification that shrinks the
key range, such as a page split, tree-height increase, or a records redistribute, the
longest common prefix may get longer, and in a structure modification that enlarges
the key range, such as a page merge, tree-height decrease, or records redistribute,
the longest common prefix may get shorter. Work out how this compression can be
accomplished, if possible, with the structure modifications presented in Sects.
8.2
and
8.3
. Note that there is a problem with determining exactly the longest common
prefix of
low-key
.p/ and
high-key
.p/ when p is the youngest child of its parent and
its key range changes in a situation when the information in the saved path cannot
be trusted. Show that this problem does not occur if we store
high-key
.p/ explicitly
in page p, as suggested in Problem
7.7
.
8.4
Some practical implementations of the B-tree relax the balance conditions such
that pages are allowed to become empty until they are detached from the B-tree and
deallocated. Adapt the algorithms in this chapter to this
free-at-empty
policy. Note
however that we cannot leave completely empty pages hanging around in the B-
tree; if a page becomes empty, it must be detached from the B-tree within the same
structure modification that empties it. Explain why. What might be the actual gains
achieved by this policy?
8.5
A page split includes the allocation of the new sibling page and thus the
updating of the corresponding space-map page in the same redo-only atomic
structure modification. Similarly, the deallocation of the emptied sibling is included
in a page merge, the allocations of the two child pages are included in a tree-height
decrease, and the deallocations of the two child pages are included in a tree-height
decrease. The contention by different processes on the space-map pages, which
must be kept write-latched during the entire structure modification, may degrade
concurrency. Consider means of alleviating this problem. What if the allocations
and deallocations are made redo-only modifications of their own? What kind of log
records are then used?
8.6
With top-down structure modifications, some unnecessary page splits and
merges may occur when the keys vary in length keys or when other concurrent
transactions perform insertions or deletions on the same path between the optimistic
and pessimistic traversals. Give examples of this. Also show that with fixed-length
keys and in the absence of concurrent updates on the same path no unnecessary
splits or merges are performed.
8.7
Outline a procedure
bottom-up-page-merges
that performs the sequence of
page merges or records redistributes (possibly preceded by a tree-height decrease)
triggered by a delete action, when bottom-up structure modifications are used. What
redo-undo log records are generated for such a sequence? Also outline an algorithm
for undoing such a sequence when recovering from a system crash. What redo-only
log records are generated?
