MadeEasy Test Series: Databases - B Tree

Question

Suppose size of disk block 1000 Bytes and search key of 12 Bytes, pointer size 8 bytes. How many minimum number of records in data file which leads 3 level dense B+ tree index? (Assume minimum node fill factor ceil(P/2) pointers where p is the maximum pointer per node).

Comments

@y Ashwin Kulkarni 

what about max??

---

@kulkarni @shivank

i think you all are calculating   MINIMUM NO OF KEY+1 = (min no of key +1 ) record

---

@abhishek,

If order of leaf in B+ = 49, then 49<key,pointer> pairs at leaf (max condition)

min condition should be ceil(49/2) = 25 ? what's wrong with this?

Answer 1

Minimum records in the file will be same as minimum number of <key,pointer> pairs in all leaf nodes.

First find the best order for the leaf: $(p-1)*(12+8) + 8 \leq 1000$ $\rightarrow$ $p-1 \leq \frac{992}{20} $ $\rightarrow$ $p=50$

This means maximum 50 pointers(record and block) and minimum 25 pointers $\rightarrow$ min 24 <keys,pointer> pairs

.Here each pair corresponds to a record in file.

Best order for internal node : $p(8) + (p-1)12 \leq 1000$ $\rightarrow$ $p = 50$ $\rightarrow$ min 25 ptrs and min 24 keys.

So, At Level 1, For Root, "minimum 2 pointers" $\rightarrow$ 2 internal nodes at Level 2.

Total pointers at Level 2 considering minimum $\rightarrow$ 25 pointers per node * 2 nodes = 50 pointers $\rightarrow$ Total leaves at the last Level 3 $\rightarrow = 50$

So total <key,pointer> pairs = 24 pointers per leaf * 50 leaves $\rightarrow$ 1200 pairs.

This means $1200$ minimum records will be needed to make a $B^{+}$ Tree of 3 levels.

Comments

Korth would be sufficient.

---

In korth for order n of leaf nodes it is given that n-1 <key, pointers > pairs will be there.

---

@Upasana it was my mistake, According to the standard, Order of leaf is number of total pointers(record pointers and 1 block pointer). And it is given rightly in Korth, I just checked. So if thats the case

Order of leaf node : $(p-1)*(12+8) + 8 \leq 1000 \rightarrow p = 50 \rightarrow$ minimum 25 pointers and 24 keys.

Now continuing from Total 50 pointers at Level 2 , Level 3 will have 50 leaves $\rightarrow$ total $50*24 \rightarrow 1200 $ records. So answer given was right.

Actually the definition of order is mostly changed in questions, so what is given we just have to use that. Only in some questions we need to remember.