B+ Tree

B+ trees offer significant value by providing efficient data retrieval in block-oriented storage applications like file systems and databases. A B+ tree is nothing more than a tree (with a particularly high fanout or order, which we shall refer to as m) that satisfies the following conditions:

• An internal node (nodes that aren't the root or leaves) must have a number of children d such that ⌈m/2⌉ ≤ d ≤ m
• The root node may have at least 2 children and up to m children
• The number of keys k that an internal node may carry is ⌈m/2⌉ - 1 ≤ k ≤ m - 1
• Leaf nodes have no children, but the number of dictionary pairs k that a single leaf node may carry is ⌈m/2⌉ - 1 ≤ k ≤ m - 1

A B+ tree is similar to a B tree except that all the dictionary pairs lie in the leaf nodes.

Getting Started

This program was developed, compiled, run, and tested only with Java Development Kit 1.8.0_201 (Java 8). To compile the program, run the following command:

$ javac bplustree.java

To execute the program, run the following command:

$ java bplustree <input_file>

Running

For the program to work properly, ensure that the input_file follows the format:

• The first line must contain Initialize(m) where m is the order of the B+ tree
• All subsequent lines may contain only the following operations:
  1. Insert(key, value) where key is an integer and value is a floating point number
  2. Delete(key) where key is the key of the dictionary pair you would like to delete
  3. Search(key) where key is the key of the dictionary pair whose value you would like to find
  4. Search(lowerBound, upperBound) where all values of dictionary pairs whose keys fall within lowerBound ≤ key ≤ upperBound will be recorded

Output for each search query will be recorded within a file titled output_file.txt.

Sample Input File

Initialize(3)
Insert(21, 0.3534)
Insert(108, 31.907)
Insert(56089, 3.26)
Insert(234, 121.56)
Insert(4325, -109.23)
Delete (108)
Search(234)
Insert(102, 39.56)
Insert(65, -3.95)
Delete (102)
Delete (21)
Insert(106, -3.91)
Insert(23, 3.55)
Search(23, 99)
Insert(32, 0.02)
Insert(220, 3.55)
Delete (234)
Search(65)

Sample Output File

121.56
3.55, -3.95
-3.95

Authors

• Shandy Sulen