【B+树】树结构之B+树简介

文章目录

1.m阶B+树定义

B+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。
B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。
根结点本身即可以是内部结点，也可以是叶子结点。
根节点关键字个数范围[1,m-1]。
除根节点外的节点关键字个数范围[ $\lceil$ m/2 $\rceil$ -1,m-1]。内部节点中，存储的索引数是关键字数加1；叶子节点中，存储的数据数是关键字数
所有叶子节点在同一层。
内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接构成一个链表。

2.m阶B+树节点数据结构

b+树节点本身(包括叶子节点)不存储信息，常作为索引记录待查数据位置信息，通常通过指针索引待查数据。
b+树只有叶子节点存储指向待查数据的指针。这点和b树不同。
其基本数据结构如下(如果是叶子节点还需存放一个指针索引数据)

template<typename T>//节点key值类型为模板类型T
class BPlusTreeNode {
private:
    int currentKeyNum;//节点当前存储的key数量
    int maxKeyNum;//节点最多能存储的key数量
    T *pKey;//存放key的一位数组，初始化时需new分配maxKeyNum个空间
    BPlusTreeNode<T> *pParent;//父节点指针
    BPlusTreeNode<T> **pChilds;//存放孩子节点的一位数组，初始化时需new分配maxKeyNum个空间
    static const T keyMaxValue = 10000;//节点key的最大值
}

3.m阶B+树的基本操作示意

3.1查找操作

从根节点开始查找，利用B+树的性质可以逐层查找，不过多赘述。

3.2插入操作

例1：在下面三阶b+树中插入9

在这里插入图片描述
首先查找9应插入的叶节点(最左下角的那一个),插入发现没有破坏B+树的性质,完毕。插完如下图所示:

例2：在下面三阶b+树中插入20

在这里插入图片描述
首先查找20应插入的叶节点(第二个叶子节点),插入，如下图

发现第二个叶子节点已经破坏了B+树的性质,则把之分解成[20 21], [37 44]两个,并把21往父节点移，如下图

发现父节点也破坏了B+树的性质,则把之再分解成[15 21], [44 59]两个,并把21往其父节点移，如下图
在这里插入图片描述
这次没有破坏B+树的性质(如果还是不满足B+树的性质,可以递归上去,直到满足为至),插入完毕

例3：往下图的3阶B+树插入100

在这里插入图片描述
首先查找100应插入的叶节点(最后一个节点), 插入，如下图

修改其所有父辈节点的键值为100(只有插入比当前树的最大数大的数时要做此步),如下图

然后重复例2的方法拆分节点,最后得

3.3删除操作

例1：删除下图3阶B+树的关键字91

首先找到91所在叶节点(最后一个节点),删除之，如下图

没有破坏B+树的性质,删除完毕
例2：删除下图3阶B+树的关键字97

首先找到97所在叶节点(最后一个节点),删除之，然后修改该节点的父辈的键字为91(只有删除树中最大数时要做此步)，如下图
例3：删除下图3阶B+树的关键字51

首先找到51所在节点(第三个节点),删除之，如下图

破坏了B+树的性质,从该节点的兄弟节点(左边或右边)借节点44，并修改相应键值,判断没有破坏B+树,完毕，如下图
例4：删除下图3阶B+树的关键字59

首先找到59所在叶节点(第三个节点),删除之，如下图

破坏B+树性质,尝试借节点,无效(因为左兄弟节点被借也会破坏B+树性质),合并第二第三叶节点并调整键值，如下图
例5：删除下图3阶B+树的关键字63

首先找到63所在叶节点(第四个节点),删除之，如下图

合并第四五叶节点并调整键值，如下图

发现第二层的第二个节点不满足B+树性质,从第二层的第一个节点借59,并调整键值，如下图