索引是数据库中一个非常重要的概念,能够帮助数据库系统更迅速高效地完成查询。本章将分上下两节来介绍MySQL的索引机制。上篇主要介绍索引的定义和InnoDB的索引实现。下篇主要介绍MyISAM的索引实现和常用类型的索引介绍。
索引是存储引擎用于快速找到记录的一种数据结构。这是索引的基本功能。如果没有索引,执行查询时MySQL必须从第一个记录开始扫描整个表的所有记录,直至找到符合要求的记录。表里面的记录数量越多,这个操作的代价就越高。如果作为搜索条件的列上已经创建了索引,MySQL就能根据索引更快找到目标记录。如果表有1000个记录,通过索引查找记录至少要比顺序扫描记录快100倍。因此,建立高效的索引能够极大提升查询效率。
InnoDB支持两种索引,B+树索引和哈希索引。自适应的哈希索引是InnoDB的特性之一,所谓自适应性,意为InnoDB会根据表的使用情况自动为表生成哈希索引,这个过程不能被人为干预。
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+树的高度一般在2-3层,也就是对于查找任一键值的行记录,最多只需要2-3次IO。按照一般磁盘每秒至少可做100次IO计算,使用B+树索引的每次查询只需0.02-0.03秒就能完成,效率很高。
B+树索引可分为聚集索引和辅助索引,它们内部都是B+树结构,高度平衡,叶节点存放所有数据。这里先介绍聚集索引。
InnoDB存储引擎表是索引组织表,即表中数据按照主键顺序存放。聚集索引就是按照每张表的主键构造一棵B+树,并在叶节点中存放整张表的行记录数据,因此也让聚集索引的叶节点成为数据页。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同B+树数据结构一样,每个叶节点(数据页)都通过一个双向链表来进行链接,具体结构可见下图。
由于实际的数据页只能按照一颗B+树进行排序,所以每张InnoDB表只有一个聚集索引。大部分情况下,查询优化器倾向于使用聚集索引,这样可以在叶节点上直接找到行数据。并且由于定义了数据的逻辑顺序,聚集索引能很快返回针对范围值的查询。
这里提到了“定义了数据的逻辑顺序”,指的是聚集索引“逻辑上”顺序存储数据,而不是物理上的顺序存储。逻辑上的顺序存储包括数据页通过双向链表链接,页按照主键顺序排列;每个页中的记录也是通过双向链表进行维护,物理存储上可以同样不按照主键存储。
总结一下聚集索引的好处。对于主键的排序查找和范围查找速度非常快。叶节点的数据就是我们要查询的数据,比如我们想要查询一张姓名表的最后十个人,由于B+树索引是双向链表,可以快速找到最后一个叶节点上的数据页,并依次向前查找取出10条记录。对于范围查询(Range Query),如果要查找主键某一范围内的数据,根据上层中间节点就可以得到数据页的范围,之后再直接读取数据页即可。
前面我们提到,每张表只有一个建立在主键上的聚集索引。但是我们经常需要针对其他列来创建索引,以便我们更便捷地管理数据。这里的索引就是辅助索引,又叫非聚集索引。辅助索引也是B+树结构的索引,但是它的叶节点不包含行记录,只包含键值和一个书签,这个书签用来告诉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采用自适应的哈希索引。首先来看一下什么是哈希索引。哈希索引是基于哈希表(散列表)实现的,只有精确匹配索引所有列的查询才有效。在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来选择禁用或启用此功能。默认情况下,我们都建议启用该特性。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。