7. Consider a relation TwitterUsers(UserID: integer, LastName: string, ...) whic

Question

7. 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

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.

Related Questions

Navigate

• Browse (All)
• Browse 7
• Subjects

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