全都是树 BST、AVL、RB、B、B+|数据结构Ⅲ.2

二叉排序树|_{Binary Sort/Search Tree}

定义与性质

二叉排序树，也称二叉检索树、二叉搜索树、二叉查找树等。其英文缩写为 BST。

BST 是一棵空树或具有以下特征的二叉树：

1. 若左子树非空，则左子树上所有的结点都小于根结点；
2. 若右子树非空，则右子树上所有的结点都大于根结点；
3. 左右子树也是一棵二叉排序树。

【经典错误】判断：二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值

【答案解析】错误 ！如下面这棵树所示。
5
/ \
3 6
\ /
8 2

这棵二叉树满足其任一结点的值均大于其左孩子的值，小于右孩子的值，但它并不是二叉排序树，因为在右支路中有$2\lt5$，在左支路中$8\gt5$。不满足二叉排序树的性质。

---

BST 拥有以下几种常见的性质及其推导。

1. 最坏情况下，BST的深度为$n$，此时是一棵单支树或斜二叉树；而理想情况下，深度为$\lceil\log_2(n+1)\rceil$ 也即$\lfloor\log_2n\rfloor+1$.
2. 在任意一棵非空二叉排序树中，删除某一个结点再将其插入，所得二叉排序树可能与原来不同！ 比如删除的结点是分支结点时。
3. 在任意一棵非空二叉排序树中，查找某一个结点时，所经过的关键字构成的序列$(a_1,a_2,\cdots,a_n)$ 中，$\forall i,\;i\in N$ 有$a_j\gt a_i,\;j\gt i$，或$a_j\lt a_i,\;j\gt i$. 即第$i$ 个元素之后的所有元素均大于它或均小于它。

---

沿用我们在 # 树与二叉树|数据结构Ⅲ 一文中创建的 C++ 类模板。
此处，我们创建继承自二叉树基类的 BST：

BST的查找

对于二叉树的查找，很容易想到的做法就是按照一定规则遍历进行查找。

而由于二叉排序树的性质较为特殊，由此我们可以通过对根结点的比较来优化遍历查找的时间复杂度。（类似于二分法的思想）有：

1. 如果目标结点值 = 当前根结点值 则返回；
2. 如果目标结点值 < 当前根结点值，则在当前树的右子树中继续查找，反之亦然。

template<class elementType> 
BinTree<elementType> *BinTree<elementType>::FindTree(elementType x){
    // 非递归法查找结点
    BinTree<elementType> *tree = this;
    while((!tree->isNULL) && (tree->root_data!=x)){
        if(x < tree->root_data){
            tree = tree->left;
        }else{
            tree = tree->right;
        }
    }
    return tree;
}

BST的插入

二叉排序树作为动态树表，其特点是树的结构通常不是一次生成的，而是在查找过程中，当树中不存在与给定值相等的key值时才进行的插入。

插入结点的过程如下：

代码实现：

template<class elementType>
bool BinTree<elementType>::BSTInsert(elementType x){
    // 二叉排序树的插入
    if(this->isNULL){
        this->root_data = x;
        this->isNULL = false;
        this->left  = new BinTree<elementType>();
        this->right = new BinTree<elementType>();
        return true;
    }else if(this->root_data == x){
        return false;
    }else if(this->root_data > x){
        return this->left->BSTInsert(x);
    }else{
        return this->right->BSTInsert(x);
    }
}

BST的创建

二叉排序树的创建可以看作是一颗空树依次对一个个元素进行插入。

此处考虑通过传入函数的数据个数以及对应的数组进行依次插入从而实现二叉排序树的创建。

template<class elementType>
bool BinTree<elementType>::createSortTree(int n, elementType args[]){
    /*
        二叉排序树的创建
        参数：n --节点个数
             args[] --节点的顺序输入数组
             EndFlag --自定义结束符
    */
    this->isNULL = true;
    bool flag = false;
    for(int i = 0; i < n; i++){
        flag = this->BSTInsert(args[i]);
        this->count ++;
        if(!flag){
            this->count = 0;
            this->isNULL = true;
            return false;
        }
    }
    return true;
}

BST的删除

注意：删除结点后必须保证树仍是二叉排序树

根据BST的基本结构，可以梳理得到二叉排序树删除结点的基本算法：

1. 查找待删除结点（同时需要记录一下待删除结点的父结点）；

2. 如果待删除结点为叶子结点，那么直接删除并不会影响BST结构，程序结束。

