Information Technology Reference
In-Depth Information
7.4
We add to our key-range transaction model a read action RŒy;
z
;V that reads
from the logical database r all tuples whose keys are in the range Œy;
z
.More
specifically, given keys y and
z
with y
z
, the action RŒy;
z
;V returns the set
V
Df
.x;
v
/
j
.x;
v
/
2
r; y
x
z
g
.
Outline an implementation for this action, keeping the number of page latchings as
small as possible.
7.5
In the B-tree structure considered in this chapter, B-tree pages do not carry
their high keys, and leaf pages do not carry their low keys, that is, these keys are
not stored explicitly in the page and hence cannot be deduced by looking only into
the page contents. Assume that a B-tree page is latched, its
P
AGE
-LSN
is saved, after
which the page is unlatched. Later the page is latched again, and its
P
AGE
-LSN
is
inspected. If it is found to be equal to the saved value, we can be sure that the page
contents have not changed in the interim. Moreover, we can be sure that the key
range covered by the page remains unchanged, that is, the low and high keys of the
page are still the same. Explain why. Point out where this fact is made use of in the
algorithms of this chapter.
7.6
Many presentations of the B-tree index structure use the minor space optimiza-
tion that the key in the index record of the eldest child is omitted, meaning that in
the search algorithm the missing key is regarded as the least possible key (
1
).
Work out this modification for the algorithms in this chapter.
7.7
Consider a modification of the B-tree structure in which the high key of every
B-tree page is stored explicitly in the page. How can B-tree traversals gain from this
modification? Work out this modification for the algorithms in this chapter. What
further advantages can be gained if each leaf page also carries its low key?
Bibliographical Notes
The B-tree was already used as an index structure in early database management
systems such as System R [Astrahan et al.
1976
]. The original B-tree index structure
was introduced by Bayer and McCreight [
1972
]. The B
C
-tree version considered in
this topic (and called simply the B-tree) was introduced by Knuth [
1973
]. Different
B-tree variants and techniques are surveyed by Comer [
1979
] and Srinivasan and
Carey [
1993
] and, more recently, by Graefe [
2010
,
2011
].
Controlling concurrent access to a B-tree or one of its variants has been studied
by several authors, including Samadi [
1976
], Bayer and Schkolnick [
1977
], Lehman
and Yao [
1981
], Kwong and Wood [
1982
], Mond and Raz [
1985
], and Sagiv
[
1986
]. Lock-coupling—the analog of latch-coupling but short-duration page locks
substituted for latches—is used to traverse the B-tree in the algorithms by Samadi
[
1976
], Bayer and Schkolnick [
1977
], Kwong and Wood [
1982
], and Mond and Raz
[
1985
], while in algorithms designed for a variant of the B-tree called the B-link
