Multilevel indexing with B+tree in C++

Question

The issue arises when I initiate the program and opt to display all the books; they appear correctly. However, when I attempt to search for or delete a book, it claims that the book is not found, despite the ID being correct. Interestingly, these functions work seamlessly with newly inserted books but encounter difficulties with those already present in the CSV file.

#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <ctime>
#include <map>
#include <algorithm>
#include<sstream>

using namespace std;

struct Book {
    int ID;
    char Title[300];
    int Year;
    char Authors[512];
    int Citations;
    char Update[20];
    char Abstract[1024];
};

struct BPlusTreeNode {
    vector<int> keys;
    vector<Book> values;
    BPlusTreeNode* parent;
    vector<BPlusTreeNode*> children;

    BPlusTreeNode() : parent(nullptr) {}
};

class BPlusTree {
private:
    static const int ORDER = 4; 
    BPlusTreeNode* root;
    map<int, Book> bookIndex;

public:
    
    BPlusTree() : root(nullptr) {}

    ~BPlusTree() {
        deleteTree(root);
    }

    void insert(int key, const Book& value) {
        if (!root) {
            root = new BPlusTreeNode();
            root->keys.push_back(key);
            root->values.push_back(value);
            bookIndex[key] = value;
        } else {
            insertInternal(root, key, value);
        }
    }

    bool search(int key, Book& result) const {
    return searchInternal(root, key, result);
    }


    bool update(int key, int newCitations, int newYear, const char* newTitle) {
        return updateInternal(root, key, newCitations, newYear, newTitle);
    }

    bool remove(int key) {
        return removeInternal(root, key);
    }
    const std::map<int, Book>& getBookIndex() const {
        return bookIndex;
    }
    
    std::map<int, Book>& getBookIndex() {
        return bookIndex;
    }
    
private:
    
    void insertInternal(BPlusTreeNode* node, int key, const Book& value) {
        if (node->children.empty()) { 
            insertIntoLeaf(node, key, value);
            if (node->keys.size() > ORDER - 1) {
                splitLeaf(node);
            }
        } else { 
            int childIndex = findChildIndex(node, key);
            insertInternal(node->children[childIndex], key, value);
            if (node->keys.size() > ORDER - 1) {
                splitInternal(node);
            }
        }
    }

    void insertIntoLeaf(BPlusTreeNode* node, int key, const Book& value) {
    auto it = lower_bound(node->keys.begin(), node->keys.end(), key);

    int index = it - node->keys.begin();
    node->keys.insert(it, key);
    node->values.insert(node->values.begin() + index, value);
    bookIndex[key] = value;
}


    void splitLeaf(BPlusTreeNode* node) {
        int splitIndex = node->keys.size() / 2;
        BPlusTreeNode* newLeaf = new BPlusTreeNode();
        newLeaf->keys.assign(node->keys.begin() + splitIndex, node->keys.end());
        newLeaf->values.assign(node->values.begin() + splitIndex, node->values.end());
        node->keys.erase(node->keys.begin() + splitIndex, node->keys.end());
        node->values.erase(node->values.begin() + splitIndex, node->values.end());

        if (node->parent) {
            BPlusTreeNode* newParent = node->parent;
            int newIndex = findChildIndex(newParent, newLeaf->keys[0]);
            newParent->keys.insert(newParent->keys.begin() + newIndex, newLeaf->keys[0]);
            newParent->children.insert(newParent->children.begin() + newIndex + 1, newLeaf);
            newLeaf->parent = newParent;
        } else { 
            BPlusTreeNode* newRoot = new BPlusTreeNode();
            newRoot->keys.push_back(newLeaf->keys[0]);
            newRoot->children.push_back(node);
            newRoot->children.push_back(newLeaf);
            node->parent = newRoot;
            newLeaf->parent = newRoot;
            root = newRoot;
        }
    }