3. 如果待删除结点左子树存在右子树不存在（或者左子树不存在右子树存在），说明只存在比该结点小（或者大）的子树，于是可以将其子树中存在的一边整体候补上来，程序结束。

4. 如果待删除结点左右子树均存在，则需要按照BST的性质从其左子树（或者右子树）中选择键值最大（最小）的结点（例如右子树的中序序列第一个结点）补到待删除结点的位置才不会破坏结构。

三种情况的示意图如下：

其中，对于第三种情况，因为涉及到了指针的使用，需要多加留意操作步骤：

具体代码：

template<class elementType> 
bool BinTree<elementType>::DeleteBSTNode(elementType x){
    //通过指定键值x对BST进行结点删除
    BinTree<elementType> *front = this,*tree = this;
    while((!tree->isNULL) && tree->root_data!=x){
        if(x < tree->root_data){
            front = tree;
            tree = tree->left;
        }else{
            front = tree;
            tree = tree->right;
        }
    }//循环法查询目标结点，及其父结点
    if(tree->isNULL) return false;//未找到目标结点则返回false
    if(tree->left->isNULL){
        if(front->left->root_data == x){
            front->left = tree->right;
        }else{
            front->right = tree->right;
        }
        tree->right = new BinTree<elementType>();
        delete tree;
        return true;
    }//情况1，只有右子树时，右子树上移，并释放目标结点
    if(tree->right->isNULL){
        if(front->left->root_data == x){
            front->left = tree->left;
        }else{
            front->right = tree->left;
        }
        tree->left = new BinTree<elementType>();
        delete tree;
        return true;
    }//情况2，只有左子树时，左子树上移，并释放目标结点
    BinTree<elementType> *replacePaNode = tree->left->RightmostParent();
    if(front->left->root_data == x){
        front->left = replacePaNode->right;
    }else{
        front->right = replacePaNode->right;
    }//情况3，找到左子树最右结点并替换目标结点
    replacePaNode->right->left = tree->left;
    tree->left = new BinTree<elementType>();
    replacePaNode->right->right = tree->right;
    tree->right = new BinTree<elementType>();
    delete tree;
    replacePaNode->right = new BinTree<elementType>();
    //更新指针域的指向，并删除目标结点
    return true;
}

template<class elementType> 
BinTree<elementType> *BinTree<elementType>::RightmostParent(){
    // 循环法 查找当前树的最右结点(一定是叶子结点)
    // 返回其父亲结点
    BinTree<elementType> *tree = this,*front = this;
    while((!tree->isNULL) && (!tree->right->isNULL)){
        front = tree;
        tree = tree->right;
    }
    return front;
}

事实上，也可以不通过指针调整的方式实现非终端结点的删除。只需找到其中序后继或前驱结点后，将它们的数值进行交换，问题就转变成删除该后继结点了。此后继结点或是叶结点或是只有左子树或只有右子树的结点，删除之都比较方便，只需将其孩子结点往上替补即可。

编程仿真

此处将综合上述代码，整体集成到bintree.h和bintree.cpp文件中，用C++实现链式二叉排序树的以下操作：

仿真要求清单

1. 输入数据个数 DataCount（要求在 10 和 20 之间）
2. 输入数据最大值 MaxData（在 50 和 100 之间）
3. 在 0 和 MaxData 之间，随机产生 DataCount 个不重复的整数，按产生先后顺序形成一个数据序列，并输出该序列
4. 利用上述数据序列，创建一个二叉排序树
5. 统计该二叉树的高度并输出该二叉树的叶子节点
6. 中序遍历该二叉排序树，输出遍历序列，验证创建的二叉排序树 是否正确

文件架构

.
├── BinaryTree_src
│   ├── bintree.cpp
│   ├── bintree.h
│   └── CMakeLists.txt
├── CMakeLists.txt
└── main.cpp

主函数

#include"Graph_src/graph.h"
#include"Graph_src/graph.cpp" //引入自写图库
#include"BinaryTree_src/bintree.h"
#include"BinaryTree_src/bintree.cpp" //引入自写二叉树库
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string.h>
#define DataCount 20 //宏定义最大数据个数
#define MaxData 100 //宏定义最大数据值
#define random(x) rand()%(x)+1 //宏定义随机数生成函数
using namespace std;

void RandomNum(int args[], int count,int data_max);

