C++ B+Tree搜索和插入实现

Question

我为B+Tree做了一个C++的例子。我测试了很多次。我没有得到任何错误或错误，但我不能确定它是否真的工作(没有任何错误)或我不知道它是否适合使用(内存问题，优化等)。我要你的意见，测试结果和建议。

    /*
 * C++ Program to Implement B+ Tree
 */
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include <stdlib.h>
#include <fstream>
#include <sstream>
#include <unistd.h>
using namespace std;

struct Student{
    int number;
    int failCount;
    string name;
    string surname;
    string field;
};

struct less_than_key
{
    inline bool operator() (const Student& struct1, const Student& struct2)
    {
        return (struct1.number < struct2.number);
    }
};

const int numberofdatas = 4;
const int numberofkeys = numberofdatas+1;

struct BTreeNode
{
    BTreeNode* parent;
    vector<BTreeNode*> childLeafs;
    vector<Student> datas;
    BTreeNode(){
        parent = NULL;
    }
} * BTreeRoot = new BTreeNode;


void BTreeOpt(BTreeNode* tree){
    if(!tree->childLeafs.empty()){
        for(int i = 0; i < tree->childLeafs.size();i++){
            tree->childLeafs[i]->parent = tree;
        }
        for(int i = 0; i < tree->childLeafs.size();i++){
            BTreeOpt(tree->childLeafs[i]);
        }
    }
}

// Search in B+Tree and return last leaf
BTreeNode* BTreeSearch(BTreeNode* tree, int key){
    BTreeOpt(BTreeRoot);
    while(!tree->childLeafs.empty()){
        if(key < tree->datas[0].number){
            if(!tree->childLeafs.empty())
            tree = tree->childLeafs[0];
        }
        if(tree->datas.size() > 1)
        for(int i =0; i < tree->datas.size()-1; i++){
            if(key >= tree->datas[i].number && key < tree->datas[i+1].number){
                if(!tree->childLeafs.empty())
                tree = tree->childLeafs[i+1];
            }
        }
        if(key > tree->datas.back().number){
            if(!tree->childLeafs.empty())
            tree = tree->childLeafs[tree->datas.size()];
        }
    }
    return tree;
}

void BTreeSplitT(BTreeNode* node){
    BTreeNode * Parent, * Right = new BTreeNode, *Left = new BTreeNode;
    // Control if node has Parent
    if(node->parent != NULL){
        Parent = node->parent;
    }else{
        Parent = new BTreeNode;
    }
    int middleInt = node->datas.size()/2;
    Student middle = node->datas[middleInt];
    // Load Left Node
    for(int i=0; i< middleInt;i++){
        Left->datas.push_back(node->datas[i]);
        if(!node->childLeafs.empty()){
            Left->childLeafs.push_back(node->childLeafs[i]);
        }
    }
    // Load childLeafs
    if(!node->childLeafs.empty()){
        Left->childLeafs.push_back(node->childLeafs[middleInt]);
        middleInt++;
        Right->childLeafs.push_back(node->childLeafs[middleInt]);
    }
    // Load Right Node
    for(int i=middleInt; i< node->datas.size();i++){
        Right->datas.push_back(node->datas[i]);
        if(!node->childLeafs.empty()){
            Right->childLeafs.push_back(node->childLeafs[i+1]);
        }
    }
    if(Parent->datas.empty()){
        Parent->datas.push_back(middle);
        Parent->childLeafs.push_back(Left);
        Parent->childLeafs.push_back(Right);
        Right->parent = Left->parent = Parent;
        BTreeRoot = Parent;
    }else{
        int n = 0;
        if(middle.number < Parent->datas[0].number){
            n = 0;
        }
        for(int i =0; i < Parent->datas.size()-1; i++){
            if(middle.number >= Parent->datas[i].number && middle.number < Parent->datas[i+1].number){
                n = i+1;
            }
        }
        if(middle.number > Parent->datas.back().number){
            n = Parent->datas.size();
        }
        if(n == Parent->datas.size()){
            Parent->childLeafs.pop_back();
            Parent->datas.push_back(middle);
            Parent->childLeafs.push_back(Left);
            Parent->childLeafs.push_back(Right);
            Left->parent = Right->parent = Parent;
        }else{
            Parent->datas.insert(Parent->datas.begin()+n, middle);
            Parent->childLeafs.insert(Parent->childLeafs.begin()+n+1, Right);
            Parent->childLeafs[n] = Left;
            Left->parent = Right->parent = Parent;
        }
        if(Parent->datas.size() > numberofdatas){
            BTreeSplitT(Parent);
        }
    }
}



// Insert to BTreeRoot
void BTreeInsert(Student student){
    BTreeNode* temp = BTreeSearch(BTreeRoot, student.number);
    temp->datas.push_back(student);
    std::sort(temp->datas.begin(), temp->datas.end(), less_than_key());
    if(temp->datas.size() >= numberofkeys){
        BTreeSplitT(temp);
    }

}

// Print B+Tree datas
void BTreePrint(BTreeNode* tree){
    if(tree->childLeafs.size() != 0)
    for(int i = 0; i < tree->childLeafs.size();i++){
        BTreePrint(tree->childLeafs[i]);
    }
    if(tree->childLeafs.size() == 0)
    for(int i = 0; i < tree->datas.size();i++){
        cout << tree->datas[i].number << " -> ";
    }
}

// Print B+Tree visual
void BTreePrint2(BTreeNode* tree){
    for(int i = 0; i < tree->datas.size();i++){
        cout << tree->datas[i].number << " -> ";
    }
    cout << endl;
    if(tree->childLeafs.size() != 0)
    for(int i = 0; i < tree->childLeafs.size();i++){
        BTreePrint2(tree->childLeafs[i]);
    }
}
int main()
{
    Student ogr;
    string line;
    int no;
    ifstream menuFile ("numbers.txt");
    if (menuFile.is_open()){
        while ( getline (menuFile,line) ){
            std::istringstream os(line);
            os >> no;
            ogr.number = no;
            printf("Adding: %d\n",no);
            BTreeInsert(ogr);
            BTreePrint2(BTreeRoot);
            printf("---------------------------\n");
        }
        menuFile.close();
    }
    else cout << "Menu Dosyası Bulunamadı.";
    return 0;
}

Answer 1

避免using namespace std;。

你不能删除你分配的任何内存。

operator()在less_than_key中是内联定义的，因此可以省略inline关键字。

BTreeRoot是一个全局变量，应该避免。最好是在main (您使用它的地方)中声明，所有的BTree函数都是BTreeNode的成员。如果将其保持为全局变量，则将其声明为类型(BTreeNode BTreeRoot)，而不是立即分配的指针。

不要使用tree->childLeafs.size() != 0，而是使用!tree->childLeafs.empty()。在向量上调用size可能需要计算，而empty不需要计算。

在BTreeSearch中，将tree->datas[tree->datas.size()-1]替换为tree->datas.back()。如果datas是空的，这可能是一个错误的访问。带有for的i循环可以在1处开始索引，条件和正文有适当的更改，这将简化一些代码(不需要从大小中始终减去1)。

所有#include指令都应该是文件的顶部，而不是在很难找到的中间部分(并且更有可能包含两次)。