我们在看一本书的时候，想找到相关的知识，先去看目录，然后定位到页码，然后找到对应的知识。mysql中的索引就是类似于目录的作用。

一、索引类型：

1.B-Tree索引

B-Tree通常意味着所有的值都是按照顺序存储的，并且每一个叶子页到根的距离相同。

B-TREE

每个节点都是一个二元数组: [key, data]，所有节点都可以存储数据。key为索引key,data为除key之外的数据。结构如下：

检索原理：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或未找到节点返回null指针。

缺点：1.插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。造成IO操作频繁。2.区间查找可能需要返回上层节点重复遍历，IO操作繁琐。

B+TREE

与B-Tree相比，B+Tree有以下不同点：非叶子节点不存储data，只存储索引key；只有叶子节点才存储data。是一个平衡的多叉树,而且同层级的节点间有指针相互链接。结构如下图：

Mysql中B+Tree：在经典B+Tree的基础上进行了优化，增加了顺序访问指针。在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。这样就提高了区间访问性能：如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率(无需返回上层父节点重复遍历查找减少IO操作)。

适用于B-TREE索引的查询类型：

等值匹配，范围匹配或者值前缀匹配。MySQL只能高效的使用索引的最左前缀列。因此，值前缀只支持最左前缀列。

因为是顺序存储，因此，很容易做排序操作。

   

2 hash索引

对于每一行数据，都会计算一个哈希码，哈希码是一个较小的值，不同键值的行计算出来的hash值也不一样。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。

因为索引自身只需要存储对应的哈希值，因此，哈希索引查询速度非常快。

哈希索引的限制：

• 哈希索引中只保存了哈希值和指针，不存储字段值，所以不能使用索引中的值来避免读取行。

• 因为不是按照顺序存储，无法用于排序。

• 不支持最左前缀列。例如在（A,B）上建立哈希索引，查询只有数据A，无法使用索引。

• 只支持等值比较查询，包括=,IN(),<=,>=，不支持范围查询，例如<,>

• 访问数据速度很快，除非有很多哈希冲突，则需要遍历链表中的所有指针。

• 建立索引时，如果选择了哈希冲突很多的列，索引维护操作的代价比较大。例如，想要删掉某行数据，哈希冲突比较多，需要花很多时间去找到链表中的位置，然后删掉引用。

注意：

在InnoDB引擎中有一个特殊的功能叫做：“自适应哈希索引”。当InnoDB注意到某些索引值被使用的非常频繁时，它会在内存中基于B-Tree索引之上，再创建一个哈希索引。

3.聚簇索引

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。具体的细节依赖于引擎的实现方式。主要说InnoDB引擎。

InnoDB的聚簇索引实际上在同一个结构中保存了B-Tree索引和数据行。

数据行和相邻的键值紧凑地存储在一起，因此，无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。

InnoDB通过主键聚集数据。如果没有定义主键，那么InnoDB会选择一个唯一的非空索引代替。如果没有这样的索引，InnoDB会隐式定义一个主键作为聚簇索引。

优点

• 可以把相关的数据保存到一起，例如实现电子邮箱，可以根据用户ID来聚集数据，这样只需要从磁盘读取一次，就可以获取用户的全部邮件。

• 数据访问快。

• 使用覆盖索引扫描的查询可以直接使用叶节点中的主键值。

缺点

• 如果数据全部放在内存中，访问顺序不重要，因此聚簇索引没有什么优势。

• 插入速度严重依赖于插入顺序。按照主键的顺序插入是加载数据到InnoDB表中速度最快的方式。如果不是按照主键顺序加载数据，加载完成之后最好使用OPTIMIZE TABLE命令重新组织下表。

• 更新聚簇索引列的代价很高。

• 基于聚簇索引的表在插入新行，或者主键被更新导致需要移动行时，可能面临页分裂问题。页分裂会导致表占用更多的磁盘空间。

• 二级索引（非聚簇索引）可能比想象的大，因为在二级索引的叶子节点上包含了引用行的主键列。

• 二级索引访问需要两次索引查找，而不是一次。

4.覆盖索引

msyql可以使用索引来直接获取列的数据，这样就不需要再读取数据行，如果一个索引包含或者说覆盖所有需要查询的字段的值，我们就称为覆盖索引。

优点

• 索引条目通常远小于数据行大小，如果只需要读取索引，那么mysql就会极大的减少数据访问量。对于I/O密集型的应用也有帮助，因为索引比数据更小。

• 索引时按照列值顺序存储的，所以对于I/O密集型的范围查询比随机从磁盘上读取每一行数据的I/O要少的多。对于MyISAM引擎，可以通过OPTIMIZE TABLE命令让索引完全顺序排列。

• 由于InnoDB的聚簇索引，覆盖索引对InnoDB表特别有用。InnoDb的二级索引在叶子节点中保存了行的主键值，所以如果二级主键能够覆盖查询，则可以避免对主键索引的二次查询。

覆盖索引必须要存储索引列的值，而哈希索引、空间索引和全文索引都不存储索引列的值，所以mysql只能使用B-Tree索引来做覆盖索引。不是所有的引擎都支持覆盖索引。