索引

索引介绍

若索引太多，应用程序的性能可能会受到影响。而索引太少，对查询性能又会产生影响。要找到一个合适的平衡点，这对应用程序的性能至关重要。

InnoDB支持的索引：B+树索引，全文索引以及哈希索引。

B+树索引并不能找到一个给定键值的具体行。B+树索引能找到的只是被查找数据行所在的页。然后数据库通过把页读入到内存，再在内存中通过PageDirectory（页目录：存储用户记录的相对位置，对记录起到索引作用）进行二叉查找，最后得到要查找的数据。

B+树及B+树索引

由B树和索引顺序访问方法演化过来。

不管怎么变化，B+树总是会保持平衡。但是为了保持平衡对于新插入的键值可能需要做大量的拆分页（split）操作。因为B+树结构主要用于磁盘，页的拆分意味着磁盘的操作，所以应该在可能的情况下尽量减少页的拆分操作。因此，B+树同样提供了类似于平衡二叉树的旋转（Rotation）功能。

在数据库中，B+树的高度一般都在2～4层，这也就是说查找某一键值的行记录时最多只需要2到4次IO，这倒不错。因为当前一般的机械磁盘每秒至少可以做100次IO，2～4次的IO意味着查询时间只需0.02～0.04秒。

InnoDB 里的 B+ 树中的每个节点都是一个数据页。

B树与B+树的区别是什么？

B+树是为磁盘存储专门设计的一M阶多路平衡查找树(阶数可以理解为每个节点最多的孩子节点的个数，二叉树就是2阶)，所有记录节点都是按照从小到大顺序存放在最后一层的叶子节点上，由各叶子节点的指针相连接。可以认为一个叶子节点就是一个内存页(默认情况下，一个内存页大小为16K)，每个内存页里面存储多个数据行，内存页直接通过指针连接，形成一个双向链表，所以叶子节点在逻辑上是连续的，在物理上不是连续存储的，就是每个叶子节点可以存储在不同地址上，通过指针相互连接。每个非叶子节点(也就是索引节点)也是一个内存页，里面存储了很多索引节点的值，但是B+树索引节点只存索引值，不存数据行的数据，这样可以让每个索引内存页存储更多的索引值，这样可以使得B+树的层数更少（这也是B+树比B树更优的地方）。B+树在数据库的中实现一般是只有2到4层，机械磁盘一般1秒可以进行100次IO，也意味着每次在B+树中的查询操作可以在20ms到40ms之间完成。

1. B树每个节点会保存关键字，索引和数据。而B+树只有叶子节点保存数据，其他节点只保存关键字和索引。所以相同的内存空间可以容纳更多的索引节点。
2. B+树的所有数据都存在叶子节点上，所以查询会更加稳定，而且相邻的叶子节点都是连接在一起的，更加适合区间查找和搜索。

B+树与二叉树区别是什么？为什么不用红黑树？

红黑树是一个平衡的二叉查找树。有以下几个性质：

1. 根节点和叶子节点都是黑色的（这里的叶子节点指的是普通的节点增加的一个黑色的空节点）。
2. 红色节点的子节点必须是黑色的，也就是不能有两个红色节点连续。
3. 黑色的节点可以连续，但是从根节点到叶子节点的所有路径包含的黑色节点的个数是一致的。(所以根节点到叶子节点的最长路径<=最短路径的两倍)

红黑树是二叉查找树（也就是每个节点的左子树<当前节点的值，右子树所有节点>=当前节点值），但不是严格意义上的平衡二叉树，因为平衡二叉树要求任何节点的左右子树高度差是<=1，红黑树根节点到叶子节点的最长路径会<=最短路径的两倍,所有他是大致意义上的平衡树。

相比于AV树（也就是自平衡的二叉查找树，左右子树高度差不超过1），红黑树插入，删除效率更高。因为不需要保证绝对的平衡，任何不平衡需要的旋转次数不超过3次，即便在最坏的情况下，红黑树能够以O(log(N))的时间复杂度进行搜索、插入、删除操作。

与红黑树的比较

红黑树等平衡树也可以用来实现索引，但是文件系统及数据库系统普遍采用 B+ Tree 作为索引结构，主要有以下两个原因：

（一）更少的查找次数

