MySQL学习笔记（三）索引-上篇

索引是数据库中一个非常重要的概念，能够帮助数据库系统更迅速高效地完成查询。本章将分上下两节来介绍MySQL的索引机制。上篇主要介绍索引的定义和InnoDB的索引实现。下篇主要介绍MyISAM的索引实现和常用类型的索引介绍。

索引的定义

索引是存储引擎用于快速找到记录的一种数据结构。这是索引的基本功能。如果没有索引，执行查询时MySQL必须从第一个记录开始扫描整个表的所有记录，直至找到符合要求的记录。表里面的记录数量越多，这个操作的代价就越高。如果作为搜索条件的列上已经创建了索引，MySQL就能根据索引更快找到目标记录。如果表有1000个记录，通过索引查找记录至少要比顺序扫描记录快100倍。因此，建立高效的索引能够极大提升查询效率。

InnoDB索引实现

InnoDB支持两种索引，B+树索引和哈希索引。自适应的哈希索引是InnoDB的特性之一，所谓自适应性，意为InnoDB会根据表的使用情况自动为表生成哈希索引，这个过程不能被人为干预。

B+树索引

B+树索引是传统意义上的索引，也是目前关系型数据库中最常用的索引，本质上是B+树在数据库中的实现。B+树是由B树和索引顺序访问方法（ISAM）演化而来的一种经典数据结构，在此只做简单了解，不详细讨论其实现方法。

来看如下图所示的一棵B+树，其高度为2，每页可存放4条记录，扇出（fan out）为5。B+树的记录只存放在叶节点中，且按键值的大小顺序存放，每个叶节点指针相互连接。如果从最左边的叶节点开始顺序遍历，可以得到键值的顺序排序：5，10，15，20，25，30，50，55，60，65，75，80，85，90。

B+树示例

B+树索引在数据库中的一个特点是高扇出性，高扇出性意味着更少的层数，在数据库中，B+树的高度一般在2-3层，也就是对于查找任一键值的行记录，最多只需要2-3次IO。按照一般磁盘每秒至少可做100次IO计算，使用B+树索引的每次查询只需0.02-0.03秒就能完成，效率很高。

聚集索引（Clustered Index）

B+树索引可分为聚集索引和辅助索引，它们内部都是B+树结构，高度平衡，叶节点存放所有数据。这里先介绍聚集索引。

InnoDB存储引擎表是索引组织表，即表中数据按照主键顺序存放。聚集索引就是按照每张表的主键构造一棵B+树，并在叶节点中存放整张表的行记录数据，因此也让聚集索引的叶节点成为数据页。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同B+树数据结构一样，每个叶节点（数据页）都通过一个双向链表来进行链接，具体结构可见下图。

InnoDB聚集索引

由于实际的数据页只能按照一颗B+树进行排序，所以每张InnoDB表只有一个聚集索引。大部分情况下，查询优化器倾向于使用聚集索引，这样可以在叶节点上直接找到行数据。并且由于定义了数据的逻辑顺序，聚集索引能很快返回针对范围值的查询。

这里提到了“定义了数据的逻辑顺序”，指的是聚集索引“逻辑上”顺序存储数据，而不是物理上的顺序存储。逻辑上的顺序存储包括数据页通过双向链表链接，页按照主键顺序排列；每个页中的记录也是通过双向链表进行维护，物理存储上可以同样不按照主键存储。

总结一下聚集索引的好处。对于主键的排序查找和范围查找速度非常快。叶节点的数据就是我们要查询的数据，比如我们想要查询一张姓名表的最后十个人，由于B+树索引是双向链表，可以快速找到最后一个叶节点上的数据页，并依次向前查找取出10条记录。对于范围查询（Range Query），如果要查找主键某一范围内的数据，根据上层中间节点就可以得到数据页的范围，之后再直接读取数据页即可。

辅助索引（Secondary Index）

前面我们提到，每张表只有一个建立在主键上的聚集索引。但是我们经常需要针对其他列来创建索引，以便我们更便捷地管理数据。这里的索引就是辅助索引，又叫非聚集索引。辅助索引也是B+树结构的索引，但是它的叶节点不包含行记录，只包含键值和一个书签，这个书签用来告诉InnoDB，哪里能找到与键值对应的行记录。由于InnoDB存储引擎表是索引组织表，因此InnoDB中的辅助索引的书签就是键值对应的主键。下面这张图描述了聚集索引和辅助索引的关系。

InnoDB两级索引

辅助索引的存在不影响数据在聚集索引中的组织，所以每张表可以有多个辅助索引。当查询使用到辅助索引时，InnoDB会先遍历辅助索引并通过叶节点指针获得对应主键，然后再通过聚集索引找到对应的行记录。举例来说，如果在一棵高度为3的辅助索引树种查找数据，需要对辅助索引遍历3次找到指定主键。如果聚集索引树的高度同样为3，则还需要对聚集索引再进行3次查找，最终找到行数据所在的页。总共需要6次逻辑IO.