    void splitInternal(BPlusTreeNode* node) {
        int splitIndex = node->keys.size() / 2;
        BPlusTreeNode* newInternal = new BPlusTreeNode();
        newInternal->keys.assign(node->keys.begin() + splitIndex, node->keys.end());
        newInternal->children.assign(node->children.begin() + splitIndex + 1, node->children.end());
        for (auto child : newInternal->children) {
            child->parent = newInternal;
        }
        node->keys.erase(node->keys.begin() + splitIndex, node->keys.end());
        node->children.erase(node->children.begin() + splitIndex + 1, node->children.end());

        if (node->parent) {
            BPlusTreeNode* newParent = node->parent;
            int newIndex = findChildIndex(newParent, newInternal->keys[0]);
            newParent->keys.insert(newParent->keys.begin() + newIndex, newInternal->keys[0]);
            newParent->children.insert(newParent->children.begin() + newIndex + 1, newInternal);
            newInternal->parent = newParent;
        } else { 
            BPlusTreeNode* newRoot = new BPlusTreeNode();
            newRoot->keys.push_back(newInternal->keys[0]);
            newRoot->children.push_back(node);
            newRoot->children.push_back(newInternal);
            node->parent = newRoot;
            newInternal->parent = newRoot;
            root = newRoot;
        }
    }

    int findChildIndex(BPlusTreeNode* node, int key) const {
        auto it = upper_bound(node->keys.begin(), node->keys.end(), key);
        return it - node->keys.begin();
    }
    
    bool searchInternal(BPlusTreeNode* node, int key, Book& result) const {
    if (!node) {
        return false;
    }

    auto it = lower_bound(node->keys.begin(), node->keys.end(), key);

    if (it != node->keys.end() && *it == key) {
        int index = it - node->keys.begin();
        result = node->values[index];
        return true;
    } else if (!node->children.empty()) {
        int childIndex = findChildIndex(node, key);
        return searchInternal(node->children[childIndex], key, result);
    }

    return false;
}



    
    bool updateInternal(BPlusTreeNode* node, int key, int newCitations, int newYear, const char* newTitle) {
    if (!node) {
        return false;
    }

    auto it = lower_bound(node->keys.begin(), node->keys.end(), key);

    if (it != node->keys.end() && *it == key) {
        int index = it - node->keys.begin();
        Book& book = node->values[index];

        if (newCitations != -1) book.Citations = newCitations;
        if (newYear != -1) book.Year = newYear;
        if (newTitle != nullptr) {
            strncpy(book.Title, newTitle, sizeof(book.Title) - 1); 
            book.Title[sizeof(book.Title) - 1] = '\0';  
        }

        return true;
    } else if (!node->children.empty()) {
        int childIndex = findChildIndex(node, key);
        return updateInternal(node->children[childIndex], key, newCitations, newYear, newTitle);
    }

    return false;
}
    
    bool removeInternal(BPlusTreeNode* node, int key) {
    if (!node) {
        return false;
    }

    if (node->children.empty()) { 
        auto it = find(node->keys.begin(), node->keys.end(), key);
        if (it != node->keys.end()) {
            int index = it - node->keys.begin();

            node->keys.erase(it);
            node->values.erase(node->values.begin() + index);
            bookIndex.erase(key);

            adjustParentAfterDelete(node->parent);  

            return true;
        } else {
            return false;
        }
    } else { 
        int childIndex = findChildIndex(node, key);
        return removeInternal(node->children[childIndex], key);
    }
}

    void adjustParentAfterDelete(const BPlusTreeNode* node) {
    if (node->keys.size() < ORDER / 2) {
        BPlusTreeNode* parent = node->parent;
        int childIndex = findChildIndex(parent, node->keys[0]);

        
        if (childIndex > 0 && parent->children[childIndex - 1]->keys.size() > ORDER / 2) {
            borrowFromLeftSibling(parent, childIndex);
        }
       
        else if (childIndex < parent->children.size() - 1 && parent->children[childIndex + 1]->keys.size() > ORDER / 2) {
            borrowFromRightSibling(parent, childIndex);
        }
        
        else if (childIndex > 0) {
            mergeWithLeftSibling(parent, childIndex);
        }
        
        else {
            mergeWithRightSibling(parent, childIndex);
        }
    }

    if (node->parent) {
        adjustParentAfterDelete(node->parent);
    }
    }

