#b-tree #DBMS

Question

Let the order of B-tree is 32 and the B-tree is 63% full. What will be the number of <key,data pointer> entries the 2 level B tree holds?

Comments

root is 63% full
max number of <key,ptr> pairs =31
as its 63% full number of pairs = 31*0.63 = 19, number of block pointers =20
in first level, number of <key,ptr> pairs= 19
in 2nd level, 20 nodes, each contain 19 nodes so 20*19 = 380
so total possible <key,ptr> pairs = 19+380 = 399 i think.

---

add one more level caz root is considered as level 0

why u choose 31*.63=19 why not 20 caz when we say 50% full we do ceil(P/2)

then why not ceil(31 * .63)=20

Answer 1

here, order = 32 and Assuming that B tree node is 63% full.

so P = ceil ( 0.63 * 32 ) = 21 

( If we take order P = 20, then utilization will be 62.5 % which is not allowed. )

so at level 0 (Root ) : 20 keys

        level 1 : 21 * 20 = 420 keys

        level 2 : 21 * 21 * 20 = 8820 keys

Hence, total =20 + 420 + 8820 = 9260 keys

Comments

21 should be taken.. Else minimum occupancy of 63% will not be satisfied

---

ok then my ans is correct??

---

i think u are correct