MySQL索引

一.索引的概述

1.为什么要使用索引？

在我们对海量的数据进行查询时，由于数据量十分庞大，会导致查询的速度缓慢，那么为了提高我们的查询速度，可以在某些字段上加上索引，那么根据这些加了索引的字段查询数据，速度就会更快。

2.索引是什么？

2.索引存放的位置

3.索引的分类

主键索引：主键自带索引效果，也就是说通过主键来查询数据，性能是非常好的。
普通索引：为普通列创建的索引。
唯一索引：为某一列创建索引（列中的数据是唯一的）。
组合索引：为多个字段创建的索引，需要遵守最左前缀法则才能命中索引。注意：一般不建议组合索引超过五个字段。
全文索引：进行查询的时候，数据源可能来自于不同的字段不同的表，比如说百度某个词条，查处的结果词条可能在标题中，也可能在内容里，说明数据源来自不同的字段或者不同的表。在实际生产环境中，一般不会使用MySQL提供的MyISAM存储引擎的全文索引功能来实现全文查找。而是会使用第三方的搜索引擎中间件比如ElasticSearch（多），Solr。

3.索引为什么快？

如上图所示，由于MySQL数据存储在磁盘中，当我们查询数据时，会分批量对磁盘进行多次io来查询数据，当数据量多的时候io次数变多，开销会非常大，从而查询效率非常缓慢。

当我们为某个字段创建索引后，根据此字段去查询时会先通过字段值拿到对应数据在磁盘上的物理地址（MyISAM），从而直接拿到对应的数据，大大减少了磁盘io的次数，提高了查询效率，至于为什么查询索引会比直接查询数据要快，就要提到索引的数据结构了(B+树)，下面会讲到。

使用索引要注意什么？

二.索引使用的数据结构

数据存储的结构被称为数据结构，常用的数据结构有线性表，栈，堆，树等。
下面我们简单回顾一下各个数据结构的特点：

1.线性表：线性表主要有两种数据结构支撑：线性顺序表和线性链式表。

线性顺序表：相邻数据的逻辑关系和数据的物理地址相关。
线性链式表：相邻数据的逻辑关系和数据的物理地址不相关。
- 单项链表：能够通过当前节点找到下一个节点，以此来维护表之间的逻辑关系。
- 双向链表：能够通过当前节点找到上一个节点或者下一个节点，双向都可以找。
  顺序表和链式表的区别（以数组和链表为例）：
数组：因为数组是在内存上连续的一片区域，所以可以通过下标快速定位到元素，随机查询的效率很高，但是由于增删时，后于的每一个元素都要后移或者前移，导致增删的效率比较低。（查询的时间复杂度：O(1)）
链表：由于链表在内存上是不连续的，所以想要查询元素，无法直接拿到内存地址，必须要从头开始遍历链表，所以链表的查询效率比较低，但是由于增删时只需要修改节点的指针指向，所以增删的效率比较高。（查询的时间复杂度：O(n)）

2.栈，队列，串，广义表

栈：先进后出，有顺序栈和链式栈
队列：先进先出，有顺序队列和链式队列
串：String定长串，StringBuffer/StringBuilder动态串
广义表：更加灵活的多维数组，可以在不同的元素中创建不同维度的数组。

3.树（重要）

1）多叉树：非二叉树

2）二叉树：一个节点最多只能有两个子节点

3）二叉查找树：二叉查找树的根节点是比所有左子树的节点要大的，比所有右子树的节点要小。这样的规律同样满足于它的子树。二叉查找树的查询性能性能和树的高读有关。

4）平衡二叉树：由于二叉查找树的根节点的左子树和右子树的节点相差过大时，会导致高度过高的子树查询效率降低，那么为了能够更好的维护二叉查找树的节点，我们引入了平衡二叉树。

平衡二叉树又称为AVL树。平衡二叉树遵循以下两个特点：

每棵子树中的左子树和右子树的深度差不能超过1
二叉树中每棵子树都要求是平衡二叉树

平衡因子︰每个结点都有其各自的平衡因子，表示的就是其左子树深度同右子树深度的差。平衡二叉树中各结点平衡因子的取值只可能是:0、1和-1。

如图所示，其中(a)的两棵二叉树中由于各个结点的平衡因子数的绝对值都不超过1，所以（a)中两棵二叉树都是平衡二叉树;而(b)的两棵二叉树中有结点的平衡因子数的绝对值超过1，所以都不是平衡二叉树。

二叉排序树转化为平衡二叉树

如果平衡二叉树不满足以上两个特点，则需要通过自旋来满足上述两个特点，自旋分为三种：左旋、右旋、双向旋转（先左后右，先右后左）。具体可以看这篇：平衡二叉树如何通过自旋保持平衡

5）红黑树（平衡二叉树的一种体现）

红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

性质1.结点是红色或黑色。
性质2.根结点是黑色。
性质3.不可能有连在一起的红色节点。
性质4.每个红色结点的两个子结点都是黑色。叶子结点都是黑色（nil-黑色的空节点)
平衡二叉树为了维护树的平衡，在一旦不满足平衡的情况就要进行自旋，但是自旋会造成一定的系统开销。因此红黑树在自旋造成的系统开销和减少查询次数之间做了权衡。因此红黑树有时候并不是一颗平衡二叉树。

这些约束强制了红黑树的关键性质:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

红黑树已经是在查询性能上得到了优化，但索引依然没有使用红黑树作为数据结构来存储数据，因为红黑树在每一层上存放的数据内容是有限的，导致数据量一大，树的深度就变得非常大，于是查询性能非常差。因此索引没有使用红黑树。

6）B树

B树允许一个结点存放多个数据。这样可以使更小的树的深度来存放更多的数据。但是，B树的一个结点中到底能存放多少个数据，决定了树的深度。

通过数值计算，B树的一个结点最多只能存放15个数据，因此B树依然不能满足海量数据的查询性能优化。

7）B+树

B+树的特点:
- 非叶子结点冗余了叶子结点中的键。
- 叶子结点是从小到大、从左到右排列的。
- 叶子结点之间提供了指针，提高了区间访问的性能。
- 只有叶子节点存放数据，非叶子节点是不存放数据的，只存放键。

B+树的非叶子节点不存储索引键的值，只在叶子节点上存储索引的键值，相同的节点数量相较于其他的结构能够存储的键更多，树的深度更浅，通过计算可以发现，三层结构就可以存储两千多万条数据，相比于其他的数据结构能够支持海量的数据，同时在相邻的叶子节点之间同过指针进行指向，那么查询连续查询两个相邻的数据时，第二次查询不会再从根节点遍历，而是根据第一次查询到的叶子节点持有的指针快速找到相邻的节点，大大提高了查询效率。同时叶子节点之间的指针可以支持范围查找，通过找到边界点的叶子节点，然后再根据相邻叶子节点的指针去直接遍历整个区域，不需要每次都从根节点遍历，大大提高了范围查找的速度。

7）哈希表

使用哈希表来存取数据性能是最快的，但是由于哈希表是根据哈希值来确定存储的位置，那么逻辑上相邻的数据在物理位置上不相邻，所以不支持范围查找（区间访问），比如找某个范围内的值，B+树结构的索引可以先找到边界值再根据叶子节点之间的指针快速访问，但是哈希表结构就只能每次都计算哈希值来查找数据。同时哈希表结构会产生哈希冲突，生成链之后会导致查询效率变慢。所以这也是为什么MySQL存在hash索引和b+树索引但是我们通常都使用b+树索引。