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