索引原理,MySQL的InnoDB索引原理详解

必赢365net手机版 41

本文由  网易云发布。

转自:MySQL的InnoDB索引原理详解

 

1
、搜索二叉树:每个节点有两个子节点,数据量的增大必然导致高度的快速增加,显然这个不适合作为大量数据存储的基础结构。

作者:范鹏程,网易考拉海购

2、
B树:一棵m阶B树是一棵平衡的m路搜索树。最重要的性质是每个非根节点所包含的关键字个数
j 满足:┌m/2┐ – 1 <= j <= m –
1;一个节点的子节点数量会比关键字个数多1,这样关键字就变成了子节点的分割标志。一般会在图示中把关键字画到子节点中间,非常形象,也容易和后面的B+树区分。由于数据同时存在于叶子节点和非叶子结点中,无法简单完成按顺序遍历B树中的关键字,必须用中序遍历的方法。

InnoDB是
MySQL最常用的存储引擎,了解InnoDB存储引擎的索引对于日常工作有很大的益处,索引的存在便是为了加速数据库行记录的检索。以下是我对最近学习的知识的一些总结,以及对碰到的以及别人提到过的问题的一些分析,如有错误,请指正,我会及时更正。

3、
B+树:一棵m阶B树是一棵平衡的m路搜索树。最重要的性质是每个非根节点所包含的关键字个数
j 满足:┌m/2┐ – 1 <= j <=
m;子树的个数最多可以与关键字一样多。非叶节点存储的是子树里最小的关键字。同时数据节点只存在于叶子节点中,且叶子节点间增加了横向的指针,这样顺序遍历所有数据将变得非常容易。

目录

InnoDB表结构

B树与B+树

聚簇索引和二级索引

SQL执行顺序

SQL优化建议

一些问题分析

参考资料

4
、B*树:一棵m阶B树是一棵平衡的m路搜索树。最重要的两个性质是1每个非根节点所包含的关键字个数
j 满足:┌m2/3┐ – 1 <= j <= m;2非叶节点间添加了横向指针。

1. InnoDB表结构

此小结与索引其实没有太多的关联,但是为了便于理解索引的内容,添加此小结作为铺垫知识。

1.1 InnoDB逻辑存储结构

MySQL表中的所有数据被存储在一个空间内,称之为表空间,表空间内部又可以分为段(segment)、区(extent)、页(page)、行(row),逻辑结构如下图:

必赢365net手机版 1

  • 段(segment)

表空间是由不同的段组成的,常见的段有:数据段,索引段,回滚段等等,在
MySQL中,数据是按照B+树来存储,因此数据即索引,因此数据段即为B+树的叶子节点,索引段为B+树的非叶子节点,回滚段用于存储undo日志,用于事务失败后数据回滚以及在事务未提交之前通过undo日志获取之前版本的数据,在InnoDB1.1版本之前一个InnoDB,只支持一个回滚段,支持1023个并发修改事务同时进行,在InnoDB1.2版本,将回滚段数量提高到了128个,也就是说可以同时进行128*1023个并发修改事务。

  • 区(extent)

区是由连续页组成的空间,每个区的固定大小为1MB,为保证区中页的连续性,InnoDB会一次从磁盘中申请4~5个区,在默认不压缩的情况下,一个区可以容纳64个连续的页。但是在开始新建表的时候,空表的默认大小为96KB,是由于为了高效的利用磁盘空间,在开始插入数据时表会先利用32个页大小的碎片页来存储数据,当这些碎片使用完后,表大小才会按照MB倍数来增加。

  • 页(page)

页是InnoDB存储引擎的最小管理单位,每页大小默认是16KB,从InnoDB
1.2.x版本开始,可以利用innodb_page_size来改变页size,但是改变只能在初始化InnoDB实例前进行修改,之后便无法进行修改,除非mysqldump导出创建新库,常见的页类型有:数据页、undo页、系统页、事务数据页、插入缓冲位图页、插入缓冲空闲列表页、未压缩的二进制大对象页、压缩的二进制大对象页。

  • 行(row)

行对应的是表中的行记录,每页存储最多的行记录也是有硬性规定的最多16KB/2-200,即7992行(16KB是页大小,我也不明白为什么要这么算,据说是内核定义)

1.2 InnoDB行记录格式

InnoDB提供了两种格式来存储行记录:Redundant格式、Compact格式、Dynamic格式、Compressed格式,Redudant格式是为了兼容保留的。

Redundant行格式(5.0版本之前的格式)

必赢365net手机版 2

  • 字段长度偏移列表:存储字段偏移量,与列字段顺序相反存放,若列长度小于255字节,用一个字节表示,若大于255字节,用两个字节表示
  • 记录头信息:固定用6字节表示,具体含义如下:

必赢365net手机版 3

隐藏列:事务id和回滚列id,分别占用6、7字节,若此表没有主键,还会增加6字节的rowid列。

Compact行格式(5.6版本的默认行格式)

