2,512 views
0 votes
0 votes
if we use 3 key ,4 pointer nodes. how many different B tree are there when the data file has 6 records.?? ...kindly explain with a descriptive figure

1 Answer

0 votes
0 votes

structure of b-tree

b-tree node structure
p1 key1, data recordpointer p2


in this p = child pointer ....///key=keys....///record = data record pointer
note:- every node has same structure whether it is root,internal,leaf...but in leaf node child pointers r null,
now order of b-tree is maximum no. of child pointers a node can have .
lets say 'p' is order
order of root = min. 2  to max. 'p'.....///// keys/record pointers= 1 to p-1
  .........internal = min ceil p/2 to p/////keys/record pointers= ceil (p-1)/2 to m-1
 leaf ==null child pointers/////keys/record pointers= ceil (p-1)/2 to  p-1.
keys = record pointers for any node.
any node in b-tree has data record pointers 
note :- all leaf nodes are at same level in b-tree considered in DBMS for indexing..
we cannot disribute 6 records in all nodes..
here we have to disribute them only in leaf nodes..

there are only 2 ways to disribute...given below 

4 pointer node..3 key....doesn't mean that every node  should be completely filled..//root can have record or cannot have record it is not necessary in btree

root can have min..2 child pointers and 1 key..max- 4 child here

leaf can have minimum..2 keys& records.. and maximum 3 keys and records///child pointers are zero in leaf node..

edited by

Related questions

1 votes
1 votes
1 answer
2
manisha11 asked Jun 7, 2019
449 views
In case of B Trees we split a node on insertion in case of overflow,is there any possible case in which this may lead to underflow also? as a key is promoted to parent th...
0 votes
0 votes
1 answer
3
aditi19 asked Nov 23, 2018
407 views
can anyone share some good resources fot B+ tree deletion?
0 votes
0 votes
0 answers
4
Shivangi Parashar 2 asked Oct 22, 2018
315 views