Open In App

C++ Program to Implement B+ Tree

Last Updated : 23 Jul, 2025
Suggest changes
Share
Like Article
Like
Report

A B+ Tree is an advanced data structure that extends the B-tree by adding a linked list of leaf nodes. This structure is widely used in databases and file systems to allow efficient insertion, deletion, and search operations. In this article, we will learn how to implement the B+ Tree in C++ along with its basic operations.

What is a B+ Tree?

A B+ Tree is a self-balancing tree data structure that maintains sorted data and allows for efficient insertion, deletion, and search operations. It differs from a B-tree in the following ways:

  • All values are at the leaf level.
  • Leaf nodes are linked, making range queries and sequential access more efficient.

Properties of B+ Trees

A B+ tree of order m has the following properties:

  • All leaf nodes are at the same level.
  • All internal nodes except the root have at least ⌈m/2⌉ children. The root has at least two children if it is not a leaf node.
  • All internal nodes have at most m children.
  • Each internal node with k children contains k-1 keys.
  • All leaf nodes contain between ⌈m/2⌉ and m keys.
  • The keys in leaf nodes are sorted, and each leaf node has a pointer to the next leaf node.

Implementation of B+ Tree in C++

A B+ tree consists of internal nodes and leaf nodes. Internal nodes store keys and pointers to child nodes, while leaf nodes store keys and pointers to the actual data records.

Representation of B+ Tree in C++

The following diagram represents the structure of a B+ tree:

BplusTree
B+ Tree

To represent a B+ Tree in C++, we will use a classes that contains the required definition: a struct to represent each node, member function to provide basic functionality. To keep the B+ tree generic, we will use templates so that it can store multiple data types.

