B Tree in DSA
Introduction
B tree is a self balancing tree which can have two or
more than two child nodes. Elements in the nodes are sorted in order. In B tree
seaching, insertions and deletions are done in logarthmic time. B tree is
suitable for storage systems which needs to read and write large blocks of
data. B tree is used in databases and file systems.
B tree has order denoted by m; order of B tree shows the number of children a
node can have and the number of keys each node can have. If value of m is 5
then a node can have only 5 children and 5 -1 = 4 keys.
Properties of B tree according to Kunth
- Each node can have at most m
children
- Each internal node (non-leaf
node) has at least ceil(m/2) child nodes
- If the root is not leaf then it
has at least two children
- Non-leaf node with n children
has n-1 keys
- All the leaves are in the same
level
For example..Â
Create B tree of order (m) =5 from given data: 33 44 55 22 17 18
19 27 78 88 91 92 57 64 58 75 59 76
