索引的作用类似指向表中行的指针，能够提高查询速度。尽管索引可以提高查询速度，但是不必要的索引会浪费空间，并且在进行插入、修改 和删除时需要花费额外的力气去更改索引。

1. 在MySQL中使用索引

• CREATE方式
  CREATE可以创建普通索引、唯一索引。

  CREATE INDEX index_name ON table_name (column_list);
  CREATE UNIQUE INDEX index_name ON table_name (column_list);
  

• ALTER方式
  ALTER可以创建普通索引、唯一索引和主键索引。

  ALTER TABLE table_name ADD INDEX (column_list);
  ALTER TABLE table_name ADD UNIQUE INDEX (column_list);
  ALTER TABLE table_name ADD PRIMARY KEY (column_list);
  

• 建表时创建索引

2. 索引的结构

MySQL中有许多中索引结构，常用见的有两种：B+Tree索引和Hash索引。

2.1 Hash索引

Hash索引顾名思义，基于哈希表实现的索引，只有精确匹配索引所有列的查询时才有效。对于每一行数据，存储引擎会对所有索引列计算哈希值，然后将哈希值存在哈希表中，同时哈希表中保存指向每行数据的指针。
对于哈希值相同的，采用“拉链法”解决哈希冲突，类似HashMap。

MySQL中Memory引擎才支持Hash索引。

Hash索引的局限性

• Hash索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行
• Hash索引数据并不是按照索引列的值顺序存储的，所以无法用于排序
• Hash索引也不支持部分索引匹配，因为Hash索引始终使用的是索引列的全部内容来计算哈希值的
• Hash索引只支持等值比较，包括=、IN()、<>；并且不支持任何范围查询，例如WHERE age > 18
• 通常访问Hash索引的数据非常快，除非出现非常多的哈希冲突。因为当哈希冲突时，需要遍历链表，一一比较行指针指向的行数据是否匹配

2.2 B+Tree索引

B+Tree索引可以说是最常见、最普遍使用的索引了，它的结构是一个多叉搜索树。

B+Tree的索引结构解释

它有以下特点：

• 一个节点内的key从左到右是非递减数列
• 与B-Tree不同，因为并不是所有节点都具有相同的域，所以B+Tree中叶子节点和非叶子节点一般大小不同。
• 非叶子节点不存储data，只存储key
• 叶子节点不存储指针
• 每个叶子节点间有一个指向相邻叶子节点的指针【数据库系统对B+Tree做的优化】，它的目的是提高区间的访问性能，如图如果要查询key为10到40的所有数据，当找到10后，只需要顺着节点和指针顺序遍历就可以一次性访问到所有数据。

每个节点可以算作一个磁盘块。真实的数据存储在叶子节点里，非叶子节点不存储真实数据，只存储指引索引方向的数据项。

B+Tree查找过程

如果所以，如果要查找数据项30，那么首先会把磁盘块1加载到内存，此时发生一次IO，在内存中利用二分查找确定30在20和50之间，通过磁盘块1的第一个指针找到磁盘块2的地址；然后把磁盘块2加载到内存，发生第二次IO，30在24和40之间，通过指针将磁盘块6加载到内存，发生第三次IO；最后在内存中查找到数据项30，结束查询，总共发生了三次IO。

估算一下：MySQL将一个节点的大小设为等于一个页，这样每个节点只需要一次IO就可以完全载入。从上面过程我们可知，利用B+Tree查询的话会发生h次IO。利用InnoDB引擎估算一下，InnoDB引擎页的大小默认为16KB，假设主键类型为BIGINT（8 byte），指针类型一般也为4或8个byte，也就是说一个页中大概可以存储16KB/(8 byte + 8 byte)≈1K个索引，也就是说一个高度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3条记录。当然实际情况与这里计算的肯定有不同，但是可以知道B+Tree可以将一次查询的IO次数控制在一个很小的次数。

B+Tree性质

1. 通过上面的分析，我们知道一个页（节点）内索引列越小，可以存放的数据项的数量就越多，树的高度越低。这就是为什么要求索引字段要尽量小。这也是为什么B+Tree把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高。当数据项等于1时将会退化成线性表。
2. 【重要】左前缀原则。当B+Tree的数据项是复合的数据结构，比如(name,sex,age)的时候，B+Tree是按照从左到右的顺序来建立搜索树的，比如当(张三,male,18)来检索的时候，B+Tree会优先比较name来确定下一步的所搜方向，如果name相同再依次比较sex和age，最后得到检索的数据；但当(male,18)这样的没有name的数据来的时候，B+Tree就不知道如何检索数据，因为建立B+Tree的时候第一个比较因子是name，所以必须要先根据name来搜索才能知道下一步怎么查询。比如当(张三,18)这样的数据来检索时，B+Tree可以用name来指定搜索方向，但下一个字段sex的缺失，所以只能把名字等于张三的数据都找到，然后再匹配age是18的数据。

2.3 Hash索引与B+Tree索引区别

• 因为Hash索引是直接取哈希值，所以通常在等值查询时Hash索引要快很多，前提是该哈希值的哈希冲突较少的情况下
• 根据上文可知，Hash索引不支持范围查询，B+Tree索引支持范围查询。因为原先有序的数据在经过哈希算法后，有可能变得不是连续的了，就没法利用索引完成范围查询
• 同理，Hash索引无法利用索引完成排序以及模糊查询，例如LIKE 'xxx%'
• 同理，Hash索引不支持多列索引的左前缀匹配原则
• B+Tree索引搜索效率比较平均，在大量哈希冲突情况下，Hash索引搜索效率很低

3. MySQL索引实现

3.1 MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构，叶子节点的data域存放的是数据记录的地址。

image.png

这里设表一共有三列，假设我们以Col1为主键，则图8是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：

image.png

同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
MyISAM的索引方式也叫做非聚簇索引的，之所以这么称呼是为了与InnoDB的聚簇索引区分。

3.2 InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

image.png

上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，下图为定义在Col3上的一个辅助索引：

image.png

这里以英文字符的ASCII码作为比较准则。聚簇索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

3.3 聚簇索引和非聚簇索引

从上文可知：

• 聚簇索引，数据文件本身就是索引文件，即将索引与数据放在一起
• 非聚簇索引，将数据与索引分开存储，叶子节点存储了指向数据位置的地址，直接指向数据行

在InnoDB中，辅助索引访问数据时总需要二次查找
假设有如下表

image.png
image.png

• InnoDB聚簇索引
  1. 利用id列进行搜索时，将主键作为主索引，行数据存储在叶子节点中，数据文件就是主键索引文件。如果利用WHERE id = 7这样的条件查找主键索引，则按照B+Tree的算法找到对应叶子节点，之后就可以获得行数据。
  2. 如果按照name列为条件进行搜索，则需要两个步骤：第一步在辅助索引B+Tree中检索name为Breke，到达叶子节点获得对应主键10；第二部使用主键10在主索引B+Tree中在执行一次检索操作，最终找到叶节点即可获得整行数据。
• MyIASM非聚簇索引
  非聚簇索引的主索引B+Tree和辅助索引B+Tree看上去没有什么区别，节点结构完全一致，只是存储的内容不同而已：主索引存储的是面向主键的信息，辅助索引存储的是面向辅助列的信息。表的数据单独存在数据文件中，两棵树都是在叶子节点中使用一个地址执行真正的表数据。

参考

---

MySQL索引背后的数据结构及算法原理 - 张洋