template <typename T> class BPlusTree { public: struct Node { bool isLeaf; vector<T> keys; vector<Node*> children; Node* next; };

Here:

  • isLeaf: indicates whether the node is a leaf node.
  • keys: stores the keys in the node.
  • children: stores pointers to child nodes (for internal nodes).
  • next: points to the next leaf node (used only for leaf nodes).

Basic Operations of B+ Tree in C++

Following are some of the basic operations of B+ tree that are required to manipulate its elements:

Operation Name

Description

Time Complexity

Space Complexity

Insert

Inserts a new element into the B+ tree

O(log n)

O(1)

Delete Node

Removes an element from the B+ tree

O(log n)

O(1)

Search

Searches for an element in the B+ tree

O(log n)

O(1)

Range Query

Retrieves all elements within a given range from the B+ Tree

O(log n + k)

O(k)

Split Child

Splits a full child node during insertion

O(1)

O(1)

Here n represents the number of nodes in the tree and k represents number of elements in the range for a range query.

Implementation of Insert Function

  • If the tree is empty, create a new leaf node and insert the key.
  • Otherwise, traverse the tree to find the appropriate leaf node.
  • If the leaf Implementation of Delete Node Functionnode has space, insert the key in the correct position.
  • If the leaf node is full, split it into two nodes and distribute the keys.
  • If splitting propagates to internal nodes, continue splitting up the tree.
  • If the root splits, create a new root with two children.

Implementation of Delete Node Function

  • Find the leaf node containing the key to be deleted.
  • Remove the key from the leaf node.
  • If the leaf node has too few keys, borrow from a sibling or merge with a sibling.
  • If merging propagates to internal nodes, continue merging up the tree.
  • If the root has only one child after merging, make that child the new root.

Implementation of Search Function

  • Start from the root node.
  • Traverse internal nodes by comparing keys and following the appropriate child pointer.
  • Reach a leaf node and search for the key.
  • Return the result of the search.

Implementation of Range Query Function

  • Find the leaf node containing the lower bound of the range.
  • Traverse the leaf nodes using the next pointers until the upper bound is reached.
  • Collect all keys within the range.

Implementation of Split Child Function

  • Create a new node to hold half of the keys from the full node.
  • If the node being split is an internal node:
    • Move the middle key to the parent node.
    • Distribute the keys greater than the middle key to the new node.
    • Distribute the corresponding child pointers to the new node.
  • If the node being split is a leaf node:
    • Copy the middle key to the parent node (don't remove it from the leaf).
    • Distribute half of the keys to the new node.
    • Update the "next" pointer of the original node to point to the new node.
    • Update the "next" pointer of the new node to point to the original node's old "next".
  • Insert the new node as a child of the parent node, right after the original node.
  • Adjust the parent node's key and child pointer arrays to accommodate the new key and child.

C++ Program to Implement B+ Tree

The following program demonstrates the implementation of B+ tree in C++:

C++ 
// C++ Program to Implement B+ Tree #include <algorithm> #include <iostream> #include <vector> using namespace std; // B plus tree class template <typename T> class BPlusTree { public:  // structure to create a node  struct Node {  bool isLeaf;  vector<T> keys;  vector<Node*> children;  Node* next;  Node(bool leaf = false)  : isLeaf(leaf)  , next(nullptr)  {  }  };  Node* root;  // Minimum degree (defines the range for the number of  // keys)  int t;  // Function to split a child node  void splitChild(Node* parent, int index, Node* child);  // Function to insert a key in a non-full node  void insertNonFull(Node* node, T key);  // Function to remove a key from a node  void remove(Node* node, T key);  // Function to borrow a key from the previous sibling  void borrowFromPrev(Node* node, int index);  // Function to borrow a key from the next sibling  void borrowFromNext(Node* node, int index);  // Function to merge two nodes  void merge(Node* node, int index);  // Function to print the tree  void printTree(Node* node, int level); public:  BPlusTree(int degree): root(nullptr), t(degree){}  void insert(T key);  bool search(T key);  void remove(T key);  vector<T> rangeQuery(T lower, T upper);  void printTree(); }; // Implementation of splitChild function template <typename T> void BPlusTree<T>::splitChild(Node* parent, int index,  Node* child) {  Node* newChild = new Node(child->isLeaf);  parent->children.insert(  parent->children.begin() + index + 1, newChild);  parent->keys.insert(parent->keys.begin() + index,  child->keys[t - 1]);  newChild->keys.assign(child->keys.begin() + t,  child->keys.end());  child->keys.resize(t - 1);  if (!child->isLeaf) {  newChild->children.assign(child->children.begin()  + t,  child->children.end());  child->children.resize(t);  }  if (child->isLeaf) {  newChild->next = child->next;  child->next = newChild;  } } // Implementation of insertNonFull function template <typename T> void BPlusTree<T>::insertNonFull(Node* node, T key) {  if (node->isLeaf) {  node->keys.insert(upper_bound(node->keys.begin(),  node->keys.end(),  key),  key);  }  else {  int i = node->keys.size() - 1;  while (i >= 0 && key < node->keys[i]) {  i--;  }  i++;  if (node->children[i]->keys.size() == 2 * t - 1) {  splitChild(node, i, node->children[i]);  if (key > node->keys[i]) {  i++;  }  }  insertNonFull(node->children[i], key);  } } // Implementation of remove function template <typename T> void BPlusTree<T>::remove(Node* node, T key) {  // If node is a leaf  if (node->isLeaf) {  auto it = find(node->keys.begin(), node->keys.end(),  key);  if (it != node->keys.end()) {  node->keys.erase(it);  }  }  else {  int idx = lower_bound(node->keys.begin(),  node->keys.end(), key)  - node->keys.begin();  if (idx < node->keys.size()  && node->keys[idx] == key) {  if (node->children[idx]->keys.size() >= t) {  Node* predNode = node->children[idx];  while (!predNode->isLeaf) {  predNode = predNode->children.back();  }  T pred = predNode->keys.back();  node->keys[idx] = pred;  remove(node->children[idx], pred);  }  else if (node->children[idx + 1]->keys.size()  >= t) {  Node* succNode = node->children[idx + 1];  while (!succNode->isLeaf) {  succNode = succNode->children.front();  }  T succ = succNode->keys.front();  node->keys[idx] = succ;  remove(node->children[idx + 1], succ);  }  else {  merge(node, idx);  remove(node->children[idx], key);  }  }  else {  if (node->children[idx]->keys.size() < t) {  if (idx > 0  && node->children[idx - 1]->keys.size()  >= t) {  borrowFromPrev(node, idx);  }  else if (idx < node->children.size() - 1  && node->children[idx + 1]  ->keys.size()  >= t) {  borrowFromNext(node, idx);  }  else {  if (idx < node->children.size() - 1) {  merge(node, idx);  }  else {  merge(node, idx - 1);  }  }  }  remove(node->children[idx], key);  }  } } // Implementation of borrowFromPrev function template <typename T> void BPlusTree<T>::borrowFromPrev(Node* node, int index) {  Node* child = node->children[index];  Node* sibling = node->children[index - 1];  child->keys.insert(child->keys.begin(),  node->keys[index - 1]);  node->keys[index - 1] = sibling->keys.back();  sibling->keys.pop_back();  if (!child->isLeaf) {  child->children.insert(child->children.begin(),  sibling->children.back());  sibling->children.pop_back();  } } // Implementation of borrowFromNext function template <typename T> void BPlusTree<T>::borrowFromNext(Node* node, int index) {  Node* child = node->children[index];  Node* sibling = node->children[index + 1];  child->keys.push_back(node->keys[index]);  node->keys[index] = sibling->keys.front();  sibling->keys.erase(sibling->keys.begin());  if (!child->isLeaf) {  child->children.push_back(  sibling->children.front());  sibling->children.erase(sibling->children.begin());  } } // Implementation of merge function template <typename T> void BPlusTree<T>::merge(Node* node, int index) {  Node* child = node->children[index];  Node* sibling = node->children[index + 1];  child->keys.push_back(node->keys[index]);  child->keys.insert(child->keys.end(),  sibling->keys.begin(),  sibling->keys.end());  if (!child->isLeaf) {  child->children.insert(child->children.end(),  sibling->children.begin(),  sibling->children.end());  }  node->keys.erase(node->keys.begin() + index);  node->children.erase(node->children.begin() + index  + 1);  delete sibling; } // Implementation of printTree function template <typename T> void BPlusTree<T>::printTree(Node* node, int level) {  if (node != nullptr) {  for (int i = 0; i < level; ++i) {  cout << " ";  }  for (const T& key : node->keys) {  cout << key << " ";  }  cout << endl;  for (Node* child : node->children) {  printTree(child, level + 1);  }  } } // Implementation of printTree wrapper function template <typename T> void BPlusTree<T>::printTree() {  printTree(root, 0); } // Implementation of search function template <typename T> bool BPlusTree<T>::search(T key) {  Node* current = root;  while (current != nullptr) {  int i = 0;  while (i < current->keys.size()  && key > current->keys[i]) {  i++;  }  if (i < current->keys.size()  && key == current->keys[i]) {  return true;  }  if (current->isLeaf) {  return false;  }  current = current->children[i];  }  return false; } // Implementation of range query function template <typename T> vector<T> BPlusTree<T>::rangeQuery(T lower, T upper) {  vector<T> result;  Node* current = root;  while (!current->isLeaf) {  int i = 0;  while (i < current->keys.size()  && lower > current->keys[i]) {  i++;  }  current = current->children[i];  }  while (current != nullptr) {  for (const T& key : current->keys) {  if (key >= lower && key <= upper) {  result.push_back(key);  }  if (key > upper) {  return result;  }  }  current = current->next;  }  return result; } // Implementation of insert function template <typename T> void BPlusTree<T>::insert(T key) {  if (root == nullptr) {  root = new Node(true);  root->keys.push_back(key);  }  else {  if (root->keys.size() == 2 * t - 1) {  Node* newRoot = new Node();  newRoot->children.push_back(root);  splitChild(newRoot, 0, root);  root = newRoot;  }  insertNonFull(root, key);  } } // Implementation of remove function template <typename T> void BPlusTree<T>::remove(T key) {  if (root == nullptr) {  return;  }  remove(root, key);  if (root->keys.empty() && !root->isLeaf) {  Node* tmp = root;  root = root->children[0];  delete tmp;  } } // Main function to test the B+ Tree implementation int main() {  BPlusTree<int> tree(3);  // Insert elements  tree.insert(10);  tree.insert(20);  tree.insert(5);  tree.insert(15);  tree.insert(25);  tree.insert(30);  cout << "B+ Tree after insertions:" << endl;  tree.printTree();  // Search for a key  int searchKey = 15;  cout << "\nSearching for key " << searchKey << ": "  << (tree.search(searchKey) ? "Found" : "Not Found")  << endl;  // Perform a range query  int lower = 10, upper = 25;  vector<int> rangeResult = tree.rangeQuery(lower, upper);  cout << "\nRange query [" << lower << ", " << upper  << "]: ";  for (int key : rangeResult) {  cout << key << " ";  }  cout << endl;  // Remove a key  int removeKey = 20;  tree.remove(removeKey);  cout << "\nB+ Tree after removing " << removeKey << ":"  << endl;  tree.printTree();  return 0; }

Output
B+ Tree after insertions: 15 5 10 20 25 30 Searching for key 15: Found Range query [10, 25]: 10 20 25 B+ Tree after removing 20: 15 5 10 25 30

Related Articles:


T
techwiz47
Article Tags :

Explore

Lightbox