int main(void){
    int args[DataCount];
    memset(args,-1,DataCount);//初始化
    
    int count = 0,data_max = 0;
    while(count < 10 || count > 20){
        cout << "请输入数据个数(10~20):";
        cin >> count;
    }
    while(data_max < 50 || data_max > 100){
        cout << "请输入数据最大值(50~100):";
        cin >> data_max;
    }
    
    RandomNum(args,count,data_max);//生成随机数
    
    for(int i = 0; i < count; i++){
        cout << args[i] << " ";
    }
    cout << endl;//输出

    BinTree<int>* BST = new BinTree<int>();
    BST->createSortTree(count,args);//创建排序树

    cout << "树的高度为：" << BST->getHight() << endl;

    cout << "输出 二叉排序树(中序遍历)：" << endl << BST << endl;

    int res[DataCount] = {0};
    int num = BST->getLeafNode(res);
    if(num){
        cout << "输出 叶子节点：" << endl;
        for(int i = 0; i < num; i++)
            cout << res[i] << " ";
    }
    cout << endl;
 	BinTree<int>* newBST = BST->CopyTree();//深度复制
    cout << "输出 复制的树：" << endl << newBST << endl;
    int select = 0;
    while(select!=1 && select!=2){
        cout << "请输入需要查找的树:(1.源树；2.复制树)" << endl;
        cin >> select;
    }
    int x;cout << "请输入需要查找的节点数据：";cin >> x;
    BinTree<int>* searchRes;
    switch (select){
        case 1:searchRes = BST->FindTree(x);break;
        case 2:searchRes = newBST->FindTree(x);break;
    }
    if(searchRes->isNULL) cout << "[Error]目标树中没有该结点！" << endl;
    else{printf("找到目标结点：[地址: %p]\n",searchRes);} 
    cout << "请输入需要在副本中删除的节点数据：";cin >> x;
    if(newBST->DeleteBSTNode(x))
        cout << "[Success]删除成功;当前副本中序遍历为：" << newBST << endl;
    else
        cout << "[Error]删除失败." << endl;
    
    cout << endl <<"正在将二叉树转为邻接表……" << endl;
    ALGraph<int>* graph = new ALGraph<int>(BST);
    cout << "[Success]转换成功" << endl;
    int res[MAXVEXMUN];
    graph->TopSort(res);
    cout << endl <<"输出拓扑排序：" << endl;
    for(int i = 0; i < graph->VexNum; i++){
        cout << res[i] << " ";
    }
    cout << endl;
    return 0;
}

void RandomNum(int args[], int count,int data_max){
    int i = 0;
    srand((unsigned)time(NULL));
    while(i < count){
        int j;
        int temp = random(data_max);
        for(j = 0; j < i; j++){
            if(args[j] == temp)
                break;
        }
        if(j == i)
            args[i++] = temp;
    }
}

平衡二叉树|_{Balanced Binary Tree}

定义与性质

对于 BST 的查找来说，其查找效率随着创建时输入的元素顺序不同而有所不同。最坏情况下会形成一棵单支树，此时深度为$O(n)$，平均查找长度也会降低。

为了避免 BST 高度增长过快的这种缺陷，我们规定在插入和删除结点时，还需保证：任意结点的左右子树高度差的绝对值不超过1。

我们称这样的二叉排序树为 平衡二叉树（Balanced Binary Tree），简称平衡树。

此外，我们也称平衡二叉树为 AVL 树。
AVL 提出平衡二叉树的两位大学教授 G.M. Adelson-Velsky 和 E.M. Landis 名称的缩写。

平衡树是一棵空树或具有以下特征的二叉树：

1. 左右子树高度差的绝对值不超过1；
2. 左右子树也是一棵平衡二叉树。

平衡因子 |Balance Factor, bf

定义 平衡因子（bf）：结点的左子树的深度减去右子树的深度。
即： 结点的平衡因子 = 左子树的高度 - 右子树的高度 。

在 AVL树中，所有节点的平衡因子都必须满足$-1\leq bf\leq 1$.

相关性质

1. 若 AVL 的高度为$h$ ，平衡因子$bf=1$，则其结点总数$N_h=N_{h-1}+N_{h-2}+1$，初始条件为：$N_0=0,N_1=1,N_2=2$. (这也是已知层数求最少 AVL 结点的递推式)
2. 含有$n$ 个结点的平衡二叉树最大深度为$O(\log_2n)$，其平均查找长度也为$O(\log_2n)$.
3. 对 AVL 中序遍历若可得到一个降序序列，则树中最大元素一定无左子树。
4. 在非空 AVL 树中删除某结点再插入回来得到的新树，无论该结点原本是不是叶结点，都有可能与原来不同。

