Consider a relation s over the attributes A and B with the following characteristics:

Question

• 5,000 tuples with 10 tuples per page
• A 2-level B+ tree index on attribute A with up to 100 index entries per page
• Attribute A is a candidate key of s
The values that the attribute A takes in relation s are uniformly distributed in the range 1 to 100,000.

(a) Assuming that the aforesaid index on A is unclustered, estimate the number of disk accesses needed to compute the range query ?A>1000 ? A<6000(s).
(b) What would be the cost if the above index were clustered?

Answer 1

(a) Assuming that the aforesaid index on A is unclustered, estimate the number of disk accesses needed to compute the range query ?A>1000 ? A<6000(s).
SOLUTION:
Unclustered index: Since the range 1000–6000 is a fraction 5000/100000 = 1/20 or the total range, it means that the selection will roughly select 1/20*5000 = 250 tuples. Since the index is unclustered, it will take 1 I/O per data entry to fetch it through the index.
Searching the index itself will take 2 + the number of pages that contain the relevant index entries (ceiling(250/100)=3). Therefore, the total number of disk accesses will be 2+3+250=255.

(b) What would be the cost if the above index were clustered?
Clustered index: In this case, we only need to find the first data page at the cost of 1 index search, i.e., 2. All the data records of interest will be grouped in maximum 250/10
+1 = 26 pages (1 extra if the first data entry of interest starts in the middle of a page). So, the total number of accesses is 2+26=28.