前言
问题：MySQL的索引B+树叶子节点上的数据记录是通过单向链表还是双向链表组织起来的？
本文的观点是基于MySQL使用Innodb存储引擎的情况下进行的！ 很多渠道说：MySQL数据按照主键大小依次排列，记录之间是双向链表连起来。如果说我告诉你这种说法很大程度上是错的，你肯定说我在胡扯。
正文
我们先看看MySQL的B+树索引结构是什么样的
是的，这种图和网上的很多图都是类似的，我们可以看到每个节点上会有多个记录或者数据，MySQL使用Innob引擎时，这个节点就代表的是Innodb页，Innodb页是最小的存储单元。
通过上图或者你以前就知道，一个Innodb页存储很多条数据。 但是Innodb页可不只有数据记录，还会有其他数据
同样每条记录也不单单只有数据本身，还包含其他额外的数据，我的上篇文章有这么一幅图
其中额外信息中，有记录头信息部分，这部分到底长什么样呢
记录头占 5 个字节，40 位，下图是对应代表的含义
1-2 位：预留，可以无视
3 位：在记录刚被删除时，不是马上删掉，而是将其标记为已删除，实际还在占用空间
4 位：最小目录项标记，B+树是非叶子节点（每个节点是一个 Innodb 页）内，最小目录项标记
5-8 位：成员数量，Innodb 中，所有的记录间不是无关的，也是要再次分组的，这里表示一个组的组长。举个栗子，一个 Innodb 页好比军队的一个排长，下面每个班长都带个袖标，袖标上是班的人数
9-21 位：相对位置，表示本记录在 Innodb 里的相对位置，可以简单的认为（不准确）在一个页里的第几条记录
22-24 位：记录类型，一般记录类型为普通类型，值为 0
25-40 位：下一条记录的相对位置，是指本记录距离下一条记录开头的真实位置，比如说，这里值为 64，就是从当前记录真实记录地址往后走 64 个字节，就是下一条记录的真实数据
这里我们着重看一下下条记录的相对位置部分： 什么是相对位置呢？简要回答就是我离你有多远，而不是起点离你有多远。 放在MySQL里代表记录之间的距离。
下面我们借助另一张图看一下，看一下Innodb页中记录之间是怎么存储的
上图中我们看到，记录之间是亲密无间的排列的。 那我们怎么找下一条记录呢，还是看上面的出现的一张图，里面的下条记录的相对位置
比如，记录1的中下条记录的相对位置为38，意味着从记录1的真实数据开始往后找38个字节就是下一条记录的真实数据的开始。如果记录1的下条记录的相对位置是-38，代表从记录1的真实数据部分往前找38个字节就是下一条记录的真实数据部分。
如果你了解数据结构，你一定明白，这特么就是链表啊！ 是的，Innodb页中的数据之间，是通过单向链表来实现的。
但是，Innodb页之间是双向链表关联的。
一个Innodb页中的文件头中有这么两个属性：上一页的页号、下一页的页号
所以MySQL叶子节点之间是通过双向链表完成的。
总结：
Mysql中记录间既有单向链表，又有双向链表！
作者：阿牛
原文地址：https://www.kuya123.com/2021/07/mysql-innodb
