MySQL记录之间是单向链表还是双向链表?

程序员阿牛
2021-07-11 / 0 评论 / 348 阅读
温馨提示:
本文最后更新于2021-07-11,若内容或图片失效,请留言反馈。

前言

本文的观点是基于MySQL使用Innodb存储引擎的情况下进行的!

很多渠道说:MySQL数据按照主键大小依次排列,记录之间是双向链表连起来。如果说我告诉你这种说法很大程度上是错的,你肯定说我在胡扯。

正文

我们先看看MySQL的B+树索引结构是什么样的
image.png

是的,这种图和网上的很多图都是类似的,我们可以看到每个节点上会有多个记录或者数据,MySQL使用Innob引擎时,这个节点就代表的是Innodb页,Innodb页是最小的存储单元。

通过上图或者你以前就知道,一个Innodb页存储很多条数据。但是Innodb页可不只有数据记录,还会有其他数据。
image.png
上图就是Innodb页的结构图

同样每条记录也不单单只有数据本身,还包含其他额外的数据,我的上篇文章有这么一幅图

image.png

其中额外信息中,有记录头信息部分,这部分到底长什么样呢

记录头占 5 个字节,40 位,下图是对应代表的含义

image.png

  • 1-2 位:预留,可以无视
  • 3 位:在记录刚被删除时,不是马上删掉,而是将其标记为已删除,实际还在占用空间
  • 4 位:最小目录项标记,B+树是非叶子节点(每个节点是一个 Innodb 页)内,最小目录项标记
  • 5-8 位:成员数量,Innodb 中,所有的记录间不是无关的,也是要再次分组的,这里表示一个组的组长。举个栗子,一个 Innodb 页好比军队的一个排长,下面每个班长都带个袖标,袖标上是班的人数
  • 9-21 位:相对位置,表示本记录在 Innodb 里的相对位置,可以简单的认为(不准确)在一个页里的第几条记录
  • 22-24 位:记录类型,一般记录类型为普通类型,值为 0
  • 25-40 位:下一条记录的相对位置,是指本记录距离下一条记录开头的真实位置,比如说,这里值为 64,就是从当前记录真实记录地址往后走 64 个字节,就是下一条记录的真实数据
    这里我们着重看一下下条记录的相对位置部分:什么是相对位置呢?简要回答就是我离你有多远,而不是起点离你有多远。放在MySQL里代表记录之间的距离。

下面我们借助另一张图看一下,看一下Innodb页中记录之间是怎么存储的

image.png

上图中我们看到,记录之间是亲密无间的排列的。那我们怎么找下一条记录呢,还是看上面的出现的一张图,里面的下条记录的相对位置

image.png

比如,记录1的中下条记录的相对位置为38,意味着从记录1的真实数据开始往后找38个字节就是下一条记录的真实数据的开始。如果记录1的下条记录的相对位置是-38,代表从记录1的真实数据部分往前找38个字节就是下一条记录的真实数据部分。

如果你了解数据结构,你一定明白,这特么就是链表啊!是的,Innodb页中的数据之间,是通过单向链表来实现的。

但是,Innodb页之间是双向链表关联的。
image.png

一个Innodb页中的文件头中有这么两个属性:上一页的页号、下一页的页号

image.png

所以MySQL叶子节点之间是通过双向链表完成的。

因此:记录间可以说是既有单向链表又有双线链表。

关注站长公众号:
gzh