来看一个具体例子。定义如下一个表：

CREATE TABLE t (

id PK,

name KEY,

sex,

flag

)ENGINE=InnoDB;

表中包含四条记录：

1，dan，f，A

3，alice，m，B

5，helen，m，A

9，frank，f，C

其B+树索引构造如下图所示，id是主键，id索引树为聚集索引，行记录存放在其叶节点上；以name索引建立一棵辅助索引树，叶节点存储主键，也就是id。

当执行SELECT * FROM t WHERE name='alice'这个查询时，InnoDB先通过name辅助索引定位得到id为3，再通过聚集索引定位到具体的行记录，扫描的路径如图中蓝色区块示意。

InnoDB索引机制

自适应哈希索引

InnoDB采用自适应的哈希索引。首先来看一下什么是哈希索引。哈希索引是基于哈希表（散列表）实现的，只有精确匹配索引所有列的查询才有效。在MySQL中，只有Memory引擎显式支持哈希索引，也是其默认的索引类型。

哈希索引实现

对于每一行数据，存储引擎会对所有的索引列计算一个哈希值，这是一个较小的值，且不同键值的行计算出来的哈希值不同。哈希索引存储所有的哈希值，并在哈希表中保存指向每个数据行的指针。Memory引擎支持非唯一哈希索引，就是当不同的键值计算出的哈希值相同时，索引会用链表的方式存放多个记录指针到同一个哈希条目中。

下面来看一个具体例子。我们定义如下一个姓名表：

CREATE TABLE testhash(

fname VARCHAR(20) NOT NULL,

lname VARCHAR(20) NOT NULL,

INDEX USING HASH(fname)

)ENGINE=MEMORY;

在表中插入如图左上角所示的四行数据，之后存储引擎会使用一个哈希函数f( )去计算每行的哈希值（示例数据，非真实数据）。然后生成对应的哈希表。

哈希表的数据结构包括一个槽（slot）和对应的值（value），slot为计算出的哈希值，value则是指向对应行数据的指针。注意到有两行数据计算出的哈希值都是2323，称之为哈希冲突。具有相同哈希值的多个行指针用链表结构来存储，并最终指向对应的行数据。要注意的是，哈希表中slot的存储是顺序的，但是行数据本身不需要顺序存储。

哈希索引机制

我们来看下面这条查询的具体执行过程。

SELECT lname FROM testhash WHERE fname='Peter';

MySQL首先计算 'Peter' 的哈希值为2323，并使用该值寻找对应的记录指针。在哈希索引表中查找2323，第一个指针指向记录 'Arjen Lentz'，但是 'Arjen' 不匹配

索引值 'Peter' .顺着链表往下找到第二个指针，指向记录 'Peter Zaitsev '，与索引值匹配，返回行记录完成此次查询。

哈希索引特性

由于哈希索引只存储对应的哈希值，结构十分紧凑，因此查找的速度非常快。

哈希索引不支持部分索引列匹配查找。比如我们在列（A，B）上建立哈希索引，查询只有数据列A时无法使用这个哈希索引。因为hash（A，B）和hash（A）的值是不同的。

哈希索引数据并不是按照索引值顺序存储的，因此无法用于排序。

哈希索引只支持等值比较查询，比如=，IN（），<=>等；不支持任何范围查询，比如WHERE id>100，因为哈希索引不是按照索引值顺序存储数据的。

访问哈希索引的数据非常快，除非有很多哈希冲突（不同的索引值有相同的哈希值，例如前面例子中2323有2个对应的指针）。当出现哈希冲突时，存储引擎必须遍历链表中所有的行指针，和索引值逐个进行比较，直到找到匹配的行。

如果哈希冲突很多，维护索引的代价也会很高。如果在某个选择性很低（哈希冲突很多）的列上建立哈希索引，当从表中删除一行数据时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应行的引用。冲突越多，代价越大。

从这些特性可知，哈希索引的使用有诸多限制。而一旦哈希索引有了用武之地，查询效率能有非常大的提升。举个例子，在数据仓库应用中有一种经典的星型schema，需要关联很多查找表，哈希索引就非常适合查找表的需求。

自适应的哈希索引

现在回头来看InnoDB的自适应性哈希索引。当InnoDB发现表中某些索引值被频繁引用时，它会在内存中基于B+树索引之上再创建一个哈希索引，使得B+树索引也具有哈希索引的一些优点，比如快速的哈希查找。但自应哈希索引完全是InnoDB存储引擎的内部行为，用户无法控制或修改具体细节，只能通过设置参数innodb_adaptive_hash_index来选择禁用或启用此功能。默认情况下，我们都建议启用该特性。