    void borrowFromLeftSibling(BPlusTreeNode* parent, int childIndex) {
        
    BPlusTreeNode* node = parent->children[childIndex];
    BPlusTreeNode* leftSibling = parent->children[childIndex - 1];


    int borrowedKey = leftSibling->keys.back();
    Book borrowedValue = leftSibling->values.back();

    parent->keys[childIndex - 1] = borrowedKey;

    node->keys.insert(node->keys.begin(), borrowedKey);
    node->values.insert(node->values.begin(), borrowedValue);

    leftSibling->keys.pop_back();
    leftSibling->values.pop_back();
    }

    void borrowFromRightSibling(BPlusTreeNode* parent, int childIndex) {
        
    BPlusTreeNode* node = parent->children[childIndex];
    BPlusTreeNode* rightSibling = parent->children[childIndex + 1];

    int borrowedKey = rightSibling->keys.front();
    Book borrowedValue = rightSibling->values.front();

    parent->keys[childIndex] = borrowedKey;

    node->keys.push_back(borrowedKey);
    node->values.push_back(borrowedValue);

    rightSibling->keys.erase(rightSibling->keys.begin());
    rightSibling->values.erase(rightSibling->values.begin());
    }

    void mergeWithLeftSibling(BPlusTreeNode* parent, int childIndex) {
    BPlusTreeNode* node = parent->children[childIndex];
    BPlusTreeNode* leftSibling = parent->children[childIndex - 1];

    leftSibling->keys.push_back(parent->keys[childIndex - 1]);
    leftSibling->values.push_back(node->values[0]);

    leftSibling->keys.insert(leftSibling->keys.end(), node->keys.begin(), node->keys.end());
    leftSibling->values.insert(leftSibling->values.end(), node->values.begin(), node->values.end());

    parent->keys.erase(parent->keys.begin() + childIndex - 1);
    parent->children.erase(parent->children.begin() + childIndex);
    
    delete node;
    }

    void mergeWithRightSibling(BPlusTreeNode* parent, int childIndex) {
    BPlusTreeNode* node = parent->children[childIndex];
    BPlusTreeNode* rightSibling = parent->children[childIndex + 1];

    node->keys.push_back(parent->keys[childIndex]);
    node->values.push_back(rightSibling->values[0]);

    node->keys.insert(node->keys.end(), rightSibling->keys.begin(), rightSibling->keys.end());
    node->values.insert(node->values.end(), rightSibling->values.begin(), rightSibling->values.end());

    parent->keys.erase(parent->keys.begin() + childIndex);
    parent->children.erase(parent->children.begin() + childIndex + 1);
    
    delete rightSibling;
    }
    
    void deleteTree(BPlusTreeNode* node) {
        if (node) {
            for (auto child : node->children) {
                deleteTree(child);
            }
            delete node;
        }
    }


};

void csvToBinary(const char* csvFileName, const char* binaryFileName, const char* indexFileName, BPlusTree& bPlusTree) {
    ifstream csvFile(csvFileName);
    ofstream binFile(binaryFileName, ios::binary | ios::trunc);
    ofstream indexFile(indexFileName);

    if (!csvFile.is_open() || !binFile.is_open() || !indexFile.is_open()) {
        cerr << "Error opening files." << endl;
        return;
    }

    const int chunkSize = 1000;

    string line;
    while (getline(csvFile, line)) {
        Book book;
        sscanf(line.c_str(), "%d,%299[^,],%d,%511[^,],%d,%19[^,],%1023[^\n]",
               &book.ID, book.Title, &book.Year, book.Authors, &book.Citations,
               book.Update, book.Abstract);

        binFile.write(reinterpret_cast<char*>(&book), sizeof(Book));

        bPlusTree.getBookIndex()[book.ID] = book;

        indexFile << book.ID << " " << static_cast<std::streamoff>(binFile.tellp()) - sizeof(Book) << endl;


        if (bPlusTree.getBookIndex().size() % chunkSize == 0) {
            bPlusTree = BPlusTree();
        }
    }

    csvFile.close();
    binFile.close();
    indexFile.close();
}