---

AVL的插入

当我们对 BST 进行插入（或删除）时，都有可能造成整棵树的不平衡，即平衡因子超出 AVL 定义范围的情况。所以，为了保证二叉树的平衡， AVL 树引入了所谓监督机制。即在树的某一部分发生不平衡度时触发相应的平衡操作，以保证树平衡因子维持原设。

接下来，我们将介绍出现不平衡时的 4 中情况，及其调整规律。

可点击进入 美国旧金山大学提供的 # AVL树在线插入删除可视化网站 更直观地感受 AVL 树

LL & RR 型

LL型平衡问题，就是在根结点$n$ 的左孩子（L）的左子树（L）插入了新结点$u$ ，导致整棵树失去平衡的情况。
如下图所示，解决此问题的方法是对整棵树进行 “右旋”操作。

右旋：将左子树$i$ 往右上角移动，同时使得原来的根结点$n$ 右下移动；于是$n$ 退化为了$i$ 的右子树根结点，而$i$ 原本的右子树 (蓝色三角) 被$n$ 所继承为左子树。

而RR型平衡问题，就是在根结点$n$ 的右孩子（R）的右子树（R）插入了新结点$u$ ，导致整棵树失去平衡的情况。
这与 LL型是完全对称的，为此我们需要进行左旋。

---

LR & RL 型

LR型平衡问题，就是在根结点$n$ 的左孩子（L）结点$i$ 的右孩子（R）结点$k$ 中插入了新结点$u$ ，导致整棵树失去平衡的情况。

如下图所示。可以 对$i$ 进行左旋，再对$n$ 进行右旋，从而解决问题。

同理，LR型这里不再赘述了。

AVL的删除

AVL 的删除与插入类似，首先利用 BST 的算法删除结点，然后从该结点向上回溯，找到第一个不平衡的结点（即最小不平衡子树），对该子树进行和插入类似的平衡调整，若调整后继续往上回溯时还不平衡，则继续对当前的最小不平衡子树继续调整，该过程有可能回溯到根结点。

AVL的创建

待更

红黑树|_{Red–Black Tree}

https://www.tw.3822808.com/baike-红黑树

定义和性质

• 性质1：每个节点要么是黑色，要么是红色。
• 性质2：根节点是黑色。
• 性质3：每个叶子节点（NIL）是黑色。
• 性质4：每个红色结点的两个子结点一定都是黑色。
• 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

---

此外还有其他性质，如下：

♾️如果红黑树的所有结点都是黑色，则它一定是一棵满二叉树

RB树的插入

插入结点默认是红色。

1. 如果父结点是黑色，无需处理。
2. 如果插入结点前为空树，插入结点自己就是树的根结点，则改为黑色，结束。
3. 如果父结点是红色，并且叔结点是黑色，但插入结点是右孩子，则插入结点左旋，即变为情况4。
4. 如果父结点是红色，并且叔结点是黑色，但插入结点是左孩子，则父结点和爷结点交换颜色，并右旋，结束。
5. 如果父结点是红色，并且叔结点是红色，则父结点、叔结点的红色变黑色，爷结点变红色，此时爷结点作为新的插入结点往上推两层。

可点击进入 美国旧金山大学提供的 # 红黑树在线插入删除可视化网站 更直观地感受 RB 树

RB树的删除

待删结点只有右孩子或只有左孩子，其孩子必然是红色（否则违反了性质5），此时直接当孩子着色为黑色，替补自己即可。

待删结点没有孩子，且自己是红色，则可直接删除。
待删结点没有孩子，但自己是黑色，需将自己的虚拟子结点（黑色）代替自己的位置，并且将其附上双重黑色，变为双黑结点，并在后续几种情况中消去双黑属性。

1. 兄弟结点是红色，则将兄弟结点与父结点换色，并对父结点左旋。这样可以让新的兄弟结点变为黑色。即变为了情况2。
2. 兄弟结点是黑色，并且兄弟结点的孩子左红右黑，则交换兄弟结点和其左孩子的颜色，然后兄弟结点右旋，这样可以使得新的兄弟结点右孩子是红色。即变为了情况3。
3. 兄弟结点是黑色，并且兄弟结点的孩子右孩子为红色，则交换兄弟结点和父结点的颜色，兄弟结点的右孩子变黑，然后父结点左旋。此时双黑结点退化为一重黑，完成修正。
4. 兄弟结点是黑色，并且兄弟结点的孩子均为黑色，则双黑结点与其兄弟结点同时退化一重黑色，双黑结点变为黑色结点，兄弟结点变为红色结点，然后将父结点套上一层黑色，把父结点作为新的待调整结点，往上一层推。

