BTREE

Question

find minimum no of levels are req to index 14000 records in a btree of ordre 11??

Answer 1

In a B+ tree records are only present at the leaves where as internal nodes acts as indexes to leaves.

But in B tree, records are present in internal nodes along with the leaves.

Level:0     10R   11P

Level1:     110R   121P

Level2:     1210R   1331P

Level3:     13310R 

Now total number of records in B tree are 10+110+1210+13310 > 14000.

If given a B+ tree then we require one more level , with 3 levels we can index only 13310R.

Adding one more level would index the required records.

Here 3 levels are required with starting level is 0 for a B tree.

Comments

Since it is B-Tree ( not B+ tree ), so records also reside in internal nodes.

Hence, 3 level should be sufficient ( if level starts with 0).

No of records in level 0 = 10

                        level 1 =110

                        level 2 = 1210

                        level 3  = 13310

-------------------------------------------------

   Total records with 3 level = 14640. > ( 14000)

---

@vijaycs You are right...Thnx for correcting,i too had made mistake

Answer 2

Maximum: In Root-> Block pointer/BP=P,  Records/DP=(P-1), Internal Node-> TP=P ,DP= (P-1) , Leaf->DP=(P-1)

Level 0(Root);       1Node         10Records               11BP

Level 1:                11Nodes       11*10=110Records         11*11=121BP

Level 2:                121Nodes       121*10=1210Records       121*11=1331BP

Level 3:                1331Nodes     1331*10=13310Records     

In level 3 ,13310 + 1210 + 110 + 10 = 14640 > 14000

Therefore ans is 3 
Ref: https://gateoverflow.in/88046/b-tree-b-tree

Answer 3

NUMBER OF LEVELS = CIEL (log₁₁14000)