B+ Tree Implementation

🚀 Features

🎬 Demo

📋 Table of Contents

🏃 Quick Start

#include <bptree/bptree.hpp>
#include <iostream>
int main() {
 // Create B+ tree with internal node limit 4, leaf node limit 3
 bptree::BPTree tree(4, 3);
 
 // Insert student data
 FILE* file = fopen("DBFiles/101.txt", "w");
 fprintf(file, "Wilson Sarah 22 89\n");
 tree.insert(101, file);
 fclose(file);
 
 // Search for data
 tree.search(101); // Output: "Hurray!! Key FOUND"
 
 // Display tree structure
 tree.display(tree.getRoot());
 
 return 0;
}

🔨 Building

Prerequisites

Build Instructions

Option 1: Using Makefile (Recommended)

# Clone the repository
git clone <your-repo-url>
cd bplus-tree
# Build the project
make
# Run the demo
./bptree_demo
# Run example program
./basic_usage
# Run comprehensive tests
make test

Option 2: Using CMake

# Create build directory
mkdir build && cd build
# Configure and build
cmake ..
cmake --build . --parallel
# Run tests
ctest --verbose

Build Targets

📖 Usage

Database Schema

Basic Operations

#include <bptree/bptree.hpp>
// Create tree with custom parameters
bptree::BPTree tree(4, 3); // internal_limit=4, leaf_limit=3
// Insert student record
FILE* studentFile = fopen("DBFiles/12345.txt", "w");
fprintf(studentFile, "Smith Michael 21 92\n");
tree.insert(12345, studentFile);
fclose(studentFile);
// Search for student
tree.search(12345); // Displays: "Hurray!! Key FOUND"
// Delete student record
tree.removeKey(12345);
// Display tree structures
tree.display(tree.getRoot()); // Hierarchical view
tree.seqDisplay(tree.getRoot()); // Sequential leaf traversal

Advanced Usage

// Create multiple trees for different tables
bptree::BPTree studentsTree(4, 3);
bptree::BPTree coursesTree(6, 5); // Different capacity
// Batch operations
std::vector<int> rollNumbers = {101, 102, 103, 104, 105};
for (int rollNo : rollNumbers) {
 std::string filename = "DBFiles/" + std::to_string(rollNo) + ".txt";
 FILE* file = fopen(filename.c_str(), "w");
 fprintf(file, "Student_%d 21 88\n", rollNo);
 studentsTree.insert(rollNo, file);
 fclose(file);
}

🌳 B+ Tree Theory

Core Properties

Key Characteristics

Implementation Details

Node Structure

class Node {
 bool isLeaf;
 std::vector<int> keys;
 Node* ptr2next; // Links leaf nodes for sequential access
 
 union ptr {
 std::vector<Node*> ptr2Tree; // Internal node children
 std::vector<FILE*> dataPtr; // Leaf node data pointers
 } ptr2TreeOrData;
};

Design Decisions

B+ Tree Properties

Node Capacity Constraints

Search Algorithm

void search(int key) {
 Node* cursor = root;
 
 // Navigate to leaf node
 while (!cursor->isLeaf) {
 int idx = upper_bound(cursor->keys.begin(), 
 cursor->keys.end(), key) 
 - cursor->keys.begin();
 cursor = cursor->ptr2TreeOrData.ptr2Tree[idx];
 }
 
 // Search in leaf node
 int idx = lower_bound(cursor->keys.begin(), 
 cursor->keys.end(), key) 
 - cursor->keys.begin();
 
 if (idx < cursor->keys.size() && cursor->keys[idx] == key) {
 // Key found - display data
 displayData(cursor->ptr2TreeOrData.dataPtr[idx]);
 }
}

Insertion Algorithm

Insertion Strategies Comparison

Algorithm Steps

Insertion Example

void insert(int key, FILE* filePtr) {
 if (root == nullptr) {
 // Create root node
 root = new Node();
 root->isLeaf = true;
 root->keys.push_back(key);
 root->ptr2TreeOrData.dataPtr.push_back(filePtr);
 return;
 }
 
 // Find leaf node for insertion
 Node* leaf = findLeafNode(key);
 
 if (leaf->keys.size() < maxLeafNodeLimit) {
 // Simple insertion
 insertIntoLeaf(leaf, key, filePtr);
 } else {
 // Split required
 splitLeafAndInsert(leaf, key, filePtr);
 }
}

📚 API Reference

BPTree Class

Constructors

BPTree(); // Default: internal=4, leaf=3
BPTree(int degreeInternal, int degreeLeaf); // Custom configuration

Core Operations

void insert(int key, FILE* filePtr); // Insert key-data pair
void search(int key); // Search and display data
void removeKey(int key); // Delete key from tree

Display Operations

void display(Node* cursor); // Hierarchical tree view
void seqDisplay(Node* cursor); // Sequential leaf traversal

Utility Methods

Node* getRoot(); // Get root node
int getMaxIntChildLimit(); // Get internal node capacity
int getMaxLeafNodeLimit(); // Get leaf node capacity
void setRoot(Node* ptr); // Set root node

Node Structure

class Node {
public:
 bool isLeaf; // Node type flag
 std::vector<int> keys; // Sorted keys
 Node* ptr2next; // Next leaf node (for leaves)
 
 union ptr {
 std::vector<Node*> ptr2Tree; // Child pointers (internal)
 std::vector<FILE*> dataPtr; // Data pointers (leaf)
 } ptr2TreeOrData;
 
 Node(); // Constructor
 ~Node(); // Destructor with cleanup
};

🧪 Testing

Running Tests

# Run comprehensive test suite
make test
# Or run directly
./tests/test_suite.sh
# Run with verbose output
./tests/test_suite.sh --verbose
# Clean build and test
./tests/test_suite.sh --clean-build

🤝 Contributing

📄 License