B & B+树|_{B-Tree & B+Tree}

注意：B树的英文名是 B-Tree，因此也有翻译将B树称为 “B-树”，而其中的 - 符号属于连接符，而不是“减号”，与 B+树中的 + 号不做对应，也不读作“B减树”！

B树的定义

$B$ 树，又称多路平衡查找树，B 树中所有结点的孩子个数的最大值称为 B 树的阶，通常用$m$ 表示。

一棵$m$ 阶$B$ 树或为空树，或为满足如下特性的$m$ 叉树：

1. 树中每个结点至多有$m$ 棵子树，即至多含有$m - 1$ 个关键字
2. 若根结点不是终端结点，则至少有两棵子树
3. 除根结点外的所有非叶结点至少有$\lceil m/2\rceil$ 棵子树，即至少含有$\lceil m/2\rceil-1$ 个关键字，根结点若不是叶结点，则至少有 2 棵子树
4. 所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）
5. 所有非叶结点的结构如下：

其中，$K_i\quad ( i = 1, ... ,n)$ 为结点的关键字，且满足$K_1 \lt K_2 \lt \cdots \lt K_n$，$P_i ( i = 0, 1, .... , n)$ 为指向子树根结点的指针，且指针$P_{i-1}$ 所指子树中所有结点的关键字均小于$K_i$，$P_i$ 所指子树中所有结点的关键字均大于$K_i$。而$n$ 即为结点中关键字的个数。$(\lceil m/2\rceil-1\leq n\leq m-1)$

由此也可以看出，有$n$ 个关键字的$B$ 树，其插入失败的可能性有$n+1$，即查找失败结点的个数是$n+1$.

B 树是平衡因子均为0的多路平衡查找树

下图是一棵 4 阶$B$ 树，其中关键字为英文辅音字母，淡色部分是查找字母$R$ 时的路径结点。

B树的高度

首先声明，此处讨论的高度不包括最后一层，即不带任何信息的叶子结点/终端结点/虚拟结点 那一层。（有的教材则包括此层）

对任意一棵包含$n\quad(n\geq1)$ 个关键字，高度为$h$，阶数为$m$ 的 B树：

• 当每个结点尽最大可能地分支子树时，每个结点均有$m-1$ 个关键字，从而分支出$m$ 棵子树；从而关键字个数$n\leq(m-1)\times(1+m^1+m^2+\cdots+m^{h-1})=m^h-1$.
  即：

$$h\geq\log_m(n+1)$$

• 当每个结点尽最大可能地不分支子树时，因为树非空，所以第一层至少 1 个结点、第二层至少 2 个结点，此后每个结点只含有$\lceil m/2\rceil-1$ 个关键字，分支出$\lceil m/2\rceil$ 棵子树，即第三层至少有$2\lceil m/2\rceil$ 个结点，以此类推，第$h$ 层有$2(\lceil m/2\rceil)^{h-1}$ 个结点。而第$h+1$ 层是查找不成功的终端结点，其个数为结点数+1，即$n+1$，所以有$n+1\geq2(\lceil m/2\rceil)^{h-1}$.
  即：

$$h\leq\log_{\lceil m/2\rceil}\left(\frac{n+1}2\right)+1$$

🔔综上，已知关键字个数为$n$ 的情况下，$m$ 阶$B$ 树的高度的取值范围是：

$$\log_m(n+1)\leq h\leq\log_{\lceil m/2\rceil}\left(\frac{n+1}2\right)+1$$

---

此外，根据类似的推论，我们还有已知高度情况下对结点数、关键字个数的最值讨论：

♾️ 一棵含有$n$ 个非叶结点的$m$ 阶$B$ 树中，包含的关键字个数至少为：$(n-1)(\lceil m/2\rceil-1)+1$

【推导】按每个结点包含的最少的关键字个数计算，根结点至少1个关键字，剩下的$n-1$ 个非叶结点至少包含$\lceil m/2\rceil-1$ 个，故一共是$(n-1)(\lceil m/2\rceil-1)+1$ 个。

B树的插入

B树的插入主要有两个步骤：定位和插入。

对插入关键字的定位过程其实也就是其查找过程。包含两个基本操作：

1. 在 B 树中找到所属结点
2. 在结点内查找关键字，若找到则查找成功；若没找到，通过其区间范围得到指向下一棵子树（子结点）的指针信息，并转到第一步，直到指针为空（查找到了虚拟结点）则查找失败