必赢365net手机版 4

  • 变长字段长度列表:此字段标识列字段的长度,与列字段顺序相反存放,若列长度小于255字节,用一个字节表示,若大于255字节,用两个字节表示,这也是
    MySQL的VARCHAR类型最大长度限制为65535
  • NULL标志位:标识改列是否有空字段,有用1表示,否则为0,该标志位长度为ceil(N/8)(此处是
    MySQL技术内幕-InnoDB存储引擎与官方文档有出入的地方);
  • 记录头信息:固定用5字节表示,具体含义如下:

必赢365net手机版 5

  • 列数据:此行存储着列字段数据,Null是不占存储空间的;
  • 隐藏列:事务id和回滚列id,分别占用6、7字节,若此表没有主键,还会增加6字节的rowid列。

Note:
关于行溢出,即Redundant格式、Compact格式存储很长的字符串,在该字段会存储该字符串的前768个字节的前缀(字段超过768字节则为变长字段),并将整个字符串存储在uncompress
blob页中。

Dynamic格式(5.7版本默认行格式)和Compressed格式

Dynamic格式和Compressed格式与Compact的不同之处在于对于行溢出只会在该列处存放20字节的指针,指向该字符串的实际存储位置,不会存储768字节前缀,而且Compressed格式在存储BLOB、TEXT、VARCHAR等类型会利用zlib算法进行压缩,能够以很高的存储效率来存储字符串。

1.3 InnoDB数据页结构


MySQL技术内幕-InnoDB存储引擎》书中对此有描述,但是应该不是太准确,书中有如下描述,此处不做详细介绍,若有兴趣请看此神书。

必赢365net手机版 6

必赢365net手机版 7

2. B树与B+树

B树与B+树通常用于数据库和操作系统的文件系统中。NTFS, ReiserFS, NSS,
XFS, JFS, ReFS 和BFS等文件系统都在使用B+树作为元数据索引。B+
树的特点是能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。

2.1 B树

定义:

B树(B-TREE)满足如下条件,即可称之为m阶B树:

  • 每个节点之多拥有m棵子树;
  • 根结点至少拥有两颗子树(存在子树的情况下);
  • 除了根结点以外,其余每个分支结点至少拥有 m/2 棵子树;
  • 所有的叶结点都在同一层上;
  • 有 k 棵子树的分支结点则存在 k-1
    个关键码,关键码按照递增次序进行排列;
  • 关键字数量需要满足ceil(m/2)-1 <= n <= m-1;

B树插入

必赢365net手机版 8

B树删除

必赢365net手机版 9

2.2 B+树

定义:

B+树满足如下条件,即可称之为m阶B+树:

  • 根结点只有一个,分支数量范围为[2,m]
  • 分支结点,每个结点包含分支数范围为[ceil(m/2), m];
  • 分支结点的关键字数量等于其子分支的数量减一,关键字的数量范围为[ceil(m/2)-1,
    m-1],关键字顺序递增;
  • 所有叶子结点都在同一层;

插入:

B+树的插入必须保证插入后叶节点中的记录依然排序,同时需要考虑插入B+树的三种情况,每种情况都可能会导致不同的插入算法,插入算法入下图:

必赢365net手机版 10

插入举例(未加入双向链表):

1、 插入28这个键值,发现当前Leaf Page和Index Page都没有满,直接插入。

必赢365net手机版 11

2、 插入70这个键值,Leaf Page已经满了,但是Index
Page还没有满,根据中间的值60拆分叶节点。

必赢365net手机版 12

3、 插入记录95,Leaf Page和Index Page都满了,这时需要做两次拆分

必赢365net手机版 13

4、
B+树总是会保持平衡。但是为了保持平衡,对于新插入的键值可能需要做大量的拆分页(split)操作,而B+树主要用于磁盘,因此页的拆分意味着磁盘数据移动,应该在可能的情况下尽量减少页的拆分。因此,B+树提供了旋转(rotation)的功能。旋转发生在Leaf
Page已经满了、但是其左右兄弟节点没有满的情况下。这时B+树并不会急于去做拆分页的操作,而是将记录移到所在页的兄弟节点上。通常情况下,左兄弟被首先检查用来做旋转操作,在第一张图情况下,插入键值70,其实B+树并不会急于去拆分叶节点,而是做旋转,50,55,55旋转。

必赢365net手机版 14

删除:

B+树使用填充因子(fill
factor)来控制树的删除变化,50%是填充因子可设的最小值。B+树的删除操作同样必须保证删除后叶节点中的记录依然排序,同插入一样,B+树的删除操作同样需要考虑下图所示的三种情况,与插入不同的是,删除根据填充因子的变化来衡量。

必赢365net手机版 15

删除示例(未加入双向链表):

1、删除键值为70的这条记录,直接删除(在插入第三点基础上的图)。

必赢365net手机版 16

2、接着我们删除键值为25的记录,该值还是Index Page中的值,因此在删除Leaf
Page中25的值后,还应将25的右兄弟节点的28更新到Page Index中。

