之前的一篇《MySQL索引底层数据结构及原理深入分析》很受读者欢迎，成功地帮大家揭开了索引的神秘面纱，有读者留言说分不清各种索引的概念，希望能讲一下。确实，数据库中索引种类很多，如聚集索引、复合索引、二级索引、唯一索引...你是不是也搞得不是太清楚，那么今天就带大家一起看下索引的分类及相关概念。
索引分类
- 从数据结构角度可分为B 树索引、哈希索引、以及全文（FULLTEXT）索引（现在MyISAM和InnoDB引擎都支持）和R-Tree索引（用于对GIS数据类型创建SPATIAL索引）；
- 从物理存储角度可分为聚集索引（clustered index）、非聚集索引（non-clustered index）；
- 从逻辑角度可分为主键索引、普通索引（辅助索引、二级索引等等）；
- 从列的个数角度可以分为单列索引、多列索引（或者叫复合索引、联合索引）；
- 从唯一性角度可以分为唯一索引、非唯一索引。
一个索引从不同的角度看可以属于不同的索引。例如一个索引可以是多列索引也可以是唯一索引，也可以是辅助索引。
从数据结构角度
B 树索引结构
MySQL采用B Tree作为索引和数据的存储结构，如下图1所示，在这棵树中，非叶子节点只存储索引，而且索引是冗余的，非叶子节点中两个索引中间存储的是下一个数据页的地址。在InnoDB存储引擎中，默认使用主键建立索引树，其叶子节点中每个数据项包括主键和主键所在行的所有列数据或数据地址。
注意：MySQL中一个数据页大小是16K，每页存的数据个数有限，和列数及数据类型有关。
图1
具体分析过程可以参考之前的文章，MySQL索引底层原理及数据结构深入分析，链接地址：https://mp.weixin.qq.com/s/1C1QvOvKs_yAf81GiqGoNA
HASH索引
hash索引的查询效率要高于B Tree，但是99%的情况都是用B Tree，极少情况下用hash。hash结构索引的原理：对索引字段做hash计算，把运算的结果值和这一行数据所在磁盘地址做映射。
那么，使用HASH索引时，对于数据查找，HASH索引做一次hash运算就可以在hash映射表里快速找到这一行的磁盘文件地址。一次hash就可以快速定位到索引所在行的磁盘文件地址！
即使表有一亿个数据，按这种算法，那也就可能经历一次hash运算就可以快速找到某页任意一行数据元素的所在的磁盘文件地址，时间复杂度是O(1)，那比B Tree快得多啊！那为啥99%的情况下都是用B Tree而不用hash呢？
原因是如果使用范围查找，hash就没有用武之地了，在业务中范围查找是很常用的，但HASH索引不支持，所以基本就不怎么用hash这种数据结构。hash索引适用于等值查询的场景。
全文索引
MySQL 5.6 以前的版本，只有 MyISAM 存储引擎支持全文索引。从InnoDB 1.2.x版本开始，InnoDB存储引擎开始支持全文检索，对应的MySQL版本是5.6.x系列。
但不管什么引擎，只有字段的数据类型为 char、varchar、text 及其系列才可以建全文索引。
不过MySQL从设计之初就是关系型数据库，存储引擎虽然支持全文检索，整体架构上对全文检索支持并不是太好而且限制很多，比如：1.每张表只能有一个全文检索的索引，2.不支持没有单词界定符( delimiter）的语言，如中文、日语、韩语等的限制。
所以如果有大批量或者专门的全文检索需求，还是应该选择专业的全文检索引擎，专业的人干专业的事，毕竟Elastic靠着全文检索起家，然后产品化、公司化并推出商业版本的解决方案然后融资上市，现在的市值已达100亿美元（2021/12/06 -纽约证券交易所中的市值101.5亿美元）。
从逻辑角度
主键索引
MySQL默认使用主键建立索引。
将索引和数据（或数据地址）一块维护在一棵B Tree上，树的非叶子节点是主键，叶子节点是主键及主键对应的行记录（或数据地址）。
MySQL默认使用主键建立索引树，如果没有主键会看是否有可以唯一标识一个行记录的列，有则使用该列建立索引树，没有的话MySQL内部会创建一个隐含的列类似于rowid来建立索引树。
非主键索引
除了主键外的其他字段建立的索引，也叫普通索引，辅助索引、二级索引。
相较于主键索引，InnoDB存储引擎的辅助索引会建立另外的一棵B Tree，这棵索引树的叶子节点的索引位（可以理解为key）就是我们选的索引列，叶子节点的数据位（可以理解为value）为主键值，而不是像主键索引那样索引位是主键，数据位是那一行的完整数据（除主键外）。这么做的目的一是为了节省空间，二是为了高效和保证数据的一致性。
从物理存储角度
聚集索引（聚簇索引）
从物理存储角度划分，聚集索引把索引和行数据维护在一起，例如Innodb的主键索引。
聚集索引的叶子节点就是索引列 数据值，整个磁盘数据页都是叶子节点。换句话说，数据页上存放的是完整的每行记录。因此聚集索引的一个优点就是：通过过聚集索引能获取完整的整行数据。另一个优点是：对于主键的排序查找和范围查找速度非常快。
非聚集索引（非聚簇索引）
这种索引相比较于聚集索引来说，是把索引和行数据分开维护，例如Innodb的非主键索引(辅助索引)。非聚集索引也会单独维护一个索引树（B Tree结构），只不过它的叶子节点存的是索引列和主键值（InnoDB的辅助索引）或数据地址（MyISAM的索引）。
从列的个数角度
单列索引
顾名思义，被索引的列只有一列，例如create index idx_a on table_name(a)。
联合索引(多列索引/复合索引)
也叫多列索引、复合索引，索引可以有多个列一起来建立，如create index idx_a_b on table_name(a,b)，idx_a_b是索引名称，索引列是a和b两列。注意列顺序不同建立的索引不同。
此时索引树的组织方式大致如下图，先按索引的第一列排序，再按索引的第二列排序。一个索引只会建立一个索引树，即使是多列。
从唯一性角度
唯一索引
使用若干列建立唯一索引，create unique index u_idx_a_b on table_name(a,b)，u_idx_a_b是索引名称，则每一个行数据的这些列不能完全重复。当a、b相同时，第二条数据将不能插入或更新成功。当表中列有重复数据时，无法创建唯一索引。
例如有如下数据：
当执行INSERT INTO table_name(id, a, b) VALUES (3, '01', '0');会报错：Duplicate entry '01-0' for key 'u_idx_a_b'。
索引相关概念辨析
密集索引和稀疏索引
面试中还会被问到什么是密集索引和稀疏索引。
密集索引：叶子节点保存的不只是键值，还保存了位于同一行记录里的其他列的信息，由于密集索引决定了表的物理排列顺序，一个表只有一个物理排列顺序，所以一个表只能创建一个密集索引。
稀疏索引：叶子节点仅保存了键位信息以及该行数据的地址，有的稀疏索引只保存了键位信息及其主键。
mysiam存储引擎，不管是主键索引，唯一键索引还是普通索引都是稀疏索引，innodb存储引擎：有且只有一个密集索引。
所以，密集索引就是innodb存储引擎里的聚簇索引，稀疏索引就是innodb存储引擎里的普通二级索引。
回表
前面我们提到聚集索引是把索引和数据一块维护在B Tree中，当然我们也可以建立辅助索引（非聚集索引），而辅助索引的存在并不影响数据在聚集索引中的组织，且每张表上可以有多个辅助索引。
当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引并通过叶子节点获得指向主键索引的主键，然后再通过主键索引（聚集索引）来找到一个完整的行记录。这个过程被称为回表。也就是根据辅助索引的值查询一条完整的记录需要使用到两棵B 树，即，一次辅助索引，一次聚集索引。
为什么我们还需要一次回表操作呢?直接把完整的记录放到辅助索引的叶子节点不就好了么？刚才提到过，目的是节省空间和数据一致性。如果把完整的记录放到叶子节点是可以不用回表，但是太占地方了，相当于每建立一棵B 树都需要把所有的记录再都拷贝一遍，这就有点太浪费存储空间了。而且每次对数据的变化要在所有包含数据的索引中全部都修改一次，为了保证数据的一致性，避免不了要做很多事务性操作，性能将非常低下。
所以，使用辅助索引查找数据，且查询的列不在索引树中时，就需要回表了。很明显，回表的记录越少，性能提升就越高，需要回表的记录越多，使用辅助索引的性能就越低，甚至让某些查询宁愿使用全表扫描也不使用辅助索引。
那什么时候采用全表扫描的方式，什么时候使用采用辅助索引 回表的方式去执行查询呢？这个就是查询优化器做的工作，查询优化器会事先对表中的记录计算一些统计数据，然后再利用这些统计数据根据查询的条件来计算一下需要回表的记录数，需要回表的记录数越多，就越倾向于使用全表扫描，反之倾向于使用辅助索引 回表的方式。具体怎么算的，不是今天的主题以后再说。
覆盖索引/索引覆盖
是一种索引优化方式而不是索引类型，是指查询的列只需要通过索引树就能查到，不需要二次回表。
InnoDB存储引擎支持覆盖索引(covering index，或称索引覆盖)，即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。使用覆盖索引的一个好处是辅助索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的IO操作。所以记住，覆盖索引可以视为索引优化的一种方式，而并不是索引类型的一种。 除了覆盖索引这个概念外，在索引优化的范围内，还有前缀索引等一系列概念。
还拿这个图举例，a和b两列创建了联合索引，当查询select b from table where a = '02'就采用了覆盖索引
前缀索引
有时候需要索引很长的字符列，这会让索引变得大且慢。可以索引开始的部分字符，这样可以大大节约索引空间，从而提高索引效率。但这样也会降低索引的选择性。一般情况下我们需要保证某个列前缀的选择性也是足够高的，以满足查询性能。（尤其对于BLOB、TEXT或者很长的VARCHAR类型的列，应该使用前缀索引，因为MySQL不允许索引这些列的完整长度）。
诀窍在于要选择足够长的前缀以保证较高的选择性，同时又不能太长（以便节约空间)。前缀应该足够长，以使得前缀索引的选择性接近于索引整个列。
按照《阿里最新Java编程规范泰山版》中《(二) 索引规约》中的说法：
建议前缀的长度为20区分度高达90%，我认为这不是绝对的，因为通过计算得出的数据才会更具说服力。
那在实际工作中具体如何做呢？
可以这样计算区分度：区分度 = count(distinct left(列名, 索引长度))/count(*)
SELECT COUNT(DISTINCT LEFT(field, len))/COUNT(*) FROM table_name;
通过调整len的大小，计算获得不同的区分度，区分度越大，越好。当随着len的增加，区分度的值增加的缓慢的时就可以考虑选择一个合适的len建立前缀索引：
ALTER TABLE table_name ADD KEY (field(14));
建立前缀索引后查询语句并不需要更改：
select * from table_name where a = 'xxxx' ;
前缀索引是一种能使索引更小、更快的有效办法，但另一方面也有其缺点，那就是MySQL无法使用前缀索引做ORDER BY和GROUP BY，也无法使用前缀索引做覆盖扫描。 有时候后缀索引 (suffix index)也很有用（例如，找到某个域名的所有电子邮件地址)。MySQL原生并不支持反向索引，但是我们可以转换个思路，既然数据库不支持，那我们可以利用一些小技巧让它支持，比如把字符串反转后存储，并基于此建立前缀索引。还可以通过触发器或者应用程序自行处理来维护索引。
好了，今天的分享就到这里啦，如果有疑问或不对的地方，欢迎大家留言探讨！
如果本篇文章对你有帮助，记得三连～
