Mysql索引底层实现原理

一、定义

索引（index）是帮助Mysql高效获取数据的数据结构。
所以，索引的本质的数据结构。

二、设计原理

为什么要使用索引，很容易想到的目前就是加快查询效率。因此数据库的设计者会从查询算法的角度上开始优化。最基本的查询算法也就是顺序查找，这样的时间复杂度为O（n）的算法在数据量非常大的情况下显示是糟糕的。随着计算机科学技术的发展，例如二分查找（binary search）、二叉树查找（binary tree search）等。
所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

三、索引数据结构

（1）二叉查找树

二叉查找树，它是一棵树，选取其中的一个树枝为起点开两个叉，于是递归下来就是二叉树了（下图所示），而这棵树上的节点是已经排好序的，具体的排序规则如下：

• 如果左子树不为空，则左子树上所有节点的值均小于根节点的值
• 如果右子树不为空，则右字数上所有节点的值均大于它的根节点的值
• 它的左、右子树也分别为二叉排序数（递归定义）

例子：index_text表中数据

转化为二叉查找树：

从图中可以看出，二叉查找树在组织数据时，每次经过一个节点，都会减少一半的时间。查询复杂度为O（log₂n）但是极端情况下，会出现所有的节点都位于同一侧，这样查询效率就比较低了，查询复杂度为O（n）。
如：

再此基础上，因此需要对二叉树左右子树的高度进行平衡化处理，于是就有了平衡二叉树（Balenced Binary Tree）

（2）平衡二叉树

平衡二叉树，它有可能是一颗空树，或者具有以下性质的二叉查找树：

• 它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，
• 它的左子树和右子树都是一颗平衡二叉树。
  如图：
  
  从图中可以看出，不会出现一条支路特别长的情况，此时的查询效率有了很大的提高，不论查找、插入、删除操作在平均和最坏的情况下都是O（logn）。

(3) B树

B树，又称平衡多路查找树，也就是说每个节点最多可以开m个叉（m>=2），我们称之为m阶b树。
为了方便理解，下图为一棵5阶B树

一棵m阶B树具有以下性质：
（1）若根结点不是叶子结点，最少有两个孩子
（2）树中每个节点最多有m个孩子
（3）除根结点和叶子结点外，其它每个结点至少有有 ceil(m / 2)个孩子（ceil向上取整，5/2向上取整=3）；
（4）所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部结点或查询
失败的结点，实际上这些结点不存在，指向这些结点的指针都为 null)；
（5）非叶子节点，包含n个关键字信息：【n，P0，K1，P1，K2，P2，…，Kn，Pn】。具有以下性质
①：Ki(1…n)为关键字，且关键字顺序为1 K(i-1)<K(i-1)
②：Pi 为指向子树根节点的指针，且指针 P(i-1)指向子树种所有结点的关键字均小于 Ki，但都大于 K(i-1)
③：关键字n的个数，满足ceil(m / 2) -1 <= n <= m-1

B -Tree的特性：

（1）关键字集合分布在整棵树中
（2）任何一个关键字只存在于一个节点中
（3）每个阶段存储关键字和值，也就是Ki和Pi
（4）查询有可能在非叶节点结束
（5）所有叶节点具有相同的深度，等于树高
（6）树在插入删除新的数据记录会破坏B-Tree的性质，因为在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。

B树的查询过程和二叉排序树比较类似，从根节点依次比较每个结点，因为每个节点中的关键字和左右子树都是有序的，所以只要比较节点中的关键字，或者沿着指针就能很快地找到指定的关键字，如果查找失败，则会返回叶子节点，即空指针。

(4) B + 树（B树plus版）

B+树，是B树的优化版。和B树有以下不同点： 一个n阶B+树
（1）非叶子节点的关键字个数和子树指针相等。而B树为关键字个数n<=m-1
（2）非叶子节点不在存放数据，只当做叶子节点的索引，数据都放在叶子节点。
（3）非叶子节点的子树指针指向关键字值[KI,Ki+1)的子树
（4）所有叶子节点均有一个链指针执行下一个叶子节点。

所以，B+树更适合用来做索引存储
①：B+树磁盘读写代价更低。因为非叶子节点不存放数据，只存放索引信息，因此内部节点存储更小。一次性存放在内存中的关键字也就越多，相对B树来说IO读写次数变低了。

②：B+树的查询效率稳定。由于所有的数据都放在叶子节点，非叶子节点只当做索引。不存在在非叶子节点就查询到数据的可能性。必须有一条从根节点到叶子节点的路，所以效率更加稳定。时间复杂度为O（logn）

③：B+树更利于对数据库的扫描。提高区间访问的性能。因为添加了链节点，所以只需要遍历叶子节点就能查询到数据，比如范围查询大于10小于26的数据，在搜索20和26的时候就不用了从根节点再重新搜索。

(5) 红黑树

红黑树是一种特殊的二叉树，每个节点由红儿或者黑色表示。
具有以下特性：
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。[这里指到叶子节点的路径]

红黑树在添加和删除节点时，会伴随着节点移动、左旋、右旋。
具体流程，可参考：https://www.cnblogs.com/woniu4/p/8086707.html

四、为什么使用B/B+树作为Mysql的索引数据结构

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数

先从B-Tree分析，根据B-Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：

每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。（h表示树的高度 & 出度d表示的是树的度，即树中各个节点的度的最大值）

综上所述，用B-Tree作为索引结构效率是非常高的。

五 、哈希索引以及与B/B+树的区别

哈希索引，很久hash()的运算，只需要一次定位，就能找到所需查询数据的头。不像B+树需要从根节点一直查找到叶子节点。B/B+树的形式可能会造成多次的I/O访问。所以哈希索引的方式的查询效率理论上要高于B树。

哈希索引与B/B+树的区别

B-tree 索引
索引是按照顺序存储的，所以，如果按照 B-tree 索引，可以直接返回，带顺序的数据，但这个数据只是该索引列含有的信息。因此是顺序 I/O
适用于：
①精确匹配
②范围匹配
③最左匹配

Hash 索引
索引列值的哈希值+数据行指针：因此找到后还需要根据指针去找数据，造成随机I/O
适合：
精确匹配
不适合：
模糊匹配
范围匹配
不能排序

1、hash 索引仅满足 “=”、“IN” 和 “<=>” 查询，不能使用范围查询因为 hash 索引比较的是经常 hash 运算之后的hash值，因此只能进行等值的过滤，不能基于范围的查找，因为经过hash算法处理后的 hash 值的大小关系，并不能保证与处理前的 hash 大小关系对应。
2、hash 索引无法被用来进行数据的排序操作由于 hash 索引中存放的都是经过hash 计算之后的值，而 hash 值的大小关系不一定与 hash 计算之前的值一样，所以数据库无法利用 hash 索引中的值进行排序操作。
3、对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。
4、Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比 B-Tree 索引高。对于选择性比较低的索引键，如果创建 Hash 索引，那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。
总结：哈希适用在小范围的精确查找，在列数据很大，又不需要排序，不需要模糊查询，范围查询时有用