索引的结构简单讲解

索引的底层结构是一颗B+树，并且在叶节点之间做了链表优化。

B+树和普通的二叉平衡树区别：B+树是一颗n叉树，意味着查询的时候查询深度更小，因为节点都是储存在磁盘中的，这样的好处就是减少访问数据块次数，进而减少IO时间，提高查找效率。

B+树和哈希表的区别：哈希表是k-v形式储存的，但是不适合进行范围查找，不支持排序，不支持模糊查询以及多列索引的最左前缀匹配。此外，哈希表会存在哈希冲突，性能不稳定。

B+树和数组的区别：数组也可以进行范围查找，但是对数组的数据插入与删除可能需要把整个数组进行移动，效率极低，MySQL中的B+数叶节点有链表结构，可以进行范围查找，同时也具有AVL树（平衡二叉树）的特性。

索引分类

1. 普通索引：对索引字段无任何要求。
2. 唯一索引：索引字段必须唯一，允许空值。
3. 主键索引：索引字段必须唯一，不允许空值。
4. 复合索引：多列值组成一个索引，专门用于组合搜索。后面会说明复合索引的注意事项。
5. 全文索引（仅可以适用于MyISAM引擎的数据表）：将文本中的word提取并创建索引。

MyISAM索引

索引特点

MyISAM的索引不是聚簇索引，索引叶节点的内容记录的是创建索引保存的有关列的内容和指向该行的指针。可能会产生回表查询的情况。

InnoDB索引

索引特点

由于MySQL后面的版本默认储存引擎是InnoDB，所以我们当前索引的讨论基本都是基于InnoDB的。

InnoDB的索引是聚簇索引。总结来说，每张表必须有主键（没主键InnoDB会隐式创建），每一个InnoDB表都包含一颗以主键为索引的B+树，每个叶子节点直接储存该行的相关数据（所以也将聚集索引的叶子节点称为数据页），也就是说，索引组织表中数据也是索引的一部分。

对于非主键索引，索引的叶子节点储存的是主键值。也就是说，当我们创建一个非主键索引的时候，还需要对于找到的这个主键值进行回表查询（在主键索引中查询）。因此，我们在应用中应该尽量使用主键查询。

怎样创建主键索引？

1. 尽量使用自增索引：
   (1)因为B+树的特点，在两个值之间插入一个新的值可能会造成页分裂，从而造成性能和储存效率降低。使用自增索引可以一定程度减少页分裂。
   (2)根据InnoDB索引特点，显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。如果需要创建非主键索引的话，该索引的叶节点应该足够小，便于节省储存空间。

2. 如果有k-v储存的场景，可以使用k作为主键索引：
   因为对于非主键索引，索引的叶子节点储存的是主键值，我们还要根据主键值进行回表查询。而使用k作为主键可以避免回表查询，提高查找效率。

覆盖索引

对于InnoDB非主键索引来说，如果是单一索引的话，索引叶节点的值是主键值。当我们的查询语句还存在除主键值之外的查询的话，就要进行回表查询；复合索引也是如此，但如果查找的是联合索引的最左原则字段，那就不用回表。因此，我们要合理创建索引，以及合理创建查询语句。

最左前缀原则

和B+树的结构有关。当创建联合索引的时候，B+树会将第一个字段排序，在第一个字段排序的基础上，再将第二个字段排序。这样会造成第二个字段单独字段来看无序的情况。当我们只查询第二个字段的时候，由于索引对第二个字段的排序是无序的，所以索引便失效了。最左前缀原则对文本的模糊查找同样有效。

索引下推

早期的MySQL对于联合索引有个蛋疼的机制，例如我们有个(age, name)的复合索引，现在有条查找语句：select * from tb where age = 20 and name = 'Left_Zzzz';

对于这条查询，首先会查找索引中age = 20符合条件的记录，再通过回表查询查找该表中name是否为 'Left_Zzzz'。

MySQL 5.6后引入了索引下推机制，即先在所以中对已存在的字段进行判断，直接在索引中过滤掉不符合条件的记录，再回表查询。这样的好处是减少一定的回表次数，提高查询效率。

参考资料

1.聚簇索引和非聚簇索引(通俗易懂 言简意赅)
2.极客时间——MySQL实战45讲