The B-tree is a generalization of a binary search tree  in which a node can have more than two children .The B-tree is optimized for systems that read and write large blocks of data.It has following properties

Insertion in B-Tree

The insertion in b-tree is done such that they satisfy all the properties listed above.


Consider a B-Tree of order 4 and we need to insert 5,3,21,9,1,13,2,7,10,12,4,8.Each node can have at most 4 pointers and 3 keys (M-1) or  at least 2 pointers and 1 key.Since it is a binary search tree the keys of left subtree will be less than the root value and keys of right subtree will be greater than root value.

Screen Shot 2014-05-29 at 3.54.56 PM

Fig 1 : Insertion in B-Tree



Screen Shot 2014-05-29 at 3.55.47 PM

Fig 2 : Insert 1,13,2



Screen Shot 2014-05-29 at 3.56.29 PM

Fig 3 : Insert 7,10,12


Screen Shot 2014-05-29 at 4.26.04 PM

Fig 4 : Insert 4,8


Short URL: http://tinyit.cc/edff9d
Author: Cusp2207 on May 29, 2014
Category: Computer Science, Data Structures
1 response to “B-Trees”
  1. Chef Melinda says:

    Appreciate your efforts in explaining difficult concepts in an easy way

Leave a Reply

Last articles