今天主要讲的是在查找时常用的数据结构：平衡二叉树，B-树和B+树。
今天所有的学习知识都是参考严蔚敏教授的《数据结构》这本书，由于这本书是从查找表这章引入的B树，B+树和B-树，所以，我们就先从查找表讲起，并在里面扩充一些常见的知识点。

查询表

查找表（search table）是一种数据结构，常见的操作有：

1. 查询某个元素是否在查找表中
2. 查询某个元素的属性
3. 在查找表插入一个元素
4. 在查找表中删除某个元素

根据这常见的四个操作，查找表可以分为静态查找表和动态查找表。如果只对查找表的元素进行前两中“查询”操作，则此类查询表为静态查询表；若对查找表中元素进行“更新”操作（增删操作），则此类查询表为动态查询表。

静态查询表

对于查找表的查询操作，归其本源还是一个遍历的过程。
而对于有序表的操作，直接解决思想就是二分法或者叫折半查找法。（注：这里的这般查找法仅限于顺序存储结构，对线性链表不能使用）
进行查找的方法除了折半查找之外(将元素每次二等分)，还有斐波那契查找(将元素每次斐波那契序列等分)。

斐波那契查找

如果将表按照斐波那契序列的值（如下所示）进行分割
$$F_0=1,F_1=1,F_i=F_{i-1}+F_{i-2},i>1$$
使得每个元素段中元素的个数为$F_i$。假设开始时，表中记录个数n比某个斐波那契数位上的数小，假设这个为arr[$F_i$]。先将n和下标为$F_{i-1}$的数（假设为arr[$F_{i-1}$]）进行比较：
若相等则查找成功；
若n<arr[$F_{i-1}$]，则继续在arr[:$F_{i-1}$]查找(不再查询arr[$F_{i-1}$]本身)；
若n>arr[$F_{i-1}$]，则继续在arr[$F_{i-1}$:$F_i$]查找(不再查询arr[$F_{i-1}$]和arr[$F_i$])。

动态查询表

动态查找表的特点是，表结构本身是在查找过程中动态生成的，对于给定值，若表中存在，则查找成功返回；否则插入。

二叉排序树

二叉排序树又叫二叉查找树，是具有以下性质的二叉树：

1. 若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值，
2. 若他的右子树不为空，则右子树上所有结点的值均大于它的根结点的值，
3. 他的左,右子树，也分别为二叉排序树。

值得注意的是：二叉排序树不能为空！！！
举个二叉排序树的🌰：

查找过程：
当二叉排序树，不为空时

1. 将给定值和根结点的关键字进行比较，如果相等，则查找成功
2. 若该值比根结点的关键字，则在左子树上继续查找。
3. 若该值比根结点的关键字大，则在右子树上继续查找。

添加：
查找不成功时，在查找路径上访问的最后一个结点上添加一个新的叶子结点，根据该值和最后结点的关键字的大小决定加入左孩子或者右孩子结点。

删除：
假设在二叉排序树上删除的结点为p，他的父结点为f，即指向该结点的指针为p，指向该结点的父结点的指针为f，

1. 若P结点为叶子结点，直接删去叶子结点，不会破坏整棵树的结构，则只需要修改其父结点的指针为空即可。
2. 如果p结点只有左子树或者只有右子树的话，此时只需要令左子树或右子树直接成为其父结点的子树即可（具体是父结点的左子树还是右子树需要具体根据值的大小判断）。
3. P结点的左子树和右子树均不为空，如图所示，s为p的最大子结点（直接前驱）。
   
   删去p之后，为了保证其他元素之间的相对位置不变，可以有两种做法：其一是令p的左子树为f的左子树，而p的右子树为s的右子树，结果如图所示。
   
   其二是p的直接前驱代替p，然后再从二叉树中删除它的直接前驱。当以直接前驱代s代替p时。由于s只有左子树sL，则删去s之后要令sL为Q的右子树。结果如图所示。
   

平衡二叉树

平衡二叉树，又称为AVL树，它可以是一棵空树，也可以是具有以下性质的二叉树：它的左右子树都是平衡二叉树，且左子树和右子树的深度之差 绝对值不超过1。所以，对于平衡二叉树来说，它不仅要保持二叉排序树的特性，又要保持平衡。

B-树

这里要弄明白一个概念，B-树就是B树。B树的英文就是B-tree。

B-树是一种平衡的多路查找树，它在文件系统中很有用，在此先介绍这种树的结构。
一棵m阶的B-树，或为空树，或为满足以下特征的m叉树：

