一文搞懂Mysql为什么要使用B+树
一文搞懂Mysql为什么要使用B+树
在数据库系统中，索引结构的选择对查询性能有着至关重要的影响。本文将从二叉查找树（BST）开始，逐步介绍AVL树、红黑树和B树，最终解释为什么MySQL选择B+树作为其索引结构。
一文搞懂Mysql为什么要使用B+树
前言
首先我们要知道，Mysql中Innodb和MyIsam都使用了B+树底作索引结构。为什么要引入索引，是为了增大查询效率，减少磁盘IO次数，毕竟Mysql的数据是存在磁盘里的。查找效率最高的肯定是hash，时间复杂度只有O(1)，但是这仅限于等值查找，如果是范围查找，就又得变成O(n)。所以Mysql选择了二分查找的策略，将查找的时间限制在O(logN)的级别。接下来我们从最简单的二叉查找树开始，逐步说明各种树解决的问题，以及面临的新问题，从而说明MySql为什么选择B+树作为索引结构。
二叉查找树(BST)：不平衡问题
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。如下是一棵BST树：
BST树在理想情况可以实现logN级别的查找，N是树中节点的个数。但是BST树会出现不平衡的情况，例如左子树的节点个数比右子树大很多，甚至在极端情况下，BST树会退化为链表，如下面的图所示，这个时候查找的复杂度就会退化为O(N)。
平衡二叉树(AVL)：旋转耗时
AVL树是严格的平衡二叉树，所有结点的左右子树高度差不能超过1，解决了BST树可能出现不平衡的问题，因此插入，查找和删除的复杂度在平均和最坏情况下都是O(logN)
但是AVL树实现平衡的关键在于旋转操作，插入和删除可能破坏树的平衡，因此需要通过一次或多次树旋转来重新平衡这个树。当插入数据时，最多只需要1（单旋转或者双旋转）次，但是删除数据时AVL需要维护从删除结点到根结点这条路径上所有节点的平衡，复杂度量级为O(logN)。
因为AVL树的旋转耗时，在删除数据时的效率很低，在删除操作较多时，维护平衡所需的代价可能高于其带来的好处，因此AVL实际使用并不广泛。
上面设计到的旋转操作，大家感兴趣的话可以看这个视频平衡二叉树(AVL树)，我觉得讲的很清楚。
红黑树：树太高
与AVL树相比，红黑树并不追求严格的平衡，而是大致的平衡：只是确保任一结点左右子树的高度相差不超过两倍。从实现来看，红黑树的最大特点是每个结点都属于两种颜色（红色或黑色）之一，且结点颜色的划分需要满足特定的规则：
- 根和叶子（NULL）都是黑色
- 不存在两个连续的红色结点
- 任意结点到叶子结点所有路径黑节点数量相同。
下面为一个红黑树的示例（图画的不好请见谅/(ㄒoㄒ)/~~）：
与AVL树相比，红黑树的查询效率会有所下降，这是因为树的平衡性变差，高度更高。但红黑树的删除效率大大提高了，因为红黑树同时引入了颜色，当插入或删除数据时旋转效率要比AVL树提升很多，只需要O(1)的复杂度，所以总的来说红黑树效率高于AVL。
对于数据在内存中的情况（如STL中的set），红黑树的表现是非常优异的。但是对于数据在磁盘中的情况（如Mysql），由于红黑树的树太高，导致磁盘IO次数过大，严重影响性能。
B树：为磁盘而生
B树也称B-树，是为磁盘等辅存设备设计的多路平衡查找树，与二叉树相比，B树的每个非叶节点可以有多个子树。因此，当总节点数量相同时，B树的高度远远小于AVL树和红黑树(B树是一颗“矮胖子”)，磁盘IO次数大大减少。
定义B树最重要的概念是阶数，对于一个m阶的B树，需要满足一下条件：
- 每个结点最多包含m-1个key。
- 每个结点最多有m条分支。
以一颗5阶的b树为例：
B树的优势除了树矮，还有对局部性原理的运用。B树将键相近的数据存储在同一个节点，当访问其中某个数据时，数据库会将该整个节点读到缓存中；当它临近的数据紧接着被访问时，可以直接在缓存中读取，无需进行磁盘IO；换句话说，B树的缓存命中率更高。
但是B树还有问题，就是他不适合范围查询，如果做范围查询的话，就需要中序遍历，时间复杂度是O(n)，需要多次进行磁盘IO效率很低。
B+树：更快的范围查询
为了解决B树范围查询效率低下的问题，B+树主要在B树上做了如下改动：
- 非叶子节点只存索引，叶子节点才存数据。
- 叶子节点之间通过单向链表连接
因为Innodb中每个结点使用一个页（16KB），因此B+树和B树相比，非叶子节点没有存数据，所以每个结点可以存的个数比B树要多很多，因此B+树更矮。并且Innodb中叶子结点之间使用双向链表连接，要更适合范围查询。
对于一个3层B+树，第一层有一个页面，可以存储1000条记录，第二层有1000个页面，可以存储1000*1000条记录，第三层，因为是叶子节点存的有数据，假设每个页面可以存100条数据，那就是1000×1000×100=1亿条数据，而二叉树要存1亿条数据大概需要26层左右。