一、概念

索引是存储引擎用于快速找到记录的一种数据结构。在Mysql中索引是在存储引擎层实现的，而不是在服务器层实现的，所以不同存储引擎的索引的工作方式是不一样的，计算多个存储引擎都支持同一种类型的索引，其底层实现方式也是不一样的。大部分存储引擎使用的都是B+树，即使名字叫B-tree索引。

二、关于B树的那些事

在分析不同的存储引擎B树的实现方式之前，有必要先了解B-tree和B+树的一些特点。

1、B-Tree

B树是一种多路平衡查找树(自平衡体现在存储和删除过程)

（1）特点（m阶B树）

• 根结点至少有两个子女。
• 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
• 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
• 所有的叶子结点都位于同一层。
• 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
• 每个节点都带有索引元素指向的数据记录

（2）例子（如存在一个3阶的B树）

（3）性能分析

由于磁盘的IO是由树的高度决定的，二叉树有高瘦的特点，而B树有矮胖的特点，也就是树的高度足够低，IO次数就会越少，就可以提升查找的性能了。

1、B+Tree

B+树是B-tree的升级版

（1）特点（m阶B+树）

• 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点
• 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
• 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
• 只有叶子节点带有索引元素指向的数据记录，中间节点只是索引作用，和数据没有关联。

（2）例子

（3）性能分析（相对于B树）

• 更少的IO次数。由于B+树非叶子节点不包含数据记录，因此相同大小的磁盘页可以容纳更多的节点元素，每个节点存储的记录个数比B树更多，则B+树比B树更加矮胖。因此查询IO次数更少。
• 更适于范围查询。由于B+树的叶子节点是一个有序链条，则在范围查询时，只需要首先找到下限，然后根据有序链条找到上限即可。
• 更稳定的查询效率。树的查询时间复杂度在1到树高之间(分别对应记录在根节点和叶节点)，而B+树的查询复杂度则稳定为树高，因为所有数据都在叶节点。

索引类别

1、B-Tree索引

B-Tree索引是B-Tree数据结构存储数据的，而从技术的角度出发是B+树结构。

存储引擎和索引的结构

（1）重要概念

• 聚集索引

聚集索引就是以表的主键去构造一个B+树结构，同时叶子节点存放整张表的行记录数据（聚集索引的叶子节点也称为数据页）。这就说明了索引组织表的数据本身就是索引的一部分，而每张表只能有一个聚集索引（因为数据页只能按照一个B+树进行排序）。

• 辅助索引（非聚集索引）

辅助索引是除了聚集索引外的索引。叶子节点并不包含了行记录的所有数据，只包含了索引列的数据。其外每个叶子节点中的索引还包含了一个书签，书签的作用是用来索引相应的行数据的聚集索引键（主键），那么查询辅助索引的时候就会有可能能出现二次查询的情况，例如一个阶为5的辅助索引树和5阶的聚集，那么查询需要5次IO遍历找到聚集索引的索引键，然后再到聚集索引树中经历5次IO遍历找到数据页。如果要避免二次查询的话，可以建立起需要查询列的联合索引（因为辅助索引树中有索引列的数据）。

（2）myisam的索引实现

MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。myisam的索引属于非聚集索引。

（3）innodb的索引实现

Innodb存储表是索引组织表，即表的数据本身就是B+树存储结构，表本身就是一个聚集索引。所以innodb表必须有主键，当没有显式指定时，mysql会检测表中是否存在非空唯一索引，有即把它作为主键，没有innodb就会自动创建一个6字节大小的指针作为主键。

2、hash索引

hash索引时基于hash表实现的，只有精确匹配到索引的所有列的查询索引才能生效。

（1）工作的原理

对于每一行数据，存储引擎会根据索引列计算出一个hash值，hash值是一个较小的值，并将hash值存放再一个哈希表中，此外hash表还存放了指向数据行的指针。

（2）索引的优缺点

• 因为hash索引表中只有hash值和行指针，所以无法避免读取行操作，但是有因为hash表只需要存储对应的hash值，索引索引结构非常紧凑，因此使用hash索引扫描行是非常快的。
• hash索引不支持部分索引列匹配查询。
• hash索引只支持等值查询，不支持范围查询。