第1个回答 2022-06-14
问题：MySQL的索引B+树叶子节点上的数据记录是通过单向链表还是双向链表组织起来的？
本文的观点是基于MySQL使用Innodb存储引擎的情况下进行的！ 很多渠道说：MySQL数据按照主键大小依次排列，记录之间是双向链表连起来。如果说我告诉你这种说法很大程度上是错的，你肯定说我在胡扯。
我们先看看MySQL的B+树索引结构是什么样的
是的，这种图和网上的很多图都是类似的，我们可以看到每个节点上会有多个记录或者数据，MySQL使用Innob引擎时，这个节点就代表的是Innodb页，Innodb页是最小的存储单元。
通过上图或者你以前就知道，一个Innodb页存储很多条数据。 但是Innodb页可不只有数据记录，还会有其他数据
同样每条记录也不单单只有数据本身，还包含其他额外的数据，我的上篇文章有这么一幅图
其中额外信息中，有记录头信息部分，这部分到底长什么样呢
记录头占 5 个字节，40 位，下图是对应代表的含义
这里我们着重看一下下条记录的相对位置部分： 什么是相对位置呢？简要回答就是我离你有多远，而不是起点离你有多远。 放在MySQL里代表记录之间的距离。
下面我们借助另一张图看一下，看一下Innodb页中记录之间是怎么存储的
上图中我们看到，记录之间是亲密无间的排列的。 那我们怎么找下一条记录呢，还是看上面的出现的一张图，里面的下条记录的相对位置
比如，记录1的中下条记录的相对位置为38，意味着从记录1的真实数据开始往后找38个字节就是下一条记录的真实数据的开始。如果记录1的下条记录的相对位置是-38，代表从记录1的真实数据部分往前找38个字节就是下一条记录的真实数据部分。
如果你了解数据结构，你一定明白，这特么就是链表啊！ 是的，Innodb页中的数据之间，是通过单向链表来实现的。
但是，Innodb页之间是双向链表关联的。
一个Innodb页中的文件头中有这么两个属性：上一页的页号、下一页的页号
所以MySQL叶子节点之间是通过双向链表完成的。
Mysql中记录间既有单向链表，又有双向链表！