平衡树查找操作的时间复杂度和树高 h 相关，O(h)=O(logdN)，其中 d 为每个节点的出度。

红黑树的出度为 2，而 B+ Tree 的出度一般都非常大，所以红黑树的树高 h 很明显比 B+ Tree 大非常多，查找的次数也就更多。

（二）利用磁盘预读特性

为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是每次都会预读。而B+数中存储的叶子节点在内存中是相邻的，这样可以读取会快一些。

（三）存储更多的索引节点

B+树跟B树的区别就是B+是叶子节点存储数据，非叶子节点(也就是索引节点)只存储索引项，B树是所有节点都存储数据，而每个节点都是磁盘的一个内存页，内存页大小是固定，B+树的每个索引节点可以容纳的索引值更多，与B树相比，B+树的层数更少。

索引分类

聚集索引

InnoDB存储引擎表是索引组织表，即表中数据按照主键顺序存放。而聚集索引（clustered index）就是按照每张表的主键构造一棵B+树，同时**叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页****。

由于实际的数据页只能按照一棵B+树进行排序，因此每张表只能拥有一个聚集索引。

在多数情况下，查询优化器倾向于采用聚集索引。因为聚集索引能够在B+树索引的叶子节点上直接找到数据。此外，由于定义了数据的逻辑顺序，聚集索引能够特别快地访问针对范围值的查询。查询优化器能够快速发现某一段范围的数据页需要扫描。

数据页上存放的是完整的每行的记录，而在非数据页的索引页中，存放的仅仅是键值及指向数据页的偏移量，而不是一个完整的行记录。

InnoDB存储引擎使用聚集索引，实际的数据行和相关键值保存在一块。因而，在InnoDB中要使用索引访问数据始终需要两次查找，而不是一次。因为索引叶子节点中存储的不是行的物理位置，而是主键的值。即：二次索引-->主键-->数据的叶子-->通过数据叶字节点中的page directory找到数据行。

辅助索引

对于辅助索引（Secondary Index，也称非聚集索引），叶子节点并不包含行记录的全部数据。**叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签（bookmark）。**该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。由于InnoDB存储引擎表是索引组织表，因此InnoDB存储引擎的辅助索引的书签就是相应行数据的聚集索引键。

辅助索引的存在并不影响数据在聚集索引中的组织，因此每张表上可以有多个辅助索引。

当通过辅助索引来寻找数据时，InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。举例来说，如果在一棵高度为3的辅助索引树中查找数据，那需要对这棵辅助索引树遍历3次找到指定主键，如果聚集索引树的高度同样为3，那么还需要对聚集索引树进行3次查找，最终找到一个完整的行数据所在的页，因此一共需要6次逻辑IO访问以得到最终的一个数据页。

回表与索引覆盖

一张表只能有一个聚簇索引，那为了实现非主键字段的快速搜索，就引出了二级索引（非聚簇索引/辅助索引），它也是利用了 B+ 树的数据结构，但是二级索引的叶子节点存放的是主键值，不是实际数据。

因此，如果某个查询语句使用了二级索引，但是查询的数据不是主键值，这时在二级索引找到主键值后，需要去聚簇索引中获得数据行，这个过程就叫作**「回表」****，也就是说要查两个 B+ 树才能查到数据。**

不过，当查询的数据是主键值时，因为只在二级索引就能查询到，不用再去聚簇索引查，这个过程就叫作**「索引覆盖」，也就是只需要查一个 B+ 树就能找到数据。**

Cardinality值

并不是在所有的查询条件中出现的列都需要添加索引。对于什么时候添加B+树索引，一般的经验是，在访问表中很少一部分时使用B+树索引才有意义。对于性别字段、地区字段、类型字段，它们可取值的范围很小，称为低选择性。

按性别进行查询时，可取值的范围一般只有'M'、'F'。因此上述SQL语句得到的结果可能是该表50%的数据（假设男女比例1∶1），这时添加B+树索引是完全没有必要的。相反，如果某个字段的取值范围很广，几乎没有重复，即属于高选择性，则此时使用B+树索引是最适合的。例如，对于姓名字段，基本上在一个应用中不允许重名的出现。

