I am a student in computer science and I have a question, which refers to cost optimization. I have to read the book (Fundamentals of Database Systems from Elmasry and Navathe) and try to present the topic to class. But I have some issues understanding one cost formula for B-tree-index:
Using a secondary (B+-tree) index: [...]If the comparison condition is (> >=, <, <=) and half the file records are assumed to satisfy the condition, then(very roughly) half of the first level index blocks are accessed, plus half the file records via the index. The cost estimate for this case, approximately, is C=x+(b_l1/2)+(r/2).[...]
Using Linear search: [...] C=b[...]
where
x = number of levels of multilevel index
r = number of records
b = number of blocks
b_li = number of first-level index blocks
C = cost function
I don't understand the formula for the secondary index. I think the formula should look like this:
C=x+(b_l1/2)+(b/2)
Can somebody explain me, why the formula uses the number of entries instead of number of blocks?
Thank you very much