Consider a relation TwitterUsers(UserID: integer, LastName: string, ...) which h

Question

Consider a relation TwitterUsers(UserID: integer, LastName: string, ...) which has 100 million records of 250 bytes each. We create a B+ tree index on this relation using UserID as search key. Suppose each page (tree node) is 67% full, and the sizes of a page, key and pointer are 4M, 12 and 16 bytes, respectively.

(a) How many leaf nodes does this B+ tree have?
(b) How many levels does this B+ tree have?
(c) What is the average cost of finding a user id in TwitterUsers without using the created B+ tree?

(d) What is the cost of finding a user id in TwitterUsers using the created B+ tree?

Explanation / Answer

Solution :-

My Approach:-

Say P is the Order. and we know In dense index the number of records in DB file = No. of keys in B+tree index

P*4 + (P-1)*250 <= 100 million

P = 67

Now

Level    Min.Nodes    Min_Child    Min_Keys

1    1        2      1

2    2        2*25    2*24

3    67      ---      50*24

So total keys = 1 + 2*24 + 67*24 = 1657.

Please Upvote my answer :)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects