B+树的叶子节点到底是双向链表还是单向链表

May 14, 2023

前言 #

刚使用mysql的前几年，没有深入地了解mysql的内部实现，关于B+树的叶子节点的了解仅仅是：B+树的叶子节点按照自增id的大小自左至右排序，新增的元素排在右边。 后来突然某一天在网上看到一篇文章，说B+树的叶子节点是双向链表，这让我很是疑惑，因为我一直以为B+树的叶子节点是单向链表，这篇文章是不是写错了呢？然而这片 文章也仅仅是提了一句，并没有详细论述，当时我也没有深入研究，只是在心里泛起疑问：如果是单向链表，那平时业务中经常有按主键id或者时间排序，把最新的排在最前面，是怎么回事？。 后来随着对mysql的深入学习，发现B+树的叶子节点其实是双向链表+单向链表，这篇文章就是为了解答这个疑问。

想要讲明白这个问题，必须要先了解InnoDB的页(Page)的结构，以及InnoDB的B+树的结构。下面简要介绍一下。

Innodb的页(Page) #

Innodb的页(Page)是存储数据的最小单位，页的大小默认为16KB。页的结构如下图所示： 其中的File Header中，有两个字段与本文有关：

• FILE_PAGE_PREV：上一个页的页号。
• FILE_PAGE_NEXT：下一个页的页号。

这里的页号，我们可以把它看成是双向链表中的指针。

其中记录的格式如下图所示(Compact)： 其中头信息中包含的主要字段为：

• deleted_flag：删除标志位，标识该记录是否被删除。
• next_record：下一个记录的偏移量。
• record_type: 记录类型，0表示普通记录，1表示目录项记录，2表示最小记录，3表示最大记录。

我们这里只是简要介绍一下Innodb的页(Page)的结构，并未列出所有的字段。

Innodb的B+树 #

Innodb的B+树的结构如下图所示： 当根据条件搜索某条记录时，Innodb会先从根节点开始，根据条件找到对应的叶子节点，然后再在叶子节点中找到对应的记录。

mysql8.0中，增加了desending index，这里先不讨论。等改天有空再单独写一篇文章。

总结 #

所以，B+树的叶子节点是双向链表+单向链表。innodb的B+树的叶子节点是页(Page)，页之间是双向链表，页内部有一个单向链表，这个单向链表是用来存储记录的。