怎样查看索引是否是高选择性的呢？可以通过==SHOW INDEX==结果中的列Cardinality来观察。Cardinality值非常关键，表示索引中不重复记录数量的预估值。同时需要注意的是，Cardinality是一个预估值，而不是一个准确值，基本上用户也不可能得到一个准确的值。在实际应用中，Cardinality/n_rows_in_table应尽可能地接近1。如果非常小，那么用户需要考虑是否还有必要创建这个索引。

数据库是怎样来统计Cardinality信息的呢？

1. 此外需要考虑到的是，在生产环境中，索引的更新操作可能是非常频繁的。如果每次索引在发生操作时就对其进行Cardinality的统计，那么将会给数据库带来很大的负担。另外需要考虑的是，如果一张表的数据非常大，如一张表有50G的数据，那么统计一次Cardinality信息所需要的时间可能非常长。这在生产环境下，也是不能接受的。因此，数据库对于Cardinality的统计都是通过采样（Sample）的方法来完成的。

2. 在InnoDB存储引擎中，Cardinality值是通过对8个叶子节点预估而得的，不是一个实际精确的值。再者，每次对Cardinality值的统计，都是通过随机取8个叶子节点得到的，这同时又暗示了另一个Cardinality现象，即每次得到的Cardinality值可能是不同的。

联合索引

从本质上来说，联合索引也是一棵B+树，不同的是联合索引的键值的数量不是1，而是大于等于2。

联合索引的第二个好处是已经对第二个键值进行了排序处理。例如，在很多情况下应用程序都需要查询某个用户的购物情况，并按照时间进行排序，最后取出最近三次的购买记录，这时使用联合索引可以避免多一次的排序操作，因为索引本身在叶子节点已经排序了。

覆盖索引

InnoDB存储引擎支持覆盖索引（covering index，或称索引覆盖），即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录**。

使用覆盖索引的一个好处是辅助索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的IO操作。

对于InnoDB存储引擎的辅助索引而言，由于其包含了主键信息，因此其叶子节点存放的数据为（primary key1，primary key2，…，key1，key2，…）。

此外，在通常情况下，诸如（a，b）的联合索引，一般是不可以选择列b中所谓的查询条件。但是如果是统计操作（诸如count，sum，max等操作），并且是覆盖索引的，则优化器会进行选择。

B树与B+树的区别

1. B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。

2. B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。

   1. 由于B+树的叶子节点的数据都是使用链表连接起来的，而且他们在磁盘里是顺序存储的，所以当读到某个值的时候，磁盘预读原理就会提前把这些数据都读进内存，使得范围查询和排序都很快

3. B+树更适合外部存储。由于内节点无 data 域，每个节点能索引的范围更大更精确。

   1. 由于B树的节点都存了key和data，而B+树只有叶子节点存data，非叶子节点都只是索引值，没有实际的数据，这就时B+树在一次IO里面，能读出的索引值更多。从而减少查询时候需要的IO次数！

MySQL为什么使用B-Tree（B+Tree）

红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构。

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

全文索引

全文检索通常使用倒排索引（inverted index）来实现。倒排索引同B+树索引一样，也是一种索引结构。它在辅助表（auxiliary table）中存储了单词与单词自身在一个或多个文档中所在位置之间的映射。

full invertedindex，其表现形式为{单词，(单词所在文档的ID，在具体文档中的位置)}

InnoDB存储引擎从1.2.x版本开始支持全文检索的技术，其采用full inverted index的方式。在InnoDB存储引擎中，将(DocumentId，Position)视为一个“ilist”。因此在全文检索的表中，有两个列，一个是word字段，另一个是ilist字段，并且在word字段上有设有索引。此外，由于InnoDB存储引擎在ilist字段中存放了Position信息，故可以进行Proximity Search，而MyISAM存储引擎不支持该特性。

MySQL数据库通过MATCH()…AGAINST()语法支持全文检索的查询，MATCH指定了需要被查询的列，AGAINST指定了使用何种方法去进行查询。

当前InnoDB存储引擎的全文检索还存在以下的限制：

• 每张表只能有一个全文检索的索引。
• 由多列组合而成的全文检索的索引列必须使用相同的字符集与排序规则。
• 不支持没有单词界定符（delimiter）的语言，如中文、日语、韩语等。

索引优化

此处为语雀内容卡片，点击链接查看：https://www.yuque.com/hanchanmingqi-zjjw3/kb/aoy36m (opens new window)