B+ TREE

B+ Tree is a B-Tree of order m which satisfy following condition.

1. All leaf node are at same level.

2. All intermediate nodes except the roots can have at most 'm' non - empty children's and can have as few as integer value of m/2.

3. Each node of B-Tree has are less key than its number of children and keys are inserted in a search tree fashion.

4. The root of B-Tree can have at most 'm' non-empty children and can have as few as two if root is alone.

5. Each intermediate key has a similar copy in its successor or predecessor leaf.

6. All leaf are connected through a direct link in a link list fashion.

Example:

PROPERTIES:

If Order is m then

Max children = m

Min children = 2

Max Keys = m - 1

Min Keys =1

Note: If number of keys > (m -1) than overflow occur

EXAMPLE:

Create B+tree for following of order 5 i.e m =5

a , g , f , b , k , d , h , m , x , c , l , r , n , t , u.

Here :

If Order is 5 then

Max children = 5

Min children = 2

Max Keys = 5 - 1 = 4

Min Keys =1

INSERT a :

INSERT g :

INSERT f :

INSERT b :

INSERT k : overflow occur

Now we insert k we see here overflow occur because we have m=5 so each node have at most m-1 children's, so here for inserting k we need to split it  like ( a,b,f,g,k ) , m/2 i.e 5/2=2 split from index 2 which is f.

So one copy of f will foreword to successor node and one copy is in predecessor node. as show in the figure.

INSERT d :

INSERT h :

INSERT m : overflow occur

Here we need to split the node right of f because m belongs to right side of f , so  find mid from ( f, g , h , k , m ) we get h so one copy of h is foreword to successor and one copy to predecessor we get

INSERT x : 

INSERT c : 

INSERT l : overflow occur

Here we need to split the node right of f because l belongs to right side of h , so  find mid from ( h, k , l , m , x) we get l so one copy of l is foreword to successor and one copy to predecessor we get

INSERT r :

INSERT n : overflow occur

Here we need to split the node right of l because n belongs to right side of l , so  find mid from ( l, m , n , r , x) we get n so one copy of n is foreword to successor and one copy to predecessor we get

INSERT t : 

INSERT u : overflow occur

Here we need to split the node right of n because u belongs to right side of n , so  find mid from (n , r , t ,u , x) we get t so one copy of t is foreword to successor and one copy to predecessor we get

Here overflow also occur in root node so perform same procedure as do in above. First find mid from ( f , h , l , n , t ) so mid is l Now split it in following manner. Not no copy of mid i.e l will foreword to predecessor because l become a root node.