B+树、、

引出B+树

在B树（B-树）中

第一个需求:将所有的数据，中序遍历一遍(按照顺序遍历所以节点)

按照中序遍历规则，我们需要在多个节点间多次跳动(移动)，效率是比较低的

第二个需求：范围查找，例如我们需要查找50->80之间的值

为了进一步压缩索引层级、降低树高、极致优化范围查询与顺序遍历，在 B 树结构基础上改良优化，衍生出B + 树

B+树的性质/定义

定义

B + 树 是m 阶 B 树的改良优化型多路平衡查找树，是专为数据库、磁盘索引设计的自平衡树结构；核心规则：所有数据记录仅存储在叶子节点，内部节点只存储索引键，不存数据。

性质

1.B+树所有有效元素，都会出现在叶子结点层

2.B+树的所有节点内存有序，并且整体也是有序的

3.B+树中每一个元素都是其对应孩子节点中的最大值

4.B+树中只有叶子结点层的每一个元素才会有一个指向其存储在磁盘中的记录的地址(指针)，而非叶子节点层只作为索引结构。

5.B+树叶子节点层是通过双向链表从左向右连接起来的

B+树相较于B-树的不同/差异

1.m阶B-树最多可以有M个分支，最多可以存储M-1个元素；

M阶B+树，最多可以有M个分支，且最多可以存储M个元素。

2.B-树每一个元素都有直接指向其磁盘中记录的指针；

B+树中只有叶子层中的每一个元素才直接指向其磁盘中记录的指针

3.B-树适合用于随机查找；

B+树适合用于随机查找和范围查找，顺序遍历有元素效率也很高（叶子节点层是通过双向链表从左向右连接起来的）

4.M阶B-树根节点最少得有一个元素，而非根结点最少得有【M/2】-1个元素；

M阶B+树根节点最少有一个元素，而非根结点最少有【M/2】个元素

5.5.B-树，应用于古早的文件系统，和I些特殊的数据库，例如MongoDB和NOSQL数据库，一般作为辅助索引；

B+树作为索引，应用于现有主流磁盘文件系统，关系型数据库索引

B+树的结点的设计

有效结点设计：

1.一个存储有效元素的数组

2.一个存储其孩子结点地址的数组

3.一个存储当前有效元素个数的变量

4.一个指向双亲的指针

5.一个用来表示当前结点时叶节点还是非叶节点

6.一个存储元素对应的磁盘记录的地址的指针数组

#define M 5 typedef int ElemType; typedef struct {}Record;//记录集 typedef enum { LEAF, BRANCH } NodeType; //B+树有效节点结构体设计 typedef struct BPTNode { ElemType key_arr[M + 1]; //1.一个存储有效元素的数组 struct BPTNode* ptr_arr[M + 1]; //2.一个存储其孩子结点地址的数组 int key_num; //3.一个存储当前有效元素个数的变量 struct BPTNode* parent; //4.一个指向双亲的指针 NodeType type; //5.一个用来表示当前结点时叶节点还是非叶节点 Record* recptr[M + 1]; //6.一个存储元素对应的磁盘记录的地址的指针数组 struct BPNode* next; //指向当前叶节点的下一个叶节点 struct BPTNode* prev; //指向当前叶节点的上一个叶节点 }BPTNode; //辅助结点设计 typedef struct BPlusTree { BPTNode* root; //1.存储B+树根节点的地址 BPTNode* first; //2.存储叶子结点层的第一个结点地址 }BPlusTree; typedef struct Result { bool tag; BPTNode* pNode; int index; }Result;