1. 排序方式：所有结点关键字是按递增次序排列，并遵循左小右大原则
2. 子结点数：2<=非叶结点的子结点数<=m （注：m阶代表一个树结点最多有多少个查找路径，m=m路,当m=2则是2叉树,m=3则是3叉）
3. 除根之外，所有非终端结点至少有⌈m/2⌉棵子树。所有非终端结点都包含信息$(n,A_0,K_1,A_1,...,K_n,A_n)$。
   n：关键字的个数，⌈m/2⌉-1<=n<=m-1；$K_i$：关键字，且$K_i<K_{i+1}$；$A_i$：指向子树根结点的指针，且指针$A_{i-1}$所指子数中所有结点的关键字均小于$K_i$。$A_n$所指的子树中所有结点的关键字均大于$K_n$。
   这个有点拗口？那就这样理解，每个结点里面会有n个元素(关键值)，有n+1个指针把n个元素分成n+1块，比如|4|7|表示一个结点，第一个|表示第一个指针，指向的结点的关键字都是<4的，第二个|表示第二个指针，4<指向的结点的关键字<7，第三个|表示第三个指针，指向的结点的关键字都是>7的。
4. 所有叶子结点均在同一层、叶子结点除了包含了关键字和关键字记录的指针外也有指向其子结点的指针只不过其指针地址都为null（不带信息）。

在B-树上进行查找的过程和二叉排序树的查找类似，在B-树中查找节点，包含两种基本操作：1.在B-树中查找结点；2.在结点中查找关键字。
比如在这B-树数上查找关键字47的过程如下：首先从根结点开始，根据根结点t找到a结点中的关键字35，47>35。顺着指针找到c节点，该节点有两个关键字43和78，43<47<78，同样顺着指针找到g结点在该节点中顺序查找，找到关键字47由此查找成功。

插入：
由于B-树结点中的关键字个数必须>=⌈m/2⌉, 因此每次插入一个关键字并不是在树中简单添加一个叶子结点即可，而是首先在最底层的某个非终端节点中添加一个关键字，若该节点的关键字个数n不超过m-1，则插入完成，如下图(a)(b)。否则就要产生结点的分裂，如下图©(d)。(就是让B-树结点中的关键字个数n一直满足⌈m/2⌉-1<=n<=m-1，当n为m时，就需要将结点分裂，多加一个孩子结点，以此来保证n每个结点的关键字的个数的范围)。


删除：
如果在B-树上删除一个关键字，则首先应找到该关键字所在的结点，并从中删除，若该节点为最下层的非终端节点，且其中的关键字数目不小于⌈m/2⌉，则删除完成，如下图(a)(b)删除61。否则要进行合并节点的操作，如下图©(d)删除37。
删除里的合并和添加里的分裂性质是一样的，都是为了保证n每个结点的关键字的个数的范围。

B+树

B+树(B±tree)是应文件系统所需而出的一种B-树的变型树，一棵m阶的B+树和m阶的B-树的差异在于：

1. 有n棵子树的结点中含有n个关键字。
2. 所有的叶子节点中包含了全部关键字的信息以及指向含这些关键字记录的指针，而叶子结点本身关键字的大小自小而大顺序连接。
3. 所有的非终点节点，所有的非终端节点可以看成是索引部分，节点中仅含有其子树(根节点)中的最大值(或最小值)关键字。

放一张维基百科上的B+树示例图：

在B+树上进行随机查找，插入和删除的过程基本上与B-树类似，只是在查找时，若非终端结点上的关键字等于给定值，并不终止，而是继续向下，直到叶子结点。因此在B+树中，无论查找是否成功，每次查找都是走了一条从根到叶子结点的路径。B+树查找的分析类似于B-树，B+树的插入仅在叶子结点上进行，当结点的关键字个数大于m时，要进行分裂。并且B+树的删除，也仅在叶子结点进行，当叶子结点中的最大关键字被删除时，当结点的关键字个数小于⌈m/2⌉时，要进行合并。

对于B+树这样看起来好像也没什么特别之处啊，我参考了这篇博客: 从B树、B+树、B*树谈到R 树.
B+树的优点：

1. B+树的内部结点并没有指向关键字具体信息的指针，因此其内部结点相对B 树更小。
2. B+树的查询效率更加稳定。查找必须走完一条从根结点到叶子结点的路，所以所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。(我觉得这并不能算是一个很好的优点)

我还在链接: 平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了.这篇博客里看到了关于B+树的其他优点：
1. B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
2. B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
3. B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
4. B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

总的来说，通过这次学习，你应该了解到各种树的插删查的思路。

本文参考：
数据结构(C语言版) 严蔚敏 吴伟民
从B树、B+树、B树谈到R 树
平衡二叉树、B树、B+树、B树 理解其中一种你就都明白了