Information Technology Reference
In-Depth Information
page-id page-lsn low-key high-key max-key #records space-left
1: p
4
:::
1
5 3 2 :::
2: p
2
:::
1
8 5 2 :::
3: p
1
:::
1 1
99 6 0
Then, when searching for key 7, we use the saved path, observing that the lowest-
level page that covers key 7 is page p
2
. Thus, provided that p
2
still covers key 7, we
can start the search for key 7 at page p
2
.
t
Algorithm 7.1
Procedure
initialize-saved-path
./
path
Œ1:
page-id
path
Œ2:
page-id
the page-id of the root page
path
Œ1:
page-lsn
path
Œ2:
page-lsn
0
path
Œ1:
low-key
1
path
Œ2:
low-key
1
path
Œ1:
high-key
path
Œ2:
high-key
1
path
Œ1:
max-key
path
Œ2:
max-key
1
path
Œ1:
#records
path
Œ2:
#records
0
path
Œ1:
space-left
path
Œ2:
space-left
0
Algorithm 7.2
Procedure
save-root
.p/
i
height
.p/
path
Œi :
page-id
p
path
Œi :
page-lsn
P
AGE
-LSN.p/
path
Œi :
low-key
1
path
Œi :
high-key
1
path
Œi :
max-key
maximum key of the records in page p
path
Œi :
#records
number of records in page p
path
Œi :
space-left
space left in page p
Algorithm 7.3
Procedure
save-child
.p; q/
i
height
.q/
path
Œi :
page-id
q
path
Œi :
page-lsn
P
AGE
-LSN.q/
path
Œi :
low-key
the key in the index record of child page q in page p
if
q is the youngest child of p
then
path
Œi :
high-key
path
Œi C1:
high-key
else
path
Œi :
high-key
the key in the index record of next younger sibling of page q in page p
end if
path
Œi :
max-key
maximum key of the records in page q
path
Œi :
#records
number of records in page q
path
Œi :
space-left
space left in page q
