首页
关于
留言
接口
搜索
首页
登录
登录
搜索
KAKA 梦很美
累计撰写
47
篇文章
累计收到
0
条评论
首页
栏目
首页
登录
页面
首页
关于
留言
接口
MySQL
2021-8-19
聊聊 MySQL 索引数据结构
前言 当你遇到了一条慢 SQL 需要进行优化时,你第一时间能想到的优化手段是什么? 大部分人第一反应可能都是添加索引,在大多数情况下面,索引能够将一条 SQL 语句的查询效率提高几个数量级。 索引的本质:用于快速查找记录的一种 数据结构 索引的常用数据结构: 二叉树 红黑树 Hash 表 B-TREE (B树,并不叫什么B减树) B+TREE 数据结构图形化: 点击查阅 索引数据结构 大家知道 SELECT * FROM t WHERE col = 88 这么一条 SQL 语句如果不走索引进行查找的话,正常地查就是全表扫描:从表的第一行记录开始逐行找,把每一行的 col 字段的值和 88 进行对比,这明显效率是很低的。 而如果走索引的话,查询的流程就完全不一样了(假设现在用一棵平衡二叉树数据结构存储我们的索引列) 此时该二叉树的存储结构(Key - Value):Key 就是索引字段的数据,Value 就是索引所在行的磁盘文件地址。 当最后找到了 88 的时候,就可以把它的 Value 对应的磁盘文件地址拿出来,然后就直接去磁盘上去找这一行的数据,这时候的速度就会比全表扫描要快很多。 但实际上 MySQL 底层并没有用二叉树来存储索引数据,是用的 B+TREE(B+树) 为什么不采用二叉树 假设此时用普通二叉树记录 id 索引列,我们在每插入一行记录的同时还要维护二叉树索引字段 此时找 id = 7 这一行记录时找了 6 次,和我们全表扫描也没什么很大区别。显而易见,二叉树对于这种依次递增的数据列其实是不适合作为索引的数据结构。 为什么不采用 Hash 表 Hash 表:一个快速搜索的数据结构,搜索的时间复杂度 O(1) Hash 函数:将一个任意类型的 key,可以转换成一个 int 类型的下标 假设此时用 Hash 表记录 id 索引列,我们在每插入一行记录的同时还要维护 Hash 表索引字段。 这时候开始查找 id = 7 的树节点仅找了 1 次,效率非常高了。 但 MySQL 的索引依然不采用能够精准定位的Hash 表。因为它不适用于范围查询 为什么不采用红黑树 红黑树 是一种特化的 AVL树(平衡二叉树),都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡;若一棵二叉查找树是红黑树,则它的任一子树必为红黑树。 假设此时用红黑树记录 id 索引列,我们在每插入一行记录的同时还要维护红黑树索引字段。 插入过程中会发现它与普通二叉树不同的是当一棵树的左右子树高度差 > 1 时,它会进行自旋操作,保持树的平衡。 这时候开始查找 id = 7 的树节点只找了 3 次,比所谓的普通二叉树还是要更快的。 但 MySQL 的索引依然不采用能够精确定位和范围查询都优秀的红黑树。 因为当 MySQL 数据量很大的时候,索引的体积也会很大,可能内存放不下,所以需要从磁盘上进行相关读写,如果树的层级太高,则读写磁盘的次数(I/O交互)就会越多,性能就会越差。 红黑树 目前的唯一不足点就是树的高度不可控,所以现在我们的切入点就是树的高度。 目前一个节点是只分配了一个存储 1 个元素,如果要控制高度,我们就可以把一个节点分配的空间更大一点,让它横向存储多个元素,这个时候高度就可控了。这么个改造过程,就变成了 B-TREE B-TREE 和 B+TREE BTREE 是一颗多路平衡查找树 定义如下 每个节点最多有m-1个关键字(可以存有的键值对) 根节点最少可以只有1个关键字 非根节点至少有m/2个关键字 每个节点中的关键字都按照从小到大的顺序排列,每个关键字的左子树中的所有关键字都小于它,而右子树中的所有关键字都大于它 所有叶子节点都位于同一层,或者说根节点到每个叶子节点的长度都相同 每个节点都存有索引和数据,也就是对应的 Key 和 Value 根节点的关键字数量范围:1 <= k <= m-1,非根节点的关键字数量范围:m/2 <= k <= m-1 B-TREE 的查找其实和二叉树很相似 二叉树是每个节点上有一个关键字和两个分支,B-TREE 上每个节点有 k 个关键字和 (k + 1) 个分支。 二叉树的查找只考虑向左还是向右走,而 B-TREE 中需要由多个分支决定。 B-TREE 的查找分两步 首先查找节点,由于 B-TREE 通常是在磁盘上存储的所以这步需要进行磁盘IO操作 查找关键字,当找到某个节点后将该节点读入内存中然后通过顺序或者折半查找来查找关键字。若没有找到关键字,则需要判断大小来找到合适的分支继续查找 B-TREE 和 B+TREE 的相同点 根节点至少一个元素, 根节点至少有两个节点 每个中间节点都包含k-1个元素和k个孩子,其中m/2<=k<=m 每一个叶子节点都包含k-1个元素,其中m/2<=k<=m 所有的叶子节点都位于同一层 每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域划分 B+TREE 是 BTREE 的变种, 拥有新特性 有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点 所有的叶子节点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子节点本身依关键字的大小自小而大顺序链接 所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素 B+TREE 比 BTREE 的优势 单一节点存储更多的元素,使得查询的IO次数减少 所有查询都要查找到叶子节点,查询性能稳定 所有叶子节点形成有序链表,便于范围查询 我们具体来看一下B+树结构 我们可以直观地看出节点之间含有重复元素,叶子节点还用指针连在了一起,注意: 叶子节点其实还是个双向指针, 图中未体现右到左的指针而已。每个父节点中的元素都出现在了子节点中,是子节点中的最大(或最小)元素 如上图,根节点中元素8是子节点2,5,8的最大元素,也是叶子节点6,8的最大元素,根节点元素15是子节点11,15的最大元素,也是叶子节点13,15的最大元素。需要注意的是,根节点的最大元素(此处是15)等同于整个B+树的最大元素。无论插入或删除多少元素,始终要保持最大元素在根节点当中。至于叶子节点,由于父节点的元素都出现在了子节点,所以叶子节点包含了全部元素信息。并且每个叶子节点都带有指向下一个节点的指针,形成了一个有序链表 B+树还有一个至关重要的特点,那就是”卫星数据“的位置,所谓 ”卫星数据“,指的是索引元素所指向的数据记录(比如数据库中的某一行) 在B树中,无论中间节点还是叶子节点都带有卫星数据 而在B+树中,只有叶子节点带有卫星数据,其余中间节点仅仅是索引,没有任何数据关联 在数据库的聚集索引中,叶子节点直接包含卫星数据,在非聚集索引中,叶子节点带有指向卫星数据的指针 B+树被设计如此,优势主要体现在查询性能上 单元素查询的时候,B+树会自顶向下逐层查找节点,最终找到匹配的叶子节点,比如我们查找元素3 由此看来,B树的范围查询确实有点繁琐,反观B+树的范围查询则简单的多,只需在链表上做遍历即可 如此看来B+树的链表遍历要比B树的中序遍历简单很多
2021年-8月-19日
160 阅读
0 评论
MySQL
2020-12-22
MySQL 之执行计划
什么是执行计划 ? 执行计划,就是一条SQL语句,在数据库中实际执行的时候,一步步的分别都做了什么。也就是我们用EXPLAIN分析一条SQL语句时展示出来的那些信息。 EXPLAIN命令是查看查询优化器是如何决定执行查询的主要方法,从它的查询结果中可以知道一个SQL语句每一步是如何执行的,都经历了些什么,分为哪几步,有没有用到索引,哪些字段用到了什么样的索引,是否有一些可优化的地方等,这些信息都是我们SQL优化的依据。 要使用EXPLAIN,只需在查询中的SELECT关键字之前增加EXPLAIN。语法如下: EXPLAIN SELECT 查询语句 当执行执行计划时,只会返回执行计划中每一步的信息,它会返回一行或多行信息,显示出执行计划中的每一部分和执行的次序, 如: 如果查询的是多个关联表,执行计划结果可能是多行。 接下来涉及到的示例表,均来自于MySQL官方的示例数据库 sakila,点击脚本下载地址 执行计划中的列 EXPLAIN的结果总是有相同的列,每一列代表着不同的含义,可变的只是行数和内容。从上面的例子中,我们看到返回的有很多列,为了更加清楚的了解每一列的含义,便于我们更好的完成优化SQL。 列名 含义 id id列,表示查询中执行select子句或操作表的顺序 select_type 查询类型,主要是用于区分普通查询、联合查询、子查询等复杂的查询 table 表明对应行正在访问的是哪个表 partitions 查询涉及到的分区 type 访问类型,决定如何查找表中的行 possible_keys 查询可以使用哪些索引 key 实际使用的索引,如果为NULL,则没有使用索引 key_len 索引中使用的字节数,查询中使用的索引的长度(最大可能长度),并非实际使用长度,理论上长度越短越好 ref 显示索引的那一列被使用 rows 估算出找到所需行而要读取的行数 filtered 返回结果的行数占读取行数的百分比,值越大越好 Extra 额外信息,但又十分重要 id id列是一个编号,用于标识SELECT查询的序列号,表示执行SQL查询过程中SELECT子句或操作表的顺序。 如果在SQL中没有子查询或关联查询,那么id列都将显示一个1。否则,内层的SELECT语句一般会顺序编号。 id列分为三种情况 1) id 相同 如下普通查询,没有子查询 explain select f.* from film f,film_actor fa,actor a where f.film_id = fa.film_id and fa.actor_id = a.actor_id and a.first_name = 'NICK'; 2) id 不同 如果存在子查询,id的序号会递增,id值越大优先级越高,越先被执行 explain select * from film where film_id = (select film_id from film_actor where actor_id = 2 limit 1); 3) id相同又不同 1), 2) 两种情况同时存在。id如果相同,认为是一组,从上往下执行。在所有组中,id值越大,优先级越高,越先执行。 select_type select_type列表示对应行的查询类型,是简单查询还是复杂查询,主要用于区分普通查询、联合查询、子查询等复杂的查询。 该列有如下值: 值 说明 SIMPLE 简单查询,意味着不包括子查询或UNION PRIMARY 查询中包含任何复杂的子部分,最外层查询则被标记为PRIMARY SUBQUERY 在 select 或 where 列表中包含了子查询 DERIVED 表示包含在 from 子句的子查询中的 select,MySQL会递归执行并将结果放到一个临时表中,称其为“派生表”,因为该临时表是从子查询中派生而来的 UNION 第二个 select 出现在 UNION 之后,则被标记为UNION UNION RESULT 从UNION表获取结果的select table table列表示对应行正在执行的哪张表,指代对应表名,或者该表的别名(如果SQL中定义了别名)。 partitions 查询涉及到的分区。 type type列指代访问类型,是MySQL决定如何查找表中的行。 是SQL查询优化中一个很重要的指标,拥有很多值,依次从最优到最差: system < const < eq_ref < ref < fulltext < ref_or_null < index_merge < unique_subquery < index_subquery < range < index < ALL 1) ALL 众所周知的全表扫描,表示通过扫描整张表来找到匹配的行,很显然这样的方式查询速度很慢。 这种情况,性能最差,在写SQL时尽量避免此种情况的出现。 explain select * from film; 在平时写SQL时,避免使用select *,就不难理解了。换言之,是为了避免全表扫描,因为全面扫描是性能最差的。 2) index 全索引扫描,和全表扫描ALL类似,扫描表时按索引次序进行,而不是按行扫描,即:只遍历索引树。 index与ALL虽然都是读全表,但index是从索引中读取,而ALL是从硬盘读取。显然,index性能上优于ALL,合理的添加索引将有助于性能的提升。 explain select title from film; explain select description from film; 通过 explain 结果来看,只查询表film中字段title时,是按照索引扫描的(type列为index),倘若查询字段description,却是按照全表扫描的(type列为ALL)。这是为何呢? 接下来,我们不妨看看表film的结构 从 desc film 结果来看,字段title创建的有索引,而字段description没有,所以select title from film是按索引扫描,而select description from film按全表扫描。 从上面的举例对比中,也充分印证了索引的重要性。 3) range 只检索给定范围的行,使用一个索引来选择行。key列显示使用了那个索引。一般就是在where语句中出现了bettween、<、>、in等的查询。这种索引列上的范围扫描比全索引扫描index要好。 explain select * from film where film_id between 1 and 10; 4) ref 非唯一性索引扫描,返回匹配某个单独值的所有行。本质是也是一种索引访问,它返回所有匹配某个单独值的行,然而它可能会找到多个符合条件的行,所以它属于查找和扫描的混合体。 此类型只有当使用非唯一索引或者唯一索引的非唯一性前缀时,才会发生。 show index from film; explain select * from film where title = 'ACADEMY DINOSAUR'; 5) eq_ref 唯一索引扫描。常见于主键或唯一索引扫描。 6) const 通过索引一次就能找到,const用于比较primary key 或者unique索引。因为只需匹配一行数据,所有很快。如果将主键置于where列表中,MySQL就能将该查询转换为一个const。 show index from film; explain select * from film where film_id = 1; 7) system 表只有一行记录,这是const类型的特例,比较少见,如:系统表。 possible_keys 显示在查询中使用了哪些索引。 key 实际使用的索引,如果为NULL,则没有使用索引。查询中如果使用了覆盖索引,则该索引仅出现在key列中。 possible_keys列表明哪一个索引有助于更高效的查询,而key列表明实际优化采用了哪一个索引可以更加高效。 show index from film_actor; explain select actor_id,film_id from film_actor; key_len 表示索引中使用的字节数,查询中使用的索的长度(最大可能长度),并非实际使用长度,理论上长度越短越好。key_len是根据表定义计算而得的,不是通过表内检索出的。 ref 表示在key列记录的索引中查找值,所用的列或常量const。 rows 估算出找到所需行而要读取的行数 这个数字是内嵌循环关联计划里的循环数,它并不是最终从表中读取出来的行数,而是MySQL为了找到符合查询的那些行而必须读取行的平均数,只能作为一个相对数来进行衡量。 filtered 返回结果的行数占读取行数的百分比,值越大越好。 select count(1) from film_actor where actor_id = 1; explain select * from film_actor where actor_id = 1; 表film_actor中actor_id为1的记录有19条,而SQL查询时扫描了19行(rows:19),19条符合条件(filtered: 100 19/19) Extra 额外信息,但又十分重要。常见的值如下: 1) Using index 表示SQL中使用了覆盖索引。 show index from film_actor; explain select actor_id, film_id from film_actor; 2) Using where 许多where条件里是涉及索引中的列,当它读取索引时,就能被存储引擎检验,因此不是所有带where子句的查询都会显示“Using where”。 3) Using temporary 对查询结果排序时,使用了一个临时表,常见于order by 和group by。 4) Using filesort 对数据使用了一个外部的索引排序,而不是按照表内的索引进行排序读取。也就是说MySQL无法利用索引完成的排序操作成为“文件排序”。 总结 执行计划,真的很重要,尤其是SQL调优时,很香!
2020年-12月-22日
169 阅读
0 评论
MySQL
2020-2-11
MySQL InnoDB 数据页结构
数据页 在操作系统中,我们知道为了跟磁盘交互,内存也是分页的,一页大小4KB。同样的在 MySQL 中为了提高吞吐率,数据也是分页的,不过 MySQL 的数据页大小是16KB。(确切的说是 InnoDB 数据页大小16KB)。详细学习可以 参考官网 为了详细说明,这里先用图介绍一下页的结构: 而在MySQL内存中,多个这样的数据结构作为节点构成一个双向链表。 Page 结构 从上边的图也可以发现,它描述的是页外部的一些信息,比如上一页\下一页等。 我们重点可以看看 File Header 和 Page Header File Header Page Header 上图为 Page 数据结构,File Header 字段用于记录 Page 的头信息,其中比较重要的是 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 字段,通过这两个字段,我们可以找到该页的上一页和下一页,实际上所有页通过两个字段可以形成一条双向链表。Page Header 字段用于记录 Page 的状态信息。接下来的 Infimum 和 Supremum 是两个伪行记录,Infimum(下确界)记录比该页中任何主键值都要小的值,Supremum (上确界)记录比该页中任何主键值都要大的值,这个伪记录分别构成了页中记录的边界。 User Records 中存放的是实际的数据行记录,具体的行记录结构将在本文的第二节中详细介绍。Free Space 中存放的是空闲空间,被删除的行记录会被记录成空闲空间。Page Directory 记录着与二叉查找相关的信息。File Trailer 存储用于检测数据完整性的校验和等数据。 行记录 Innodb 存储引擎提供了两种格式的行记录:Compact 和 Redundant。 Compact 行记录 变长字段长度列表:逆序记录每一个列的长度,如果列的长度小于 255 字节,则使用一个字节,否则使用 2 个字节。该字段的实际长度取决于列数和每一列的长度,因此是变长的。 NULL 标志位:一个字节,表示该行是否有 NULL 值 记录头信息:五个字节,其中 next_record 记录了下一条记录的相对位置,一个页中的所有记录使用这个字段形成了一条单链表。 列数据部分:除了记录每一列对应的数据外,还有隐藏列,它们分别是 Transaction ID、Roll Pointer 以及 row_id(当没有指定主键)。 注意:此处需要注意固定长度 CHAR 数据类型和变长 VCHAR 数据类型在 Compact 记录下为 NULL 时不占用任何存储空间。 Redundant 行记录 字段长度偏移列表:与 Compact 中的变长字段长度列表相同的是它们都是按照列的逆序顺序设置值的,不同的是字段长度偏移列表记录的是偏移量,每一次都需要加上上一次的偏移,同时对于 CHAR 的 NULL 值,会直接按照最大空间记录,而对于 VCHAR 的 NULL 值不占用任何存储空间。 此处需要注意 VCHAR 类型和 CHAR 类型在建表时传入的参数是字符长度而不是字节长度,实际的字节长度需要跟编码方式相关联,例如 UTF-8 一个中文字符需要 3 字节来表示,这样 CHAR(10) 以 UTF-8 来表示的话,它的字节长度在 10 - 30 之间。 行溢出 我们知道数据页的大小是 16KB,Innodb 存储引擎保证了每一页至少有两条记录,如果一页当中的记录过大,会截取前 768 个字节存入页中,其余的放入 BLOB Page。
2020年-2月-11日
159 阅读
0 评论
MySQL