必赢365net手机版 17

3、删除键值为60的情况,删除Leaf
Page中键值为60的记录后,填充因子小于50%,这时需要做合并操作,同样,在删除Index
Page中相关记录后需要做Index Page的合并操作。

必赢365net手机版 18

B树与B+树区别:

以m阶树为例:

  • 关键字不同:B+树中分支结点有m个关键字,其叶子结点也有m个,但是B树虽然也有m个子结点,但是其只拥有m-1个关键字。
  • 存储位置不同:B+树非叶子节点的关键字只起到索引作用,实际的关键字存储在叶子节点,B树的非叶子节点也存储关键字。
  • 分支构造不同:B+树的分支结点仅仅存储着关键字信息和儿子的指针,也就是说内部结点仅仅包含着索引信息。
  • 查询不同(稳定):B树在找到具体的数值以后,则结束,而B+树则需要通过索引找到叶子结点中的数据才结束,也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。

二叉搜索树和B树

3. 聚簇索引和二级索引

3.1 聚簇索引

每个InnoDB的表都拥有一个索引,称之为聚簇索引,此索引中存储着行记录,一般来说,聚簇索引是根据主键生成的。为了能够获得高性能的查询、插入和其他数据库操作,理解InnoDB聚簇索引是很有必要的。

聚簇索引按照如下规则创建:

  • 当定义了主键后,InnoDB会利用主键来生成其聚簇索引;
  • 如果没有主键,InnoDB会选择一个非空的唯一索引来创建聚簇索引;
  • 如果这也没有,InnoDB会隐式的创建一个自增的列来作为聚簇索引。

Note:
对于选择唯一索引的顺序是按照定义唯一索引的顺序,而非表中列的顺序,
同时选中的唯一索引字段会充当为主键,或者InnoDB隐式创建的自增列也可以看做主键。

聚簇索引整体是一个b+树,非叶子节点存放的是键值,叶子节点存放的是行数据,称之为数据页,这就决定了表中的数据也是聚簇索引中的一部分,数据页之间是通过一个双向链表来链接的,上文说到B+树是一棵平衡查找树,也就是聚簇索引的数据存储是有序的,但是这个是逻辑上的有序,但是在实际在数据的物理存储上是,因为数据页之间是通过双向链表来连接,假如物理存储是顺序的话,那维护聚簇索引的成本非常的高。

3.2 辅助索引

除了聚簇索引之外的索引都可以称之为辅助索引,与聚簇索引的区别在于辅助索引的叶子节点中存放的是主键的键值。一张表可以存在多个辅助索引,但是只能有一个聚簇索引,通过辅助索引来查找对应的航记录的话,需要进行两步,第一步通过辅助索引来确定对应的主键,第二步通过相应的主键值在聚簇索引中查询到对应的行记录,也就是进行两次B+树搜索。相反通过辅助索引来查询主键的话,遍历一次辅助索引就可以确定主键了,也就是所谓的索引覆盖,不用回表(查询聚簇索引)。

创建辅助索引,可以创建单列的索引,也就是用一个字段来创建索引,也可以用多个字段来创建副主索引称为联合索引,创建联合索引后,B+树的节点存储的键值数量不是1个,而是多个,如下图:

必赢365net手机版 19

  • 联合索引的B+树和单键辅助索引的B+树是一样的,键值都是排序的,通过叶子节点可以逻辑顺序的读出所有的数据,比如上图所存储的数据时,按照(a,b)这种形式(1,1),(1,2),(2,1),(2,4),(3,1),(3,2)进行存放,这样有个好处存放的数据时排了序的,当进行order by对某个字段进行排序时,可以减少复杂度,加速进行查询;
  • 当用select * from table where a=? and ?可以使用索引(a,b)来加速查询,但是在查询时有一个原则,sql的where条件的顺序必须和二级索引一致,而且还遵循索引最左原则,select * from table where b=?则无法利用(a,b)索引来加速查询。
  • 辅助索引还有一个概念便是索引覆盖,索引覆盖的一个好处便是辅助索引不高含行记录,因此其大小远远小于聚簇索引,利用辅助索引进行查询可以减少大量的IO操作。

必赢365net手机版 20

4. SQL执行顺序

以下的每一步操作都会生成一个虚拟表,作为下一个处理的输入,在这个过程中,这些虚拟表对于用户都是透明的,只用最后一步执行完的虚拟表返回给用户,在处理过程中,没有的步骤会直接跳过。

以下为逻辑上的执行顺序:

必赢365net手机版 21

(1)
from:对左表left-table和右表right-table执行笛卡尔积(a*b),形成虚拟表VT1;

必赢365net手机版,(2) on:
对虚拟表VT1进行on条件进行筛选,只有符合条件的记录才会插入到虚拟表VT2中;

(3) join: 指定out
join会将未匹配行添加到VT2产生VT3,若有多张表,则会重复(1)~(3);

