专栏首页云学习笔记MySQL学习笔记(三)索引-上篇
原创

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来选择禁用或启用此功能。默认情况下,我们都建议启用该特性。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • MySQL学习笔记(四)索引-下篇

    前面了解过,MyISAM存储引擎的行数据都存放在MYD文件中,索引文件存放于MYI文件中。由于索引与行记录分开存储,所以MyISAM的索引都是辅助索引,也就是非...

    scarlett学习手册
  • MySQL学习笔记(一)MySQL体系结构

    MySQL是当今最通用的数据库软件之一,也是大部分人接触最多,时间最长的数据库软件之一。深入了解MySQL的架构和设计对于DBA,研发和运维都非常重要,能够帮助...

    scarlett学习手册
  • 腾讯云数据库产品介绍

    腾讯云上有许多种数据库产品,本文简单介绍每种产品的介绍,特性,应用场景等,帮助各位根据业务需要选择最适合的数据库。

    scarlett学习手册
  • MySQL优化--概述以及索引优化分析

    win:C:\ProgramData\MySQL\MySQL Server 8.0\my.ini

    shimeath
  • 性能优化-索引优化SQL的方法

    重复索引: 重复索引是指相同的列以相同的顺序建立的同类型的索引,如下表中的 primary key和ID列上的索引就是重复索引

    cwl_java
  • MySQL性能管理及架构设计(二):数据库结构优化、高可用架构设计、数据库索引优化

    1. 减少数据冗余:(数据冗余是指在数据库中存在相同的数据,或者某些数据可以由其他数据计算得到),注意,尽量减少不代表完全避免数据冗余;

    用户5546570
  • 面试技巧,如何通过索引说数据库优化能力,内容来自Java web轻量级开发面试教程

           如果我们需要招个Java方面的高级程序员,一方面看年限(本科3年),具体到数据库方面的技能要求,包括如下三个方面:        第一,是否会...

    用户1153489
  • mysql索引使用技巧及注意事项

    一.索引的作用       一般的应用系统,读写比例在10:1左右,而且插入操作和一般的更新操作很少出现性能问题,遇到最多的,也是最容易出问题的,还是一些复杂...

    猿人谷
  • Oracle 索引

    create table bigdata as select rownum as id, TO_CHAR(sysdate,'yyyy-mm-dd hh24:m...

    郑小超.
  • MySQL索引知识学习笔记

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    SmileNicky

扫码关注云+社区

领取腾讯云代金券