用C++实现B+树

港控/mmm° 2023-10-06 21:34 25阅读 0赞

### 1、简介要求 ###

在理解并掌握B+树的逻辑结构的基础上，实现内存上的B+树数据结构，包括查询、插入、删除等基本操作。注意B+树原本为外存数据结构，本实验仅要求实现其内存版本。

### 2、实现结果和功能 ###

1.  **运行结果—建树**  
    ![在这里插入图片描述][2a767ab33a5f4f528b49470cd4d78fc6.png]  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16]
2.  **运行结果—插入**  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 1]
3.  **运行结果—删除**  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 2]
4.  **运行结果—更改**  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 3]

### 3、B+树生成器 ###

[B+树生成器][B]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 4]

### 4、代码实现 ###

#include <time.h>
    #include <iostream>
    #include <queue>
    #include <string>
    #include<algorithm>
    using namespace std;
    #define M 2//m*2=key数，m*2+1=值；//插入满格灌，删除一个节点不能少于(M+1)/2,若zhi为5，不能少于2
    string key_words[1001];//5阶树,最多4个关键字
    class Inter_Node;
    
    class Node
    {
        
    public:
        Node();
        virtual ~Node();
        Node* GetBrother(int& flag);
        Inter_Node* Parent;
        int key[M * 2];//4
        int count; 
        int isLeaf;
        void Print();
    };
    Node::~Node() {
        }
    
    class Inter_Node : public Node
    {
        
    public:
        Inter_Node();
        virtual ~Inter_Node();//虚函数声明定义
        bool Insert(int value, Node* pNode);
        bool Delete(int value);
        int Split(Inter_Node* pNode, int key);//分裂
        bool Merge(Inter_Node* pNode);
        bool Slib(Inter_Node* pNode);
        Node* Child[M * 2 + 1];//5个查找路径
    };
    Inter_Node::~Inter_Node()
    {
        
        for (int i = 0; i < M * 2 + 1; i++)
            Child[i] = NULL;
    }
    
    //叶子结点
    class Leaf_Node : public Node
    {
        
    public:
        Leaf_Node();
        virtual ~Leaf_Node();
        bool Insert(int value);
        bool Delete(int value);
        int Split(Leaf_Node* pNode);
        bool Merge(Leaf_Node* pNode);
        Leaf_Node* Pre_Node;
        Leaf_Node* Next_Node;
    };
    Leaf_Node::~Leaf_Node() {
        }
    
    //B+树
    class Bplus
    {
        
    public:
        Bplus();
        virtual ~Bplus();
        bool Search(int data, string& sPath);
        bool Insert(int data);
        bool Delete(int data);
        void Print();
    
    protected:
        Leaf_Node* Find(int data);
        bool Add_Node(Inter_Node* pNode, int key, Node* New_Node);
        bool Remove_Node(Inter_Node* pNode, int key);
        Node* Root;
    };
    Bplus::~Bplus() {
        }
    
    //结点创建对象
    Node::Node()
    {
        
        isLeaf = true;
        count = 0;
        Parent = NULL;
    }
    //叶子结点创建对象
    Leaf_Node::Leaf_Node()
    {
        
        isLeaf = true;
        Pre_Node = NULL;
        Next_Node = NULL;
    }
    //中间结点创建对象
    Inter_Node::Inter_Node()
    {
        
        isLeaf = false;
        for (int i = 0; i < M * 2 + 1; i++)
            Child[i] = NULL;
    }
    //Bplus创建对象
    Bplus::Bplus()
    {
        
        Root = NULL;
    }
    
    //结点查找兄弟结点
    Node* Node::GetBrother(int& flag)
    {
        
        if (NULL == Parent)
            return NULL;
    
        Node* p = NULL;
        for (int i = 0; i <= Parent->count; i++)
        {
        
            if (Parent->Child[i] == this)
            {
        
                if (i == Parent->count)
                {
        
                    p = Parent->Child[i - 1];//左兄弟 flag=1
                    flag = 1;
                }
                else
                {
        
                    p = Parent->Child[i + 1];//右兄弟 flag=2
                    flag = 2;
                }
            }
        }
        return p;
    }
    
    //结点输出
    void Node::Print()
    {
        
        for (int i = 0; i < count; i++)
        {
        
            cout << "(" << key[i] << "," << key_words[key[i]] << ")  ";
            if (i >= count - 1)
                cout << " | ";
        }
    }
    
    //叶子结点的分裂
    int Leaf_Node::Split(Leaf_Node* p)
    {
        
        int j = 0;
        for (int i = M; i < M * 2; i++, j++)//把值copy到新节点
        p->key[j] = this->key[i];//this为old node
        this->count = this->count - j;
        p->count = j;
        return p->key[0];
    }
    
    //叶子结点删除
    bool Leaf_Node::Delete(int value)
    {
        
        bool found = false;
        int i = 0;
        for (; i < count; i++)
        {
        
            if (value == key[i])
            {
        
                found = true;
                break;
            }
        }
        if (false == found)
            return false;
        int j = i;
        for (; j < count - 1; j++)
            key[j] = key[j + 1];
        key[j] = 0;
        count--;
        return true;
    }
    
    //叶子结点的插入
    bool Leaf_Node::Insert(int value)
    {
        
        int i = 0;
        for (; (value > key[i]) && (i < count); i++)//按顺序
        {
        
        }
        for (int j = count; j > i; j--)//移动，找到应该插入的关键字位置
            key[j] = key[j - 1];
        key[i] = value;//插入关键字
        count++;
        return true;
    }
    
    //叶结点查找
    Leaf_Node* Bplus::Find(int data)//data为关键字
    {
        
        int i = 0;
        Node* p = Root; //?????bplus的跟
        Inter_Node* q;  //?м???
        while (NULL != p)
        {
        
            if (p->isLeaf) //????????????
                break;
            for (i = 0; i < p->count; i++) //??????p??key?????p不是叶子，循环至count的节点
            {
        
                if (data < p->key[i])
                    break;
            }
            q = (Inter_Node*)p;
            p = q->Child[i];
        }
        
        return (Leaf_Node*)p;//把根return,如果跟为空,第一个插入函数生成的节点即为根
    }
    
    //叶子结点,合并叶子结点
    bool Leaf_Node::Merge(Leaf_Node* p)
    {
        
        if (this->count + p->count > M * 2)//如果加在一起格满说明不需要合并
            return false;
        for (int i = 0; i < p->count; i++)//否则将oldnode的关键字都插入到bro里
            this->Insert(p->key[i]);
        return true;
    }
    
    //中间结点Merge合并
    bool Inter_Node::Merge(Inter_Node* p)
    {
        
        key[count] = p->Child[0]->key[0];
        count++;
        Child[count] = p->Child[0];
        for (int i = 0; i < p->count; i++)
        {
        
            key[count] = p->key[i];
            count++;
            Child[count] = p->Child[i + 1];
        }
        return true;
    }
    
    //中间结点插入
    bool Inter_Node::Insert(int value, Node* New)
    {
        
        int i = 0;
        for (; (i < count) && (value > key[i]); i++)//i指向key要插入的位置
        {
        
        }
        for (int j = count; j > i; j--)//挪动倒地方
            key[j] = key[j - 1];
        for (int j = count + 1; j > i + 1; j--)//父亲key值改变，孩子移动；
            Child[j] = Child[j - 1];
        key[i] = value;//关键字传到父亲节点
        Child[i + 1] = New;//newnode放到该放的位置
        New->Parent = this;
        count++;
        return true;
    }
    
    //中间结点分裂
    int Inter_Node::Split(Inter_Node* p, int k)
    {
        
        int i = 0, j = 0;
        if ((k > this->key[M - 1]) && (k < this->key[M]))//分裂的地方在中间
        {
        
            for (i = M; i < M * 2; i++, j++)
                p->key[j] = this->key[i];//拷贝后面值进brother
            j = 1;
            for (i = M + 1; i <= M * 2; i++, j++)
            {
        
                this->Child[i]->Parent = p;//孩子跟着往后移动
                p->Child[j] = this->Child[i];
            }
            this->count = M;//关键子数量各位一半
            p->count = M;
            return k;
        }
        int pos = k < this->key[M - 1] ? (M - 1) : M;//看k大小和中间-1比较，定位在前面还是在后面节点
        k = this->key[pos];//pos为分裂点,定位为前还是后分裂点,最后肯定为中间值
        j = 0;
        for (i = pos + 1; i < M * 2; i++, j++)//前节点考后节点,从插入的位置分，插入以后的放到新节点
            p->key[j] = this->key[i];
        j = 0;
        for (i = pos + 1; i <= M * 2; i++, j++)//将孩子送给兄弟
        {
        
            this->Child[i]->Parent = p;
            p->Child[j] = this->Child[i];
        }
        this->count = pos;
        p->count = M * 2 - pos - 1;
        return k;
    }
    
    //中间结点删除
    bool Inter_Node::Delete(int k)
    {
        
        int i = 0;
        for (; (k >= key[i]) && (i < count); i++)
        {
        
        }
        for (int j = i - 1; j < count - 1; j++)
            key[j] = key[j + 1];
        k = i;
        for (; k < count; k++)
        {
        
            Child[k] = Child[k + 1];
        }
        Child[k] = NULL;
        count--;
        return true;
    }
    
    //中间结点
    bool Inter_Node::Slib(Inter_Node* p)
    {
        
        int i, j;
        if (p->key[0] < this->key[0])
        {
        
            for (i = count; i > 0; i--)
                key[i] = key[i - 1];
            for (j = count + 1; j > 0; j--)
                Child[j] = Child[j - 1];
            key[0] = Child[0]->key[0];
            Child[0] = p->Child[p->count];
        }
        else
        {
        
            key[count] = p->Child[0]->key[0];
            Child[count + 1] = p->Child[0];
            for (i = 1; i < p->count - 1; i++)
                p->key[i - 1] = p->key[i];
            for (j = 0; j < p->count - 1; j++)
                p->Child[j] = p->Child[j + 1];
        }
        this->count++;
        p->count--;
        return true;
    }
    
    //B+树添加结点
    bool Bplus::Add_Node(Inter_Node* p, int k, Node* New_Node)
    {
        
        if (NULL == p || p->isLeaf)
            return false;
        if (p->count < M * 2)//父亲不满
            return p->Insert(k, New_Node);
        Inter_Node* Brother = new Inter_Node;
        //叶子节点满，父节点也满分裂情况
        int NewKey = p->Split(Brother, k);//NewKey为需要提取并插入到root节点的值
    
        //确定需要插入的关键字，是插入到分裂节点的哪个位置
        if (p->count < Brother->count)
        {
        
            p->Insert(k, New_Node);
        }
        else if (p->count > Brother->count)
        {
        
            Brother->Insert(k, New_Node);
        }
        else
        {
        
            Brother->Child[0] = New_Node;
            New_Node->Parent = Brother;
        }
        Inter_Node* parent = (Inter_Node*)(p->Parent);
        if (NULL == parent)
        {
        
            parent = new Inter_Node();
            parent->Child[0] = p;
            parent->key[0] = NewKey;//newkey为分裂传回，为插入的中间值
            parent->Child[1] = Brother;
            p->Parent = parent;
            Brother->Parent = parent;
            parent->count = 1;
            Root = parent;
            return true;
        }
        return Add_Node(parent, NewKey, Brother);
    }
    
    //B+树查找data
    bool Bplus::Search(int data, string& sPath)
    {
        
        int i = 0;
        sPath = "查找路径为: ";
        Node* p = Root;
        if (NULL == p)
            return false;
        Inter_Node* q;
        while (NULL != p)
        {
        
            if (p->isLeaf)
                break;
            for (i = 0; (i < p->count) && (data >= p->key[i]); i++)
            {
        
            }
            int k = i > 0 ? i - 1 : i;
            sPath += to_string(p->key[k]);
            sPath += "-->";
            q = (Inter_Node*)p;
            p = q->Child[i];
        }
        if (NULL == p)
            return false;
        sPath += to_string(p->key[0]);
        bool found = false;
        for (i = 0; i < p->count; i++)
        {
        
            if (data == p->key[i])
                found = true;
            //sPath += to_string(p->key[i]);
            //sPath += "-->";
        }
        if (found)
        {
        
            sPath += " OK";
        }
        else
        {
        
            sPath += " FAIL";
        }
        return found;
    }
    
    //B+树的插入
    bool Bplus::Insert(int data) //data为插入的关键字
    {
        
        
        string a;
        if (true == Search(data, a))//查找要插入的值
            return false;
        
        Leaf_Node* Old_Node = Find(data);//找到需要插入的叶子节点定义为oldnode
       
        if (NULL == Old_Node)
        {
        
            Old_Node = new Leaf_Node;//树为空
            Root = Old_Node;
        }
        
        if (Old_Node->count < M * 2) {
        //有空间插入，直接插进去并返回
            return Old_Node->Insert(data); 
    
        }
    
        Leaf_Node* New_Node = new Leaf_Node;//即将分裂
        
        int k = Old_Node->Split(New_Node);//k为新节点第一个关键子
    
        Leaf_Node* OldNext = Old_Node->Next_Node;
        Old_Node->Next_Node = New_Node;//相邻叶子节点相连
        New_Node->Next_Node = OldNext;
        New_Node->Pre_Node = Old_Node;
    
        if (NULL != OldNext)
            OldNext->Pre_Node = New_Node;
    
        if (data < k)//小于newnode key[0]，插前面，否则插后面
        {
        
            Old_Node->Insert(data);
        }
        else
        {
        
            New_Node->Insert(data);
        }
        Inter_Node* parent = (Inter_Node*)(Old_Node->Parent);
    
        if (NULL == parent)//初始化parent，若没有父结点，新建一个
        {
        
            Inter_Node* New_Root = new Inter_Node;
            New_Root->Child[0] = Old_Node;
            New_Root->key[0] = k;
            New_Root->Child[1] = New_Node;
            Old_Node->Parent = New_Root;
            New_Node->Parent = New_Root;
            New_Root->count = 1;
            Root = New_Root;
            return true;
        }
    
        return Add_Node(parent, k, New_Node);//向父亲里插值或者分裂父亲建立新的节点
    }
    
    //B+树的删除
    bool Bplus::Delete(int data)
    {
        
        Leaf_Node* Old_Node = Find(data); //查找数据
        if (NULL == Old_Node)//树为空
            return false;
        if (false == Old_Node->Delete(data)) //删除
            return false;
        Inter_Node* parent = (Inter_Node*)(Old_Node->Parent);
        if (NULL == parent)
        {
        
            if (0 == Old_Node->count)//将整棵树删掉，没父亲没key
            {
        
                delete Old_Node;
                Root = NULL;
            }
            return true;
        }
        if (Old_Node->count >= M)
        {
        
            for (int i = 0; (i < parent->count) && (data >= parent->key[i]); i++)
            {
        
                if (parent->key[i] == data)//如果要删除的key比父亲索引他的值要大就直接删除，如果相等，就给父亲一个新索引
                    parent->key[i] = Old_Node->key[0];
            }
            return true;
        }
        //不满足规格，要合并或借值
        int flag = 1;
        Leaf_Node* Brother = (Leaf_Node*)(Old_Node->GetBrother(flag));
        int NewData = 0;
        if (Brother->count > M)//借值
        {
        
            if (1 == flag)//左兄弟
            {
        
                NewData = Brother->key[Brother->count - 1];//要被借走的数据
            }
            else//右兄弟
            {
        
                NewData = Brother->key[0];
            }
            Old_Node->Insert(NewData);
            Brother->Delete(NewData);
            //替换parent中的key值
            if (1 == flag)
            {
        
                for (int i = 0; i <= parent->count; i++)//向左兄弟借值
                {
        
                    if (parent->Child[i] == Old_Node && i > 0)
                        parent->key[i - 1] = Old_Node->key[0];
                }
            }
            else
            {
        
                for (int i = 0; i <= parent->count; i++)//向右兄弟借值
                {
        
                    if (parent->Child[i] == Old_Node && i > 0)
                        parent->key[i - 1] = Old_Node->key[0];
                    if (parent->Child[i] == Brother && i > 1)
                        parent->key[i - 1] = Brother->key[0];
                }
            }
            return true;
        }
        int NewKey = 0;
        if (1 == flag)//无法借值，合并
        {
        
            Brother->Merge(Old_Node);
            NewKey = Old_Node->key[0];//标记要删除的父亲里的key
            Leaf_Node* OldNext = Old_Node->Next_Node;//接入后面兄弟
            Brother->Next_Node = OldNext;
            if (NULL != OldNext)
                OldNext->Pre_Node = Brother;
            delete Old_Node;
        }
        else
        {
        
            Old_Node->Merge(Brother);
            NewKey = Brother->key[0];
            Leaf_Node* OldNext = Brother->Next_Node;
            Old_Node->Next_Node = OldNext;
            if (NULL != OldNext)
                OldNext->Pre_Node = Old_Node;
            delete Brother;
        }
        return Remove_Node(parent, NewKey);//移除parent或者移除parent中关键字；
    }
    
    //Bplus 移除结点
    bool Bplus::Remove_Node(Inter_Node* p, int k)
    {
        
        if (false == p->Delete(k))
        {
        
            return false;
        }
        Inter_Node* parent = (Inter_Node*)(p->Parent);
        if (NULL == parent)
        {
        
            if (0 == p->count)
            {
        
                Root = p->Child[0];
                delete p;
            }
            return true;
        }
        if (p->count >= M)//父亲不合并
        {
        
            //删掉parent中的关键字
            for (int i = 0; (i < parent->count) && (k >= parent->key[i]); i++)
            {
        
                if (parent->key[i] == k)//看父亲的parent里有没有要删除的关键字，有就更新索引
                    parent->key[i] = p->key[0];
            }
            return true;
        }
        //父亲合并
        int flag = 1;
        Inter_Node* Brother = (Inter_Node*)(p->GetBrother(flag));
        if (Brother->count > M)//父亲借值
        {
        
            p->Slib(Brother);
            if (1 == flag)
            {
        
                for (int i = 0; i <= parent->count; i++)
                {
        
                    if (parent->Child[i] == p && i > 0)
                        parent->key[i - 1] = p->key[0];
                }
            }
            else
            {
        
                for (int i = 0; i <= parent->count; i++)
                {
        
                    if (parent->Child[i] == p && i > 0)
                        parent->key[i - 1] = p->key[0];
                    if (parent->Child[i] == Brother && i > 0)
                        parent->key[i - 1] = Brother->key[0];
                }
            }
            return true;
        }
        //兄弟借值
        int NewKey = 0;
        if (1 == flag)
        {
        
            Brother->Merge(p);
            NewKey = p->key[0];
            delete p;
        }
        else
        {
        
            p->Merge(Brother);
            NewKey = Brother->key[0];
            delete Brother;
        }
        return Remove_Node(parent, NewKey);
    }
    
    //Bplus输出
    void Bplus::Print()
    {
        
        Node* p = Root;
        if (NULL == p)
            return;
        Inter_Node* a;
        int H = 0;
        queue<Node*> q;
        queue<int> h;
        q.push(p);
        h.push(1);
        while (!q.empty())
        {
        
            p = q.front();
            if (H != h.front())
            {
        
                cout << endl;
                cout << H << endl;
                H = h.front();
            }
            q.pop();
            h.pop();
            p->Print();
            if (NULL != p && !p->isLeaf)
            {
        
                a = (Inter_Node*)p;
                for (int i = 0; i <= p->count; i++)
                {
        
                    q.push(a->Child[i]);
                    h.push(H + 1);
                }
            }
        }
    }
    
    //测试：test1 建立B+tree
    void test1(Bplus* bplus, int count)//count为想要几个节点，返回值建一个树
    {
        
        srand((unsigned)time(NULL));
        //随机种子
        cout << " 插入数据： ";
        for (int i = 1; i <= count; i++)//
        {
        
            //int x = i;
            int x = rand() % 1000 + 1;//随机生成x
            key_words[x] = " ";
            for (int i = 0; i < 2; i++)
            {
        
                int y = rand() % 26 + 65;//生成一个随机数
                int z = rand() % 26 + 97;
                key_words[x] += char(y);
                key_words[x] += char(z);
            }//生成四个字符的数据
            cout << "[" << x << " "
                << "," << key_words[x] << "]" << " ";
            bplus->Insert(x);//x=key
        }
        cout << "B+树建立suceess!" << endl;
        cout << endl;
    }
    
    //测试：test2查询
    void test2(Bplus* bplus, int data)
    {
        
        string sPath;
        bplus->Search(data, sPath);
        cout << sPath;
        cout << endl;
    }
    
    //测试：test3插入
    void test3(Bplus* bplus, int data, string s)
    {
        
        bool success = bplus->Insert(data);
        key_words[data] = s;
        if (true == success)
        {
        
            cout << "OK" << endl;
        }
        else
        {
        
            cout << "FAIL" << endl;
        }
        cout << endl;
    }
    
    //测试：test4删除
    void test4(Bplus* bplus, int data)
    {
        
        bool success = bplus->Delete(data);
        if (true == success)
        {
        
            cout << "成功" << endl;
        }
        else
        {
        
            cout << "错误" << endl;
        }
        cout << endl;
    }
    
    //测试：test5打印
    void test5(Bplus* bplus)
    {
        
        bplus->Print();
        cout << endl;
    }
    
    //测试：test6修改
    void test6(Bplus* bplus, int i, string j, int k, string l)
    {
        
        if (i == k)
        {
        
            key_words[i] = l;
        }
        else
        {
        
            //i ！= j
            //删除(i , j );
            bplus->Delete(i);
            //插入(k , l )
            bplus->Insert(k);
            //初始化结点内容
            key_words[k] = l;
        }
        cout << endl;
    }
    
    //主函数
    int main()
    {
        
        Bplus* bplus = new Bplus();
        int x = 1;
        int y = 0;
        string s = " ";
        int i, k;
        string j = " ";
        string l = " ";
        while (0 != x)
        {
        
            cout << "1.请问需要多少个节点的B+tree"<<endl;
            cout << "2.需要查询 " << endl;
            cout << "3.需要插入内容 " << endl;
            cout << "4.需要删除内容" << endl;
            cout << "5.需要显示B+树形状" << endl;
            cout << "6.需要修改内容" << endl;
            cout << " \n";
            cin >> x;
            switch (x)
            {
        
            case 1:
                cout << "请输入需要多少个结点：";
                cin >> y;
                test1(bplus, y);
                break;
            case 2:
                cout << "请输入要查询的关键值key A：";
                cin >> y;
                test2(bplus, y);
                break;
            case 3:
                cout << "请输入要插入的关键值key A和B：";
                cin >> y >> s;
                test3(bplus, y, s);
                break;
            case 4:
                cout << "请输入要删除的关键值key A：";
                cin >> y;
                test4(bplus, y);
                break;
            case 5:
                test5(bplus);
                break;
            case 6:
                cout << "请输入要删除的A和B：";
                cin >> i >> j;
                cout << "请输入要插入的A和B：";
                cin >> k >> l;
                test6(bplus, i, j, k, l);
                break;
            default:
                delete bplus;
                return 0;
                break;
            }
        }
        return 0;
    }

[2a767ab33a5f4f528b49470cd4d78fc6.png]: https://img-blog.csdnimg.cn/2a767ab33a5f4f528b49470cd4d78fc6.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/99cc5213673c4d2bb31f7fc5fdf2fdf7.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y-r5oiR6ICB5Lyv,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/342481771d774627929c158a63aab597.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y-r5oiR6ICB5Lyv,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/6b78f5fb24914d3191ec85db5c781738.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y-r5oiR6ICB5Lyv,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/f7bc88afb0744d25b0106632ff8c1e99.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y-r5oiR6ICB5Lyv,size_20,color_FFFFFF,t_70,g_se,x_16
[B]: https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/c8b2482d9bd04f0b8e9e972872b838b2.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y-r5oiR6ICB5Lyv,size_20,color_FFFFFF,t_70,g_se,x_16