bool searchBook(const BPlusTree& bPlusTree, int searchID, Book& result) {
    return bPlusTree.search(searchID, result);
}

bool updateBook(BPlusTree& bPlusTree, int updateID, int newCitations, int newYear, const char* newTitle) {
    return bPlusTree.update(updateID, newCitations, newYear, newTitle);
}

bool deleteBook(BPlusTree& bPlusTree, int deleteID) {
    return bPlusTree.remove(deleteID);
}

int main() {
    const char* csvFileName = "books_1000.csv";
    const char* binaryFileName = "books.dat";
    const char* indexFileName = "books_index.txt";
    
    BPlusTree bPlusTree;

    
    csvToBinary(csvFileName, binaryFileName, indexFileName, bPlusTree);


    int choice;
    do {
        
        cout << "1. Insert a new record\n";
        cout << "2. Search for a record\n";
        cout << "3. Update a record\n";
        cout << "4. Delete a record\n";
        cout << "5. Display all records\n";
        cout << "0. Exit\n";
        cout << "Enter your choice: ";
        cin >> choice;

        switch (choice) {
            case 1: {
                
                Book newBook;
                cout << "Enter book details:\n";
                cout << "ID: ";
                cin >> newBook.ID;
                cout << "Title: ";
                cin.ignore();
                cin.getline(newBook.Title, sizeof(newBook.Title));
                cout << "Year: ";
                cin >> newBook.Year;
                cout << "Authors: ";
                cin.ignore();
                cin.getline(newBook.Authors, sizeof(newBook.Authors));
                cout << "Citations: ";
                cin >> newBook.Citations;
                cout << "Update (YYYY-MM-DD-HH:mm:ss): ";
                cin >> newBook.Update;
                cout << "Abstract: ";
                cin.ignore();
                cin.getline(newBook.Abstract, sizeof(newBook.Abstract));

                bPlusTree.insert(newBook.ID, newBook);
                break;
            }
            case 2: {
    int searchID;
    cout << "Enter ID to search: ";
    cin >> searchID;

    Book result;
    if (searchBook(bPlusTree, searchID, result)) {
        cout << "Book found: ID=" << result.ID << ", Title=" << result.Title << ", Year=" << result.Year << endl;
    } else {
        cout << "Book not found." << endl;
    }
    break;
}
            case 3: {
                int updateID, newCitations, newYear;
                string newTitle;
                cout << "Enter ID to update: ";
                cin >> updateID;
                cout << "Enter new citations (-1 for no change): ";
                cin >> newCitations;
                cout << "Enter new year (-1 for no change): ";
                cin >> newYear;
                cout << "Enter new title (or press Enter for no change): ";
                cin.ignore();
                getline(cin, newTitle); 

                if (bPlusTree.update(updateID, newCitations, newYear, newTitle.c_str())) {
                    cout << "Book updated successfully." << endl;
                } else {
                    cout << "Book not found for update." << endl;
                }
                break;
                }

            case 4: {
                
                int deleteID;
                cout << "Enter ID to delete: ";
                cin >> deleteID;

                if (bPlusTree.remove(deleteID)) {
                    cout << "Book deleted successfully." << endl;
                } else {
                    cout << "Book not found for deletion." << endl;
                }
                break;
            }
            case 5: {
    
                cout << "All Records:\n";
                for (const auto& entry : bPlusTree.getBookIndex()) {
                    const Book& book = entry.second;
                    cout << "ID=" << book.ID << ", Title=" << book.Title << ", Year=" << book.Year << endl;
                }
                break;
            }
            case 0:
                cout << "Exiting the program.\n";
                break;
            default:
                cout << "Invalid choice. Please try again.\n";
                break;
        }
    } while (choice != 0);

    return 0;
}

I attempted to debug the code, and the functions appear to be working correctly. However, they encounter issues specifically with the books already present in the CSV file.