Information Technology Reference
In-Depth Information
Fig. 7.2
Utilizing the saved
path when searching the
B-tree for key x, then for key
x
0
,andthenforkeyx
00
maximum key in the page, the number of records in the page, and the space left (in
bytes or words) in the record area of the page. Except for the low and high keys
and the maximum key, the values of these attributes can be obtained directly from
corresponding fields of the header of the page; the maximum key can be found in
the record area of the page and so can the low key in the case of a non-leaf page,
while the low key of a leaf page comes from the parent page and the high key of any
page from some ancestor page (see Lemma
7.2
).
The array
path
is initialized with the call
initialize-saved-path
./ (Algorithm
7.1
),
which saves a path with the property that, for any key x, the least index i with
path
Œi :
low-key
x<
path
Œi :
high-key
is 2, and
path
Œi :
page-id
is the page-id of
the root. When such a saved path is used, the root is latched for the initial traversal
in read mode rather than in write mode (which in turn is used in latching a leaf page
for an initial traversal for an update action).
The
path
entry for the latched root page p is updated by the call
save-root
.p/
(Algorithm
7.2
), and the
path
entry for a latched child page q of a latched parent
page p is updated by the call
save-child
.p; q/ (Algorithm
7.3
). Observe that the call
save-child
.p; q/ sets the high-key value of the child page q from the high-key value
saved for the parent page p when q is the youngest child. Thus, this call can only be
used in the case when the high-key value saved for the parent can be trusted.
Example 7.4
Assume that we wish to read the tuples with keys 3 and 7 from the
relation indexed by the B-tree of Fig.
7.1
. The initial contents of the array
path
are:
page-id
page-lsn
low-key
high-key
max-key
#records
space-left
1:
p
1
:::
1 1
1
0
0
2:
p
1
:::
1 1
1
0
0
Thus the search for key 3 starts from the root and the path p
1
!
p
2
!
p
4
is
traversed and saved:
