B+ Tree Java Implementation

B+ Tree Java Implementation


 A Little about B+ Tree:

  B+Tree is an extension of the B-Tree Search which itself is an  extension of Binary Search Tree. Rather than having a single element  in the node, B+Tree has multiple keys in a single level. Also, unlike  other trees B Tree and B+Tree follow the bottom-up approach of  progression. There is an order associated with the B+Tree which is the  maximum number of children a node can hold. Beyond which the node  splits through its middle element. Just like other Data Structures, we  can initialize,insert,delete and search the tree.

The Structure of B+Tree:
This advance Data Structure obeys the following rules: 
  1. Each leaf node is of the form :
    <<K1, D1>, <K2, D2>, ….., <Kc-1, Dc-1>, Pnext>
    where c <= b and each Di is a data pointer (i.e points to actual record in the disk whose key value is Ki or to a disk file block containing that record) and, each Ki is a key value and, Pnext points to next leaf node in the B+ tree (see diagram II for reference).
  2. Every leaf node has : K1 < K2 < …. < Kc-1, c <= b
  3. Each leaf node has at least \ceil(b/2) values.
  4. All leaf nodes are at same level.
B+Tree Operations:
  • Insertion:

Pseudo code:
  1. When insert node is overfull, check adjacent sibling.
  2. If adjacent sibling is not full, move a dictionary pair from overfull node, via parent, to nonfull adjacent sibling.
  3. If adjacent sibling is full, split overfull node, adjacent full node, and in-between pair from parent to get three nodes with floor((2m – 2)/3), floor((2m – 1)/3), floor(2m/3) pairs plus two additional pairs for insertion into parent.

  • Deletion:

Pseudo code:
  1. When combining, must combine 3 adjacent nodes and 2 in-between pairs from parent.
    1. Total # pairs involved = 2 * floor((2m-2)/3) + [floor((2m-2)/3) – 1] + 2.
    2. Equals 3 * floor((2m-2)/3) + 1.
  2. Combining yields 2 nodes and a pair that is to be inserted into the parent.
    1. m mod 3 = 1 => nodes have m – 1 pairs each.
    2. m mod 3 = 0  => one node has m – 1 pairs and the other has m – 2.
    3. m mod 3 = 2 => nodes have m – 2 pairs each.
  • Searching:



In this project, I make use of primitive Data types to create most of the B+Tree operations and functionalities. The programming language used for this program is Java.
Detailed Implementation of this program can be found here.