MYSQL索引与B+树

MYSQL索引与B+树 什么是索引？

索引是一种排好序的可以快速查找数据的数据结构

各种数据结构的索引分析 没有索引

假如我们没有使用索引。并且总数据有1000条。
当执行sql ： == select * from t_user where id = 500 ==，时，就会对id进行比较1000次，从而找到id=500的数据记录。也就是我们讲的，全局扫描。

链表

假如我们使用链表为id做索引。当执行sql ： select * from t_user where id = 500时。
就会在链表中进行比较查找，当查找到第一个id=500时表示要找的数据已经开始，当顺序查找到最后一个id=500时，表示要查找的数据已经结束（因为索引是有顺序的）。
假如，id=500的数据在1000条数据的第499,500,501位时。那此次比较就进行502次比较。
加快了查询效率。

但是链表并不适合做索引。

因为效率太低了。
我们知道链表的查询效率是O(n)。就像上面的例子，遍历了502次才找到符合条件的记录，这是很低效的。而我们知道，数组+二分查找的效率是O(lgn)，但是数组的插入元素以及删除元素的效率很低，因此使用数组做为索引结构并不合适。

另外，在选择数据库索引的结构的时候，要考虑到另一个问题。索引是存在于磁盘中，当索引非常大的时候，达到几个G的时候，无法一次加载到内存中。

考虑到上面两个因素，数据库中索引使用的是树形结构。

总结：效率低

二叉树

二叉树的查找时间复杂度可以达到O(log2(n))。

二叉树：

二叉树搜索相当于一个二分查找。二叉查找能大大提升查询的效率，但是它有一个问题：二叉树以第一个插入的数据作为根节点，如上图中，如果只看右侧，就会发现，就是一个线性链表结构

如果我们要查询的数据为4，则需要遍历所有的节点才能找到4，即，相当于全表扫描。所以二叉树也并不适合做索引。

总结：效率低，而且并不能解决磁盘IO加载到内存的问题

平衡二叉树

如果上图中平衡二叉树保存的是id索引，现在要查找id = 8的数据，过程如下：

把根节点加载进内存，用8和10进行比较，发现8比10小，继续加载10的左子树。把5加载进内存，用8和5比较，同理，加载5节点的右子树。此时发现命中，则读取id为8的索引对应的数据。

索引保存数据的方式一般有两种：

数据区保存id 对应行数据的所有数据具体内容。数据区保存的是真正保存数据的磁盘地址。

平衡二叉树很好的解决了二叉树的线性链表结构问题。
但是平衡二叉树也并不合适做索引。
1.因为结构问题，当数据量很大时候，就会造成树的深度是很大，如果查找的数据在根节点还好，如果在叶子结点，就会造成多次IO。而IO是比较耗时的。
2.每个节点存储的数据内容太少，没有很好的利用 *** 作系统和磁盘的数据交换特性。也没有利用好磁盘IO的预读能力。 *** 作系统和磁盘之间的一次数据交换是以页为单位的。一页大小为4K，即一次IO *** 作系统会将4K（整倍数）的数据加载到内存中。但是二叉树每个节点值保存了一个关键字，一个数据区，两个子节点的引用，并不能填满4K的内容。辛辛苦苦的一次IO *** 作，只加载了一个关键字。
所以平衡二叉树也并不适合做索引。

总结：解决了线性链表结构，但是树深度大，不能很好利用IO缓存。影响效率。

多路平衡查找树（B-Tree）

上图为一个2-3树（每个节点存储2个关键字，有3路），多路平衡查找树也就是多叉的意思，从上图中可以看出，每个节点保存的关键字的个数和路数关系为：关键字个数 = 路数 – 1。

假设要从上图中查找id = X的数据，B TREE 搜索过程如下：

取出根磁盘块，加载40和60两个关键字。如果X等于40，则命中；如果X小于40走P1；如果40 < X < 60走P2；如果X = 60，则命中；如果X > 60走P3。根据以上规则命中后，接下来加载对应的数据， 数据区中存储的是具体的数据或者是指向数据的指针。

为什么说这种结构能够解决平衡二叉树存在的问题呢？
B Tree 能够很好的利用 *** 作系统和磁盘的交互特性， MySQL为了很好的利用磁盘的预读能力，将页大小设置为16K，即将一个节点（磁盘块）的大小设置为16K，一次IO将一个节点（16K）内容加载进内存。这里，假设关键字类型为 int，即4字节，若每个关键字对应的数据区也为4字节，不考虑子节点引用的情况下，则上图中的每个节点大约能够存储（16 * 1000）/ 8 = 2000个关键字，共2001个路数。对于二叉树，三层高度，最多可以保存7个关键字，而对于这种有2001路的B树，三层高度能够搜索的关键字个数远远的大于二叉树。

这里顺便说一下：在B Tree保证树的平衡的过程中，每次关键字的变化，都会导致结构发生很大的变化，这个过程是特别浪费时间的，所以创建索引一定要创建合适的索引，而不是把所有的字段都创建索引，创建冗余索引只会在对数据进行新增，删除，修改时增加性能消耗。

总结：很好的解决了平衡二叉树的缺点。但是相较于B+Tree还是各有优缺点的
平衡二叉树主要发生在磁盘IO读取，B-Tree主要是内存读取。这两种耗时差距很大。

B+Tree

如果上图中是用ID做的索引，如果是搜索X = 1的数据，搜索规则如下：

取出根磁盘块，加载1，28，66三个关键字。X <= 1 走P1，取出磁盘块，加载1，10，20三个关键字。X <= 1 走P1，取出磁盘块，加载1，8，9三个关键字。已经到达叶子节点，命中1，接下来加载对应的数据，图中数据区中存储的是具体的数据。

B+树的关键字全部存放在叶子节点中，非叶子节点用来做索引，而叶子节点中有一个指针指向一下个叶子节点。做这个优化的目的是为了提高区间访问的性能。而正是这个特性决定了B+树更适合用来存储外部数据。

MySQL为什么最终要去选择B+Tree？

B+Tree是B TREE的变种，B -TREE能解决的问题，B+TREE也能够解决（ 降低树的高度，增大节点存储数据量）

B+Tree扫库和扫表能力更强。如果我们要根据索引去进行数据表的扫描，对B TREE进行扫描，需要把整棵树遍历一遍，而B+TREE只需要遍历他的所有叶子节点即可（叶子节点之间有引用）。

B+TREE磁盘读写能力更强。他的根节点和支节点不保存数据区 ，所以根节点和支节点同样大小的情况下，保存的关键字要比B TREE要多。而叶子节点不保存子节点引用，能用于保存更多的关键字和数据。所以，B+TREE读写一次磁盘加载的关键字比B TREE更多。

B+Tree排序能力更强。上面的图中可以看出，B+Tree天然具有排序功能。

B+Tree查询性能稳定。B+Tree数据只保存在叶子节点，每次查询数据，查询IO次数一定是稳定的。当然这个每个人的理解都不同，因为在B TREE如果根节点命中直接返回，确实效率更高。

数据库索引采用B+树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的 *** 作（或者说效率太低）。

所以数据库索引采用了B+Tree作为了索引。

文献参考：
什么是B+树？.
深入理解MySQL索引之B+Tree.
一步步分析为什么B+树适合作为索引的结构.