Bulk Operations on B-Trees - Transaction Processing - page 251

i c Cd log.y x C 1/ eD v .x/ C v .y x/ v .y/ Cd log.y x C 1/ e

v .x/ v .y/ C 2 d log.y x C 1/ e ;

(10.3)

as desired. t

Now we are ready to prove:

Lemma 10.13 The number M of pages that lie on the paths from the root to leaves
with numbers p 1 <p 2 < <p k fulfills the condition

X

k

M 2. d log n eC d log.p i p i1 C 1/ e /:

iD2

Proof Consider any two leaves p i1 and p i . Denote by lca .p i1 ;p i / the lowest
common ancestor of p i1 and p i . There are two cases to consider.
Case 1. The edge from lca .p i1 ;p i / toward p i1 is labeled by 0 and the edge
toward p i is labeled by 1.Thenb.p i />b.p i1 / (cf. Fig. 10.4 ). Furthermore,
M.p i1 ;p i / being the number of pages on the path from lca.p i1 ;p i / to p i not
including lca.p i1 ;p i / is equal to the number of bits to the right most and the
leftmost bit in which the binary representations of b.p i1 / and b.p i / differ. By
Lemma 10.12 ,

M.p i1 ;p i / v .b.p i1 // v .b.p i // C 2 d log.b.p i / b.p i1 / C 1/ e
v .b.p i1 // v .b.p i // C 2 d log.p i p i1 C 1/ e ;

(10.4)

because b.p i / b.p i1 / p i p i1 .
Case 2. The edges from lca .p i1 ;p i / toward p i1 and p i are both labeled by
1. Denote by b 0 the binary number obtained from b.p i1 / by changing the 1-bit
corresponding the edge from lca .p i1 ;p i / toward p i1 to 0.Thenb.p i / b 0
p i p i1 and b.p i />b 0 .FurthermoreM.p i1 ;p i / is equal to the number of bits
to the right most and the leftmost bit in which b 0 and b.p i / differ. By Lemma 10.12 ,

M.p i1 ;p i / v .b 0 / v .b.p i // C 2 d log.b.p i / b 0 C 1/ e
v .b 0 / v .b.p i // C 2 d log.p i p i1 C 1/ e
v .b.p i1 // v .b.p i // C 2 d log.p i p i1 C 1/ e ;

(10.5)

because v .b.p i1 // D v .b 0 / C 1.
Substituting into ( 10.2 ) what is given above yields