[prev] 29 [next]

Selection with B-Trees

For one queries: 

N = B-tree root node
while (N is not a leaf node)
   N = scanToFindChild(N,K)
TupleID = scanToFindEntry(N,K)
access tuple t using TupleID from N

Costone  =  (D + 1)r

For range queries (assume sorted on index attribute): 

search index to find leaf node for Lo
for each leaf node entry until Hi found {
	access tuple t using TupleId from entry
}

Costrange  =  (D + bi + bq)r