B树

平衡二叉树

对于一个有序的数组来讲，二分法是效率最高的一种查找算法。基于二分法衍生一种平衡二叉树(AVL树)的数据结构，能减少很多无关数据的搜索，在数据搜索时能大大的提升速度。

Wiki : AVL树（Adelson-Velsky and Landis Tree）是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

平衡二叉树

非平衡二叉树

复杂性

算法	平均	最差
空间	O(n)	O(n)
搜索	O(log n)	O(log n)
插入	O(log n)	O(log n)
删除	O(log n)	O(log n)

对于二叉平衡树，当节点个数在变动的时候，树的结构就会发生旋转调整（有LL，RR，LR，RL四种）。

树的调整过程

通过二叉平衡树，我们能稳定且快速的在线性表中找到目标，比线性扫描速度快很多。

缺点

由于只是二叉树，当数据量很大的时候，树的深度会非常大，搜索的层树会很大。而且在节点插入时会发生很多次旋转，节点插入速度会显著下降。

B树

在计算机科学中，B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树（binary search tree）一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。

一个 m 阶的B树是一个有以下属性的树：

1.每一个节点最多有 m 个子节点
2.每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点
3.如果根节点不是叶子节点，那么它至少有两个子节点
4.有 k 个子节点的非叶子节点拥有 k − 1 个键
5.所有的叶子节点都在同一层

每一个内部节点的键将节点的子树分开。例如，如果一个内部节点有3个子节点（子树），那么它就必须有两个键： a1 和 a2 。在插入节点时，左边子树的所有值都必须小于等于a1 ，中间子树的所有值都必须在 a1 和a2 之间，右边子树的所有值都必须大于 a2 。

一些平衡树只在叶子节点中存储值，而且叶子节点和内部节点使用不同的结构。B树在每一个节点中都存储值，所有的节点有着相同的结构。然而，因为叶子节点没有子节点，所以可以通过使用专门的结构来提高B树的性能。

下面是一个m=4阶树依次插入6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4的演示动画

缺点

B树的插入和删除还是比较麻烦，需要对树进行多次的调整变形。

B+树

B+树是对B树的一种变形扩展，使之具有三个相对与B树更好的优点，1、查询的效率更加稳定，2、IO次数更少，3、范围查询简便。

相对于B树区别如下：

1.B+树有两种类型的节点：内部结点（也称索引结点）和叶子结点。内部节点就是非叶子节点，内部节点不存储数据，只存储索引，数据都存储在叶子节点。

2.内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。

3.每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。

4.父节点存有右孩子的第一个元素的索引。

动画演示如下：

B+树相对与B树的优点

1.单一节点存储的元素更多，使得查询的IO次数更少，所以也就使得它更适合做为数据库MySQL的底层数据结构了。
2.所有的查询都要查找到叶子节点，查询性能是稳定的，而B树，每个节点都可以查找到数据，所以不稳定。
3.所有的叶子节点形成了一个有序链表，更加便于查找。

编号	B树	B+树
1	搜索键无法重复存储。	可以存在冗余搜索键。
2	数据可以存储在叶节点以及内部节点中	数据只能存储在叶节点上。
3	搜索某些数据是一个较慢的过程，因为可以在内部节点和叶节点上找到数据。	搜索速度相对较快，因为只能在叶节点上找到数据。
4	删除内部节点非常复杂且耗时。	删除永远不会是一个复杂的过程，因为元素将始终从叶节点中删除。
5	叶节点不能链接在一起。	叶节点链接在一起以使范围搜索操作更有效。