Suppose there is a relation R(A, B, C) with a B+-tree index with search keys (A,

Question

Suppose there is a relation R(A, B, C) with a B+-tree index with search keys (A, B).

1. What is the worst-case cost of finding records satisfying 10 < A < 50 using this index, in terms of the number of records n1, retrieved and the height h of the tree?

2. What is the worst-case cost of finding records satisfying 10 < A < 50 and 5 < B < 10 using this index, in terms of the number of records n2 that satisfy this selection, as well as n1 and h defined above?

3. Under what conditions on n1 and n2, would the index be an efficient way of finding records satisfying the condition from Part (2)?

Explanation / Answer

1. B+- tree do the searching in a sequential manner as leafs are interconnected so to search records in the range 10<A<50 it just requires to find the element with smallest A value and then it can return the result sequentially with shifting to the right of the current pointer untill it get a value with higher A value. SO to find the elemnt with smallest A value we perform a binary search over the tree so it will take o(h) time to find the smallest one. now to retrive n1 records it will perform sequestial search over leaf node n1 times thorugh right shift. Now one shift cost O(1) time. so the total time is O(h+n1).

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.