Information Technology Reference
In-Depth Information
10.7
Complexity of Scanning a Key Range
In this section we analyze the complexity of the bulk-read, bulk-insert, and
bulk-delete algorithms presented above. In all these actions the main target for
optimization is the phase of searching for the leaf pages on which the actions need
to be applied. We first notice that, due to the lack of sideways linking of the leaf
pages in the B-tree, the traversal algorithms use the saved-path strategy in order to
avoid the repeated search from the root page.
We first consider the bulk-read action. Let s
X
be a set of non-overlapping key
ranges to be read. We wish to prove that in the absence of concurrent updating
transactions, the total number of page latchings performed in bulk-reading the tuples
in the range set s
X
is
X
k
O.log n
C
log.1
C
dist
.l
i1
;l
i
///;
(10.1)
iD2
where n is the number of all leaf pages, l
1
;l
2
;:::;l
k
is the ordered sequence of leaf
pages containing tuples in some range of s
X
(so that the keys in l
i1
are less than
those in l
i
), and
dist
.l
i1
;l
i
) denotes the number of leaf pages between l
i1
and l
i
.
In order to prove the result, we begin with some definitions and lemmas. For any
two leaf pages p and q,letM.p; q/ denote the number of pages that are on the path
from the root to q but not on the path from the root to p;seeFig.
10.3
.
Assume that the B-tree has n leaf pages, numbered 0;1;:::;n
1 from left to
right, and consider k of them with numbers p
1
<p
2
<
<p
k
.LetM denote
the number of pages (including the pages p
1
;:::;p
k
) which lie on the paths from
Fig. 10.3
The number in M.p; q/ is the number of pages not on the path from p to the root but
on the path from q to the root
