How to construct a B+ tree with example

A B+ tree contains n-1 search key values K1K2…….Kn-1 and have n pointers.  

In a B+ tree the data are ordered  sequentially.  The leaf node may hold up to n pointers and must hold at least N/2 pointers. The root node must hold at least two pointers, unless the tree consists of only one node.  Now we construct a B+ tree. Construct a B+ tree for the following set of key values: (2,3,5,7,11,17,19,23,29,31) Assume that the tree is initially empty and values are added in ascending order. Construct a B+ tree where the pointer number is Four.

Solution:

When a node exceeds n-1 search key value then we split it into two nodes. First node contains (ceiling(n-1)/2) values.  2^nd node contains remaining node. Copy the smallest search key value of the second node to the parent node. Let's start, we know each node has N pointer and has N-1 search key values. In our example pointer number is 4, so the search key value is 4-1=3. So each node has 4 pointers and 3 search key value. The first node is

When we want to put 7 in this node we need to split it.  

Then we put  19 , 23 and split the leaf node. The node is 

Then we put 19, 23 in the leaf node and split the leaf node. 

Then we put 29,31 and split the leaf node but when we split the leaf node at a time we need to split the non leaf node. We split the non leaf node at same rules. 

If you have any question to construct B+ tree, please make sure your comment. We are ready to answer your question. If you don't see the picture clearly, just click over the picture and see the clear picture.