Information Technology Reference
In-Depth Information
X
k
M
d
log n
eC
1
C
.
v
.b.p
i1
//
v
.b.p
i
//
C
2
d
log.p
i
p
i1
C
1/
e
/
iD2
X
k
Dd
log n
eC
1
C
v
.b.p
1
//
v
.b.p
k
//
C
2
d
log.p
i
p
i1
C
1/
e
/
iD2
k
X
2
d
log n
eC
d
log.p
i
p
i1
C
1/
e
/:
iD2
(10.6)
The final inequality follows from the fact that
v
.b.p
k
//
1 and
v
.b.p
1
//
d
log n
e
unless k
D
1.
t
From Lemma
10.13
we conclude that the total number of pages on the paths
from the root to the leaves containing keys in the set s
X
of key ranges is bounded
by (
10.1
). The use of the saved-path strategy in Algorithm
10.1
then implies:
Theorem 10.14
Assume a B-tree with
n
leaf pages and a set
s
X
of non-overlapping
key ranges. Then, in the absence of concurrent updating transactions, the total
number of page latching performed in a bulk-read
.T; s
X
;s
XV
/
call is bounded
by (
10.1
).
t
The bound (
10.1
) on the number of page latchings also holds for the bulk-
insert and bulk-delete actions as given in Algorithms
10.2
and
10.3
. This result
directly follows from the algorithms: observe how the bulk insertion progresses;
cf. Fig.
10.2
. Notice, however, that for the bulk insertion, the pages to be latched
are those lying on the paths from the root to the leaves after performing the bulk
insertion.
Problems
10.1
With the partition-based key-range locking protocol, what locks must be
acquired for a bulk-update action WŒs
X
;f;s
XV V
0
?
10.2
Give an algorithm for the call
find-page-for-bulk-read
.p; p
0
;
z
;
z
2
/ used in
implementing the bulk-read action (Algorithm
10.1
).
10.3
Give algorithms for the calls
find-page-for-bulk-insert
.p;h;p
0
;x;
v
/ and
find-
page-for-bulk-delete
.p; p
0
;
z
;
z
2
/ used in implementing the bulk-insert and bulk-
delete actions (Algorithms
10.2
and
10.3
).
10.4
In Algorithms
10.1
and
10.3
, only closed key ranges Œ
z
1
;
z
2
are considered.
What changes (if any) are needed if also open and half-open ranges are allowed?
10.5
Give an algorithm for the bulk-update action WŒs
X
;f;s
XV V
0
.