(4) where: 对VT3进行条件过滤,形成VT4, where条件是从左向右执行的;

(5) group by: 对VT4进行分组操作得到VT5;

(6) cube | rollup: 对VT5进行cube | rollup操作得到VT6;

(7) having: 对VT6进行过滤得到VT7;

(8) select: 执行选择操作得到VT8,本人看来VT7和VT8应该是一样的;

(9) distinct: 对VT8进行去重,得到VT9;

(10) order by: 对VT9进行排序,得到VT10;

(11) limit: 对记录进行截取,得到VT11返回给用户。

Note:
on条件应用于连表过滤,where应用于on过滤后的结果(有on的话),having应用于分组过滤

B+树

5. SQL优化建议

索引有如下有点:减少服务器扫描的数据量、避免排序和临时表、将随机I/O变为顺序I/O。

可使用B+树索引的查询方式

  • 全值匹配:与索引中的所有列进行匹配,也就是条件字段与联合索引的字段个数与顺序相同;
  • 匹配最左前缀:只使用联合索引的前几个字段;
  • 匹配列前缀:比如like ‘xx%’可以走索引;
  • 匹配范围值:范围查询,比如>,like等;
  • 匹配某一列并范围匹配另外一列:精确查找+范围查找;
  • 只访问索引查询:索引覆盖,select的字段为主键;

范围查询后的条件不会走索引,具体原因会在下一节进行介绍。

列的选择性(区分度)

选择性(区分度)是指不重复的列值个数/列值的总个数,一般意义上建索引的字段要区分度高,而且在建联合索引的时候区分度高的列字段要放在前边,这样可以在第一个条件就过滤掉大量的数据,有利用性能的提升,对于如何计算列的区分度,有如下两种方法:

  • 根据定义,手动计算列的区分度,不重复的列值个数/列值的总个数;
  • 通过
    MySQL的carlinality,通过命令show index from <table_name>来查看,解释一下,此处的carlinality并不是准确值,而且
    MySQL在B+树种选择了8个数据页来抽样统计的值,也就是说carlinality=每个数据页记录总和/8*所有的数据页,因此也说明这个值是不准确的,因为在插入/更新记录时,实时的去更新carlinality对于
    MySQL的负载是很高的,如果数据量很大的话,触发
    MySQL重新统计该值得条件是当表中的1/16数据发生变化时。

但是选择区分度高的列作为索引也不是百试百灵的,某些情况还是不合适的,下节会进行介绍。

MySQL查询过程

当希望 MySQL能够高性能运行的时候,最好的办法就是明白
MySQL是如何优化和执行的,一旦理解了这一点,很多查询优化工作实际上就是遵循了一些原则让优化器能够按照预想的合理的方式运行————《引用自高性能
MySQL 》

当想 MySQL实例发送一个请求时, MySQL按照如下图的方式进行查询:

必赢365net手机版 22

  • 客户端先发送一条查询给服务器;
  • 服务器先检查查询缓存,如果命中了缓存,则立刻返回给存储在缓存中的结果,否则进入下一个阶段;
  • 服务器端进行SQL解析、预处理,再由优化器生成对应的执行计划;
  • MySQL 根据优化器生成的执行计划,调用存储引擎的API来执行查询;
  • 将结果返回客户端。

注意&建议

  • 主键推荐使用整型,避免索引分裂;
  • 查询使用索引覆盖能够提升很大的性能,因为避免了回表查询;
  • 选择合适的顺序建立索引,有的场景并非区分度越高的列字段放在前边越好,联合索引使用居多;
  • 合理使用in操作将范围查询转换成多个等值查询;
  • in操作相当于多个等值操作,但是要注意的是对于order
    by来说,这相当于范围查询,因此例如select * from t1 where c1 in
    (x,x) order by c2的sql是不走索引的;
  • 将大批量数据查询任务分解为分批查询;
  • 将复杂查询转换为简单查询;
  • 合理使用inner join,比如说分页时候。

必赢365net手机版 23

6. 一些问题分析

这个部分是我在学习过程中产生的一些疑问,以及在工作中碰到的或者同事提起的一些问题,对此我做了些调研,总结了一下并添加了些自己的理解,如有错误还请指正。

索引分裂

此处提一下索引分裂,就我个人理解,在
MySQL插入记录的同时会更新配置的相应索引文件,根据以上的了解,在插入索引时,可能会存在索引的页的分裂,因此会导致磁盘数据的移动。当插入的主键是随机字符串时,每次插入不会是在B+树的最后插入,每次插入位置都是随机的,每次都可能导致数据页的移动,而且字符串的存储空间占用也很大,这样重建索引不仅仅效率低而且
MySQL的负载也会很高,同时还会导致大量的磁盘碎片,磁盘碎片多了也会对查询造成一定的性能开销,因为存储位置不连续导致更多的磁盘I/O,这就是为什么推荐定义主键为递增整型的一个原因,
MySQL索引页默认大小是16KB,当有新纪录插入的时候,
MySQL会留下每页空间的1/16用于未来索引记录增长,避免过多的磁盘数据移动。

