GitHub: https://github.com/lkkhwhb/BTree
This repository contains a C++ implementation of a B-Tree, a self-balancing search tree commonly used in databases and filesystems. The project demonstrates core data structure concepts, including nodes, recursion, dynamic memory management, and tree traversal.
A B-Tree is a self-balancing search tree that maintains sorted data and allows efficient search, insertion, and traversal operations. Unlike a binary search tree (BST), where each node has at most 2 children, a B-Tree node can have multiple keys and multiple children, making it suitable for large datasets and disk-based storage systems.
-
Minimum Degree (t): Determines the minimum and maximum number of keys per node.
- Minimum keys in a non-root node:
t - 1 - Maximum keys in a node:
2t - 1 - Minimum children for a non-leaf node:
t - Maximum children:
2t
- Minimum keys in a non-root node:
-
Node: Container for keys and child pointers.
-
Leaf Node: Node with no children. All leaf nodes are at the same level.
-
Internal Node: Node that is not a leaf; it has child pointers.
- All leaf nodes are at the same depth, ensuring balance.
- Keys within a node are always sorted in ascending order.
- Each child subtree contains keys in a range defined by the parent’s keys.
- Node splitting ensures the height of the tree remains low, guaranteeing O(log n) operations.
Each node contains:
- Array of keys (size ≤
2t - 1) - Array of child pointers (size ≤
2t) - Number of keys currently stored
- Leaf indicator
Example (t = 3):
Keys: [10 | 20 | 30]
Children: C0 C1 C2 C3
- Traverse recursively to the correct child node.
- If a node is full, split the node and move the middle key up.
- Insert the key into a non-full leaf node.
- Node splitting ensures balance is maintained automatically.
- Start at the root and compare with keys.
- Traverse the appropriate child based on the key range.
- Repeat recursively until the key is found or a leaf is reached.
- Time complexity: O(log n).
Inserting keys: 10, 20, 5, 6, 12, 30, 7, 17 (t = 3):
B-Tree Structure (ASCII Diagram):
[10 20]
/ | \
[5 6 7] [12 17] [30]
- Root node:
[10 20] - Left child:
[5 6 7] - Middle child:
[12 17] - Right child:
[30]
Traversal (in-order) gives sorted keys:
5 6 7 10 12 17 20 30
Searching for 6 finds it in the leftmost child.
- Configurable minimum degree (
t) - Insertion of keys
- Search for keys
- In-order traversal (prints keys in sorted order)
- Modular C++ classes and dynamic memory usage
BTree/
├── include/
│ └── BTree.h # Class declarations
├── src/
│ └── BTree.cpp # Function definitions
└── main.cpp # Demonstration of insertion, traversal, and search
#include <iostream>
#include "include/BTree.h"
using namespace std;
int main() {
BTree t(3); // Minimum degree 3
t.insert(10);
t.insert(20);
t.insert(5);
t.insert(6);
t.insert(12);
t.insert(30);
t.insert(7);
t.insert(17);
cout << "Traversal of the tree:" << endl;
t.traverse();
int key = 6;
cout << "\nSearching for " << key << "..." << endl;
if (t.search(key))
cout << "Found " << key << endl;
else
cout << key << " not found" << endl;
return 0;
}Expected Output:
Traversal of the tree:
5 6 7 10 12 17 20 30
Searching for 6...
Found 6
- Open terminal or PowerShell in the project folder.
- Compile the project:
g++ main.cpp src/BTree.cpp -o BTreeApp- Run the executable:
.\BTreeApp.exe- Self-Balancing Trees: Node splitting maintains balance.
- Dynamic Memory Management: Nodes and keys are allocated using pointers.
- Recursion: Traversal, search, and insertion implemented recursively.
- Data Structures: Arrays, pointers, and hierarchical tree structure.
- Algorithmic Efficiency: Search and insertion operate in O(log n).
-
Wikipedia – B-Tree
A comprehensive overview of B-Trees, including properties, operations, and applications.
https://en.wikipedia.org/wiki/B-tree -
GeeksforGeeks – Introduction to B-Trees
A comprehensive overview of B-Trees, including their properties and applications.
https://www.geeksforgeeks.org/introduction-of-b-tree-2/ -
GeeksforGeeks – B-Tree Implementation in C++
A detailed guide on implementing B-Trees in C++, covering class structures and operations.
https://www.geeksforgeeks.org/cpp/b-tree-implementation-in-cpp/ -
TutorialsPoint – B-Trees
An explanation of B-Trees, their properties, and their use cases in data storage.
https://www.tutorialspoint.com/data_structures_algorithms/b_trees.htm -
Programiz – B-Tree Data Structure
A beginner-friendly guide to understanding B-Trees and their operations.
https://www.programiz.com/dsa/b-tree -
DataQuest – How to Implement a B-Tree Data Structure
A step-by-step tutorial on implementing B-Trees, including code examples.
https://www.dataquest.io/blog/b-tree-data-structure/ -
Let's Build a Simple Database – Introduction to the B-Tree
A practical guide on building a database with B-Trees, focusing on their role in indexing.
https://cstack.github.io/db_tutorial/parts/part7.html -
KhaledAshrafH/B-Tree – GitHub Repository
A C++ implementation of a B-Tree with template classes and dynamic memory usage.
https://github.com/KhaledAshrafH/B-Tree -
Kronuz/cpp-btree – GitHub Repository
A modern C++ B-Tree container library inspired by Google's B-Tree implementation.
https://github.com/Kronuz/cpp-btree -
Apache Directory – B-Tree Basics
An explanation of B-Trees and their use in directory services and databases.
https://directory.apache.org/mavibot/user-guide/1.1-btree-basics.html -
Medium – Understanding B-Trees: An In-Depth Guide
A detailed article discussing the inner workings and applications of B-Trees.
https://medium.com/@MakeComputerScienceGreatAgain/understanding-b-trees-an-in-depth-guide-dcd77f5e995e