Skip to content

Latest commit

 

History

History
135 lines (126 loc) · 6.6 KB

README.md

File metadata and controls

135 lines (126 loc) · 6.6 KB
Raw

A simple B+ tree implemented using C++

项目说明

数据结构

  • indices类型为vector，保存的是键，也就是索引值。
  • children类型为vector<Node*>，保存是指向孩子节点的指针。
  • values类型为vector，尽在当前节点为叶子节点时（leaf==true）才有效，保存的是键对应的值。

函数设计

  • 外部方法为insert插入键值对、remove删除键、search查找键。
  • 内部方法split用于插入后父亲节点索引大于M-1时用于递归分裂父节点；adjust用于删除后父亲节点元素少于M/2时用于递归调整父节点。

逻辑介绍

使用mermaid绘制，mermaid在线编辑器

  • insert
    graph TD
    A(开始：插入键值对) --> B{根节点为空吗？}
    B -->|是| C[创建新的叶子节点作为根节点，插入键值对，结束]
    B -->|否| D[找到插入的叶子节点]
    D --> E{叶子节点已满吗？}
    E -->|否| F[在叶子节点中插入键值对，结束]
    E -->|是| G[分裂叶子节点]
    G --> H{存在父节点吗？}
    H -->|否| I[创建新的根节点，结束]
    H -->|是| J[在父节点中插入新键]
    J --> K{父节点已满吗？}
    K -->|否| L[结束]
    K -->|是| M[递归分裂父节点]
    M --> H
Loading
  • remove
graph TD
A[开始] --> B[根节点为空]
B -->|是| C[打印'树空，无法删除键'，结束]
B -->|否| D[找到要删除的叶子节点]
D --> E[找到要删除的键值对]
E -->|找不到| F[打印'没有找到要删除的键 k'，结束]
E -->|找到| G[删除键值对]
G --> H[当前节点是根节点]
H -->|是| I[根节点的元素个数为0]
I -->|是| J[删除根节点，结束]
I -->|否| K[结束]
H -->|否| L[叶子节点元素个数小于MIN_IND]
L -->|否| M[结束]
L -->|是| N[左兄弟节点能借]
N -->|是| O[从左兄弟节点借一个元素，结束]
N -->|否| P[右兄弟节点能借]
P -->|是| Q[从右兄弟节点借一个元素，结束]
P -->|否| R[左右兄弟节点都不能借，只能合并]
R --> S[合并左兄弟节点]
R --> T[合并右兄弟节点]
S --> U[父节点元素个数小于MIN_IND]
U -->|是| V[调整父节点，结束]
U -->|否| W[结束]
T --> X[父节点元素个数小于MIN_IND]
X -->|是| Y[调整父节点，结束]
X -->|否| Z[结束]
Loading
  • adjust
graph TD
A[开始] --> B[当前节点是根节点]
B -->|是| C[根节点孩子指针个数]
C -->|为0| D[删除根节点，结束]
C -->|为1| E[根节点指向唯一的子节点，更新根节点，结束]
C -->|大于1| F[结束]
B -->|否| G[寻找兄弟节点]
G --> H[左兄弟节点存在且元素个数大于MIN_IND]
H -->|是| I[从左兄弟节点借一个元素，结束]
H -->|否| J[右兄弟节点存在且元素个数大于MIN_IND]
J -->|是| K[从右兄弟节点借一个元素，结束]
J -->|否| L[左右兄弟节点都不能借，只能合并]
L --> M[优先合并左兄弟节点]
M -->|可以| N[合并左兄弟节点，递归调整父节点，结束]
M -->|不可以| O[合并右兄弟节点]
O --> P[合并右兄弟节点，递归调整父节点，结束]
Loading
  • split
graph TD
A[开始] --> B[创建新节点]
B --> C[分配children指针]
C --> D[分配indices索引]
D --> E[暂存父节点的索引值]
E --> F[当前节点是根节点]
F -->|是| G[创建新根节点，结束]
F -->|否| H[插入k到父节点]
H --> I[父节点的indices大小超过MAX_IND]
I -->|是| J[递归分裂父节点，结束]
I -->|否| K[结束]
Loading

实验设计测试

int main() {
    BPlusTree<int, string> bpt;
    vector<int> keys1 = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
    vector<string> values1 = {"1", "2", "3", "4", "5", "6", "7", "8", "9","10","11","12","13","14","15","16","17","18","19"};
    vector<int> keys2 = {19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
    vector<string> values2 = {"19","18","17","16","15","14","13","12","11","10","9","8","7","6","5","4","3","2","1"};
    
    cout<<"测试从左向右插入和删除，以及查找键"<<endl;
    insertTest(bpt,keys1,values1);
    bpt.show();
    bpt.search(1);
    bpt.search(-1);
    removeTest(bpt,keys1);
    
    cout<<"测试从右向左插入和删除"<<endl;
    insertTest(bpt,keys1,values1);
    removeTest(bpt,keys1);

    cout<<"测试从左向右插入，从右向左删除"<<endl;
    insertTest(bpt,keys1,values1);
    removeTest(bpt,keys2);

    cout<<"测试从右向左插入，从左向右删除"<<endl;
    insertTest(bpt,keys2,values2);
    removeTest(bpt,keys1);
    return 0;
}

实验设计总结

我对于“m阶B树”和“m阶B+树”的理解是这样的：对于“m阶B树”，每个结点最多存储m个指向子节点的指针，m-1个键值对，这就是“m阶”的来源；而对于“m阶B+树”，实际上对于其索引节点，每个结点最多有m-1个键（不是键值对），而叶子节点最多也只有m-1个键值对，这里的“m阶”的体现并不是很直观，只是沿用了B树的称呼。这是一个关键的混淆点。网上说法不一 ，在实现时，根据维基百科，仍然取和B树相同的语义，即每个结点最多有“m”个指针，存储“m-1”个键。

我们在《数据结构》课程中已经学习了B树。B树产生的背景是，如果被检索的项存储在磁盘等外存储器上，每次查询都需要把其中一个块从磁盘读取到内存中之后才能进行。而读取的时间花费对于CPU来说是巨大的，因此需要一个数据结构能够在尽量少的读取次数中查找到结果。因此B树采用多叉的树形。

B+树是在B树的基础上，为了更好地提高磁盘I/O效率，得到更好的查询性能和空间利用率而提出的。B+树相比于B树，有几个不同：1. 非叶子节点（索引节点、内部节点）只保存索引信息，数据都保存在叶子节点。2. 所有相邻的叶子节点通过链表进行连接。

由于B+树的索引节点上不存储数据，只存储键（B树的结点上存储的是键值对），此时一页中就可以存储更多的键，而树的阶数就能更大，也就是说，树形会更矮更胖，因此IO次数可以进一步减少，也就是说查询速率得到提升。