叫大叔 发表于 2023-4-6 17:11:28

深入理解MySQL索引底层数据结构

1 引言

在日常工作中,我们会遇见一些慢SQL,在分析这些慢SQL时,我们通常会看下SQL的执行计划,验证SQL执行过程中有没有走索引。通常我们会调整一些查询条件,增加必要的索引,SQL执行效率就会提升几个数量级。我们有没有思考过,为什么加了索引就会能提高SQL的查询效率,为什么有时候加了索引SQL执行反而会没有变化,本文就从MySQL索引的底层数据结构和算法来进行详细分析。
2 索引数据结构对比

索引的定义:索引(Index)是帮助MySQL高效获取数据的排好序的数据结构。
索引中常见的数据结构有以下几种:

[*]Hash表
[*]二叉树
[*]红黑树
[*]B-Tree
[*]B+Tree
Hash表
通过索引的key进行一次hash计算,就可以快速获取磁盘文件指针,对于指定索引查找文件非常快,但是对于范围查找没法支持,有时候也会出现Hash冲突的情况。

二叉树
二叉树的特点:左边子节点的数据小于父节点数据,右边子节点的数据大于父节点数据。如下图所示,如果col2是索引,查找索引为65的行元素,只需要查找两次,就可以获取到行元素所在的磁盘指针地址。

但如果是一个按照顺序递增的值,例如为col1建立索引,不再适合使用二叉树建立索引,因为此时使用二叉树建立索引将会变成一个链式索引,此时的索引结构如下图所示,如果查找6节点需要6次遍历才能找到。

红黑树
红黑树是一种二叉平衡树,可以提高查询效率,此时若再查找6节点只需要遍历3次就能找到了。但红黑树也有缺点,当存储大数据量时,树的高度就会变的不可控, 数量越大,树的高度越高,查询的效率将会大大降低。

B-Tree
B-Tree是一种多路二叉树,所具有的特点:1 叶节点具有相同的深度,叶节点的指针为空;2 所有索引元素不重复;3 节点中的数据索引从左到右递增排列。

B+Tree
B+Tree是B-Tree的变种,所具有的特点:1 非叶子节点不存储data,只存储索引(冗余),可以放更多的索引;2 叶子节点包含所有索引字段;3 叶子节点用指针连接,提高区间访问的性能。

与红黑树相比,B-Tree和B+Tree两种数据结构都更加矮胖,存储相同数量级的索引数据时,层级更低。
B-Tree和B+Tree之间一个很大的不同,是B+Tree的节点上不储存value,只储存key,而叶子节点上储存了所有key-value集合,并且节点之间都是有序的。这样的好处是每一次磁盘IO能够读取的节点更多,也就是树的度(Max.Degree)可以设置的更大一些,因为每次磁盘IO读取的磁盘页数是一定的。例如,每次磁盘IO能够读取1页=4kb,那么省去value的情况下同样一页数据能够读取更多的key,这样就大大减少了磁盘的IO次数。

此外,B+Tree也是排好序的数据结构,数据库中>
页: [1]
查看完整版本: 深入理解MySQL索引底层数据结构