Question

A B+ tree based unclustered index exists over on a search key of 98452 records, which stores 200 keys in each leaf and steering page. What is the smallest number pages might be used by this index? how deep is the tree in this case? how many keys are in the root node?

Answer 1

98452 records and 200 keys per node

Smallest no. of pages:

98452/200 = 492 full pages with remainder of 52 keys, but this would violate the 50% rule as 52 < 50% of 200 so,

we can have 491 full pages and the remainder in this case would be 252 keys as 491*200 + 252 = 98452

Now these remaining 252 keys can be split into two pages with 126 keys each, in this the 50% rule is not violated as 126 > 50% of 200

So the smallest no of pages = 491 + 2 = 493

Keys in the root node:

We take the total no of records 98452 and divide it by the order 200. This gives us 492 which is greater than 200

We again divide 492 by 200 which gives us 2. We stop now as we got a number less than the order (200).

So the number of keys in root node = 2

Depth of the tree:

Since we made 2 divisions in the previous step to calculate no of keys in root node, depth of the tree is 2+1 = 3