关键字的定位则对应着查找失败的情况，通过查找失败的信息可以得到应该将此关键字插入的最底层非终端结点的插入位置。

接下来是插入过程。

1. 如果树为空，则分配根结点并插入关键字。
2. 如果树不为空，且插入到插入位置后，满足B树定义，即结点内关键字个数不超过$m-1$，则插入成功，结束。
3. 如果插入到结点后使得其“溢出”，则在中位数处进行左右分裂；
4. 将中位数插入原结点的父结点内，即向上提升中间字；然后将左部分设为左子级，将右部分设为右子级。
5. 如果上述操作导致父结点也“溢出”，则进行对父结点进行分裂，重复上述过程，若一直上推到根结点，则B树高度+1。

下面是一个$m=3$ 的$B$ 树，依次插入：8、9、10、11、15、16、17、18、20、23 的过程示例。

B树的删除

与 B 树的插入相对，若删除结点后使得结点内的关键字个数低于最低要求$\lceil m/2\rceil-1$ 则会出现“下溢”，为此需要进行适当调整。

我们先对各自情况进行梳理。

情况一：待删关键字位于叶中（此处的叶并非最底层的终端虚拟结点，而是有关键字的最后一层结点）

1. 若删除之并未造成“下溢”，则直接删除；
2. 若删除之造成“下溢”，且向兄弟结点中借一个关键字不会造成兄弟结点“下溢”的情况下，进行父子换位法：左兄弟的最右关键字上升到父结点，父结点中相邻关键字下降到被删除的结点中以维持平衡。（或者右兄弟的最左关键字上升）
3. 若兄弟结点“不够借”，则将当前结点与兄弟结点进行合并，连接两个兄弟结点的父结点的关键字也需下降和它们合并到一起。
4. 若因为上述第三步导致父结点的关键字个数不符合B树要求，则对父结点递归进行调整，直到满足 B树要求为止。

情况二：待删关键字位于非终端结点

被删关键字$k$ 在非终端结点上时，可以将其前驱或后继$k'$ 代替它现在的位置，然后在$k'$ 所处的结点中删除之。此时问题转化为了 情况一。

B+树的基本概念

$B+$树是应文件系统所需而产生的$B$ 树的变形，比起 B 树更加适用于实际的操作系统文件索引和数据库索引，因为其磁盘读写代价更低，查找效率更加稳定。

一棵$m$ 阶的$B+$ 树需满足下列条件：

1. 每个分支结点最多有$m$ 棵子树
2. 非叶根结点至少有两棵子树，其他每个分支结点至少有$\lceil m/2\rceil$ 棵子树（要追求“绝对平衡”，即所有子树高度要相同）
3. 结点的子树个数与关键字个数相等（B树中关键字比子树少一个）
4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来（支持顺序查找）
5. 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针

解释： 上面图示中的索引 【15、56】 和 【 3、9、15】 以及 索引 【35、42、56】 是存在不同的磁盘块里面的。
每查找一次结点都要进行一次读磁盘的操作，直到找到最下面的叶子结点，每次读取磁盘块都是一次慢速操作，所以要让树尽可能矮。一个磁盘块只有 1KB 大小，为了让一个磁盘块尽可能包含索引信息， B+树 要求非叶子结点只包含索引和地址，不包含记录。

B树与B+树的比较

关键字个数

$m$ 阶$B+$ 树 结点中$n$ 个关键字对应$n$ 棵子树
$m$ 阶$B$ 树 结点中$n$ 个关键字对应$n + 1$ 棵子树

$m$ 阶$B+$树 根结点的关键字数$n \in [1, m]$，其他结点的关键字数$n \in [\lceil m/2\rceil, m]$
$m$ 阶$B$树 根结点的关键字数$n \in [1, m - 1]$，其他结点的关键字数$n \in [\lceil m/2\rceil-1, m-1]$

关键字重复

$m$ 阶$B+$树 中，叶结点包含全部关键字，非叶结点中出现过的关键字也会出现在叶结点中
$m$ 阶$B$ 树 中，各结点中包含的关键字是不重复的

存储地址

$m$ 阶$B+$树 中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址
$m$ 阶$B$ 树 的结点中都包含了关键字对应的记录的存储地址

顺序查找

$m$ 阶$B+$树 中，叶结点包含全部关键字，可以顺序查找，同时也支持随机查找
$m$ 阶$B$ 树 只能随机查找