自增主键的弊端

对于高并发的场景,在InnoDB中按照主键的顺序插入可能会造成明显的争用,主键的上界会成为“热点”,因为所有的插入都发生在此处,索引并发的插入可能会造成间隙锁竞争,何为间隙锁竞争,下个会详细介绍;另外一个原因可能是Auto_increment的锁机制,在
MySQL处理自增主键时,当innodb_autoinc_lock_mode为0或1时,在不知道插入有多少行时,比如insert t1 xx select xx from t2,对于这个statement的执行会进行锁表,只有这个statement执行完以后才会释放锁,然后别的插入才能够继续执行,但是在innodb_autoinc_lock_mode=2时,这种情况不会存在表锁,但是只能保证所有并发执行的statement插入的记录是唯一并且自增的,但是每个statement做的多行插入之间是不连接的。

优化器不使用索引选择全表扫描

比如一张order表中有联合索引(order_id,
goods_id),在此例子上来说明这个问题是从两个方面来说:

  • 查询字段在索引中

select order_id from order where order_id > 1000,如果查看其执行计划的话,发现是用use
index condition,走的是索引覆盖。

  • 查询字段不在索引中

select * from order where order_id > 1000,
此条语句查询的是该表所有字段,有一部分字段并未在此联合索引中,因此走联合索引查询会走两步,首先通过联合索引确定符合条件的主键id,然后利用这些主键id再去聚簇索引中去查询,然后得到所有记录,利用主键id在聚簇索引中查询记录的过程是无序的,在磁盘上就变成了离散读取的操作,假如当读取的记录很多时(一般是整个表的20%左右),这个时候优化器会选择直接使用聚簇索引,也就是扫全表,因为顺序读取要快于离散读取,这也就是为何一般不用区分度不大的字段单独做索引,注意是单独因为利用此字段查出来的数据会很多,有很大概率走全表扫描。

范围查询之后的条件不走索引

根据
MySQL的查询原理的话,当处理到where的范围查询条件后,会将查询到的行全部返回到服务器端(查询执行引擎),接下来的条件操作在服务器端进行处理,这也就是为什么范围条件不走索引的原因了,因为之后的条件过滤已经不在存储引擎完成了。但是在
MySQL 5.6以后假如了一个新的功能index condition
pushdown(ICP),这个功能允许范围查询条件之后的条件继续走索引,但是需要有几个前提条件:

  • 查询条件的第一个条件需要时有边界的,比如select * from xx where c1=x and c2>x and c3<x,这样c3是可以走到索引的;
  • 支持InnoDB和MyISAM存储引擎;
  • where条件的字段需要在索引中;
  • 分表ICP功能5.7开始支持;
  • 使用索引覆盖时,ICP不起作用。

set @@optimizer_switch = “index_condition_pushdown=on” 开启ICP set
@@optimizer_switch = “index_condition_pushdown=off” 关闭ICP

范围查询统计函数不遵循 MySQL索引最左原则

比如创建一个表:

create table `person`(
`id` int not null auto_increment primary key,
`uid` int not null,
`name` varchar(60) not null,
`time` date not null,
key `idx_uid_date` (uid, time)
)engine=innodb default charset=utf8mb4;

当执行select count(*) from person where time > '2018-03-11' and time < '2018-03-16'时,time是可以用到idx_uid_date`的索引的,看如下的执行计划:

必赢365net手机版 24

其中extra标识use index说明是走索引覆盖的,一般意义来说是
MySQL是无法支持松散索引的,但是对于统计函数,是可以使用索引覆盖的,因此
MySQL的优化器选择利用该索引。

分页offset值很大性能问题

在 MySQL中,分页当offset值很大的时候,性能会非常的差,比如limit 100000,
20,需要查询100020条数据,然后取20条,抛弃前100000条,在这个过程中产生了大量的随机I/O,这是性能很差的原因,为了解决这个问题,切入点便是减少无用数据的查询,减少随机I/O。
解决的方法是利用索引覆盖,也就是扫描索引得到id然后再从聚簇索引中查询行记录,我知道有两种方式:

比如从表t1中分页查询limit 1000000,5

  • 利用inner join

select * from t1 inner join (select id from t1 where xxx order by xx limit 1000000,5) as t2 using(id),子查询先走索引覆盖查得id,然后根据得到的id直接取5条得数据。

  • 利用范围查询条件来限制取出的数据

select * from t1 where id > 1000000 order by id limit 0, 5,即利用条件id > 1000000在扫描索引是跳过1000000条记录,然后取5条即可,这种处理方式的offset值便成为0了,但此种方式通常分页不能用,但是可以用来分批取数据。

索引合并

SELECT * FROM tbl_name WHERE key1 = 10 OR key2 = 20;
SELECT * FROM tbl_name WHERE (key1 = 10 OR key2 = 20) AND non_key=30;
SELECT * FROM t1, t2 WHERE (t1.key1 IN (1,2) OR t1.key2 LIKE 'value%') AND t2.key1=t1.some_col;
SELECT * FROM t1, t2 WHERE t1.key1=1 AND (t2.key1=t1.some_col OR t2.key2=t1.some_col2);

对于如上的sql在 MySQL
5.0版本之前,假如没有建立相应的联合索引,是要走全表扫描的,但是在 MySQL
5.1后引入了一种优化策略为索引合并,可以在一定程度上利用表上的多个单列索引来定位指定行,其原理是将对每个索引的扫描结果做运算,总共有:交集、并集以及他们的组合,但是索引合并并非是一种合适的选择,因为在做索引合并时可能会消耗大量的CPU和内存资源,一般用到索引合并的情况也从侧面反映了该表的索引需要优化。

B*树

7. 参考资料


  • MySQL技术内幕-InnoDB存储引擎》:此书对于InnoDB的讲解是比较全面而且细致的,但是稍微有一点点老并且还有一点点错误地方,此书是基于
    MySQL 5.6版本的,里边会混杂一些5.7的知识。
  • 《 MySQL技术内幕:SQL编程》:值得一看。
  • 《高性能 MySQL 第三版》:此书是一本 MySQL神书,里边有很多的
    MySQL优化建议以及一些案例。
  • 官方文档:这个是比较权威而且是最新的文档,缺点是篇幅很长,内容很多,而且还是纯英文,在理解和阅读速度上相对而言没有中文来得快。

 

延伸阅读

深入解析 SQL Server
高可用镜像实现原理

MySQL慢日志功能分析及优化增强

网易云:时序数据库(TSDB)-为万物互联插上一双翅膀

 

 

了解 网易云 :
网易云官网:https://www.163yun.com/
新用户大礼包:https://www.163yun.com/gift
网易云社区:https://sq.163yun.com/

 

 B/B+/B*三种树有相似的操作,比如检索/插入/删除节点。这里只重点关注插入节点的情况,且只分析他们在当前节点已满情况下的插入操作,因为这个动作稍微复杂且能充分体现几种树的差异。与之对比的是检索节点比较容易实现,而删除节点只要完成与插入相反的过程即可(在实际应用中删除并不是插入的完全逆操作,往往只删除数据而保留下空间为后续使用)。

  先看B树的分裂,下图的红色值即为每次新插入的节点。每当一个节点满后,就需要发生分裂(分裂是一个递归过程,参考下面7的插入导致了两层分裂),由于B树的非叶子节点同样保存了键值,所以已满节点分裂后的值将分布在三个地方:1原节点,2原节点的父节点,3原节点的新建兄弟节点(参考5,7的插入过程)。分裂有可能导致树的高度增加(参考3,7的插入过程),也可能不影响树的高度(参考5,6的插入过程)。

必赢365net手机版 25

B树的节点分裂

 B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟节点的指针。

必赢365net手机版 26

B+树节点分裂

 B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了)。如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针。可以看到B*树的分裂非常巧妙,因为B*树要保证分裂后的节点还要2/3满,如果采用B+树的方法,只是简单的将已满的节点一分为二,会导致每个节点只有1/2满,这不满足B*树的要求了。所以B*树采取的策略是在本节点满后,继续插入兄弟节点(这也是为什么B*树需要在非叶子节点加一个兄弟间的链表),直到把兄弟节点也塞满,然后拉上兄弟节点一起凑份子,自己和兄弟节点各出资1/3成立新节点,这样的结果是3个节点刚好是2/3满,达到B*树的要求,皆大欢喜。

必赢365net手机版 27

B*树的节点分裂

  B+树适合作为数据库的基础结构,完全是因为计算机的内存-机械硬盘两层存储结构。内存可以完成快速的随机访问(随机访问即给出任意一个地址,要求返回这个地址存储的数据)但是容量较小。而硬盘的随机访问要经过机械动作(1磁头移动
2盘片转动),访问效率比内存低几个数量级,但是硬盘容量较大。典型的数据库容量大大超过可用内存大小,这就决定了在B+树中检索一条数据很可能要借助几次磁盘IO操作来完成。如下图所示:通常向下读取一个节点的动作可能会是一次磁盘IO操作,不过非叶节点通常会在初始阶段载入内存以加快访问速度。同时为提高在节点间横向遍历速度,真实数据库中可能会将图中蓝色的CPU计算/内存读取优化成二叉搜索树(InnoDB中的page
directory机制)。

必赢365net手机版 28

B+树检索过程

  真实数据库中的B+树应该是非常扁平的,可以通过向表中顺序插入足够数据的方式来验证InnoDB中的B+树到底有多扁平。我们通过如下图的CREATE语句建立一个只有简单字段的测试表,然后不断添加数据来填充这个表。通过下图的统计数据(来源见参考文献1)可以分析出几个直观的结论,这几个结论宏观的展现了数据库里B+树的尺度。

  1
每个叶子节点存储了468行数据,每个非叶子节点存储了大约1200个键值,这是一棵平衡的1200路搜索树!

  2
对于一个22.1G容量的表,也只需要高度为3的B+树就能存储了,这个容量大概能满足很多应用的需要了。如果把高度增大到4,则B+树的存储容量立刻增大到25.9T之巨!

  3
对于一个22.1G容量的表,B+树的高度是3,如果要把非叶节点全部加载到内存也只需要少于18.8M的内存(如何得出的这个结论?因为对于高度为2的树,1203个叶子节点也只需要18.8M空间,而22.1G从良表的高度是3,非叶节点1204个。同时我们假设叶子节点的尺寸是大于非叶节点的,因为叶子节点存储了行数据而非叶节点只有键和少量数据。),只使用如此少的内存就可以保证只需要一次磁盘IO操作就检索出所需的数据,效率是非常之高的。

必赢365net手机版 29

扁平的B+树

可以说数据库必须有索引,没有索引则检索过程变成了顺序查找,O(n)的时间复杂度几乎是不能忍受的。我们非常容易想象出一个只有单关键字组成的表如何使用B+树进行索引,只要将关键字存储到树的节点即可。当数据库一条记录里包含多个字段时,一棵B+树就只能存储主键,如果检索的是非主键字段,则主键索引失去作用,又变成顺序查找了。这时应该在第二个要检索的列上建立第二套索引。
 这个索引由独立的B+树来组织。有两种常见的方法可以解决多个B+树访问同一套表数据的问题,一种叫做聚簇索引(clustered
index ),一种叫做非聚簇索引(secondary
index)。这两个名字虽然都叫做索引,但这并不是一种单独的索引类型,而是一种数据存储方式。对于聚簇索引存储来说,行数据和主键B+树存储在一起,辅助键B+树只存储辅助键和主键,主键和非主键B+树几乎是两种类型的树。对于非聚簇索引存储来说,主键B+树在叶子节点存储指向真正数据行的指针,而非主键。

  InnoDB使用的是聚簇索引,将主键组织到一棵B+树中,而行数据就储存在叶子节点上,若使用”where
id =
14″这样的条件查找主键,则按照B+树的检索算法即可查找到对应的叶节点,之后获得行数据。若对Name列进行条件搜索,则需要两个步骤:第一步在辅助索引B+树中检索Name,到达其叶子节点获取对应的主键。第二步使用主键在主索引B+树种再执行一次B+树检索操作,最终到达叶子节点即可获取整行数据。

  MyISM使用的是非聚簇索引,非聚簇索引的两棵B+树看上去没什么不同,节点的结构完全一致只是存储的内容不同而已,主键索引B+树的节点存储了主键,辅助键索引B+树存储了辅助键。表数据存储在独立的地方,这两颗B+树的叶子节点都使用一个地址指向真正的表数据,对于表数据来说,这两个键没有任何差别。由于索引树是独立的,通过辅助键检索无需访问主键的索引树。

  为了更形象说明这两种索引的区别,我们假想一个表如下图存储了4行数据。其中Id作为主索引,Name作为辅助索引。图示清晰的显示了聚簇索引和非聚簇索引的差异。

必赢365net手机版 30

必赢365net手机版 31

  我们重点关注聚簇索引,看上去聚簇索引的效率明显要低于非聚簇索引,因为每次使用辅助索引检索都要经过两次B+树查找,这不是多此一举吗?聚簇索引的优势在哪?

  1
由于行数据和叶子节点存储在一起,这样主键和行数据是一起被载入内存的,找到叶子节点就可以立刻将行数据返回了,如果按照主键Id来组织数据,获得数据更快。

  2 辅助索引使用主键作为”指针”
而不是使用地址值作为指针的好处是,减少了当出现行移动或者数据页分裂时辅助索引的维护工作,使用主键值当作指针会让辅助索引占用更多的空间,换来的好处是InnoDB在移动行时无须更新辅助索引中的这个”指针”。也就是说行的位置(实现中通过16K的Page来定位,后面会涉及)会随着数据库里数据的修改而发生变化(前面的B+树节点分裂以及Page的分裂),使用聚簇索引就可以保证不管这个主键B+树的节点如何变化,辅助索引树都不受影响。

  3 Page结构

  如果说前面的内容偏向于解释原理,那后面就开始涉及具体实现了。

  理解InnoDB的实现不得不提Page结构,Page是整个InnoDB存储的最基本构件,也是InnoDB磁盘管理的最小单位,与数据库相关的所有内容都存储在这种Page结构里。Page分为几种类型,常见的页类型有数据页(B-tree
Node)Undo页(Undo Log Page)系统页(System Page)
事务数据页(Transaction System
Page)等。单个Page的大小是16K(编译宏UNIV_PAGE_SIZE控制),每个Page使用一个32位的int值来唯一标识,这也正好对应InnoDB最大64TB的存储容量(16Kib
* 2^32 = 64Tib)。一个Page的基本结构如下图所示:

必赢365net手机版 32

  每个Page都有通用的头和尾,但是中部的内容根据Page的类型不同而发生变化。Page的头部里有我们关心的一些数据,下图把Page的头部详细信息显示出来:

必赢365net手机版 33

  我们重点关注和数据组织结构相关的字段:Page的头部保存了两个指针,分别指向前一个Page和后一个Page,头部还有Page的类型信息和用来唯一标识Page的编号。根据这两个指针我们很容易想象出Page链接起来就是一个双向链表的结构。

必赢365net手机版 34

  再看看Page的主体内容,我们主要关注行数据和索引的存储,他们都位于Page的User
Records部分,User Records占据Page的大部分空间,User
Records由一条一条的Record组成,每条记录代表索引树上的一个节点(非叶子节点和叶子节点)。在一个Page内部,单链表的头尾由固定内容的两条记录来表示,字符串形式的”Infimum”代表开头,”Supremum”代表结尾。这两个用来代表开头结尾的Record存储在System
Records的段里,这个System Records和User
Records是两个平行的段。InnoDB存在4种不同的Record,它们分别是1主键索引树非叶节点
2主键索引树叶子节点 3辅助键索引树非叶节点
4辅助键索引树叶子节点。这4种节点的Record格式有一些差异,但是它们都存储着Next指针指向下一个Record。后续我们会详细介绍这4种节点,现在只需要把Record当成一个存储了数据同时含有Next指针的单链表节点即可。

必赢365net手机版 35

  User
Record在Page内以单链表的形式存在,最初数据是按照插入的先后顺序排列的,但是随着新数据的插入和旧数据的删除,数据物理顺序会变得混乱,但他们依然保持着逻辑上的先后顺序。

必赢365net手机版 36

  把User Record的组织形式和若干Page组合起来,就看到了稍微完整的形式。

必赢365net手机版 37

  现在看下如何定位一个Record:

  1
通过根节点开始遍历一个索引的B+树,通过各层非叶子节点最终到达一个Page,这个Page里存放的都是叶子节点。

  2
在Page内从”Infimum”节点开始遍历单链表(这种遍历往往会被优化),如果找到该键则成功返回。如果记录到达了”supremum”,说明当前Page里没有合适的键,这时要借助Page的Next
Page指针,跳转到下一个Page继续从”Infimum”开始逐个查找。

必赢365net手机版 38

  详细看下不同类型的Record里到底存储了什么数据,根据B+树节点的不同,User
Record可以被分成四种格式,下图种按照颜色予以区分。

1 主索引树非叶节点(绿色)

  1 子节点存储的主键里最小的值(Min Cluster Key on
Child),这是B+树必须的,作用是在一个Page里定位到具体的记录的位置。

  2 最小的值所在的Page的编号(Child Page Number),作用是定位Record。

2 主索引树叶子节点(黄色)

  1 主键(Cluster Key Fields),B+树必须的,也是数据行的一部分

  2 除去主键以外的所有列(Non-Key
Fields),这是数据行的除去主键的其他所有列的集合。

  这里的1和2两部分加起来就是一个完整的数据行。

3 辅助索引树非叶节点非(蓝色)

  1 子节点里存储的辅助键值里的最小的值(Min Secondary-Key on
Child),这是B+树必须的,作用是在一个Page里定位到具体的记录的位置。

  2 主键值(Cluster Key
Fields),非叶子节点为什么要存储主键呢?因为辅助索引是可以不唯一的,但是B+树要求键的值必须唯一,所以这里把辅助键的值和主键的值合并起来作为在B+树中的真正键值,保证了唯一性。但是这也导致在辅助索引B+树中非叶节点反而比叶子节点多了4个字节。(即下图中蓝色节点反而比红色多了4字节)

  3 最小的值所在的Page的编号(Child Page Number),作用是定位Record。

4 辅助索引树叶子节点(红色)

  1 辅助索引键值(Secondary Key Fields),这是B+树必须的。

  2 主键值(Cluster Key
Fields),用来在主索引树里再做一次B+树检索来找到整条记录。

必赢365net手机版 39

  下面是本篇最重要的部分了,结合B+树的结构和前面介绍的4种Record的内容,我们终于可以画出一幅全景图。由于辅助索引的B+树与主键索引有相似的结构,这里只画出了主键索引树的结构图,只包含了”主键非叶节点”和”主键叶子节点”两种节点,也就是上图的的绿色和黄色的部分。

必赢365net手机版 40

  把上图还原成下面这个更简洁的树形示意图,这就是B+树的一部分。注意Page和B+树节点之间并没有一一对应的关系,Page只是作为一个Record的保存容器,它存在的目的是便于对磁盘空间进行批量管理,上图中的编号为47的Page在树形结构上就被拆分成了两个独立节点。

必赢365net手机版 41

Leave a Comment.