logo

B+ 树

B+ 树是 1970 年由 Rudolf Bayer 教授在《Organization and Maintenance of Large Ordered Indices》一文中提出的,此后迅速成为海量数据存储与检索的重要工具。以查询为主要场景的关系型数据库,无一例外地选择了 B+ 树。

B+ 树的基本思想

B+ 树是一种平衡多路查找树,其灵感源自平衡二叉树和 B 树,但专为速度较慢的“外存”设计,因此具有独特的设计方向:

尽量减少数据不断增长时的磁盘 I/O 数量,包括插入新数据场景和查询场景。

它将经典平衡二叉树的“再平衡”过程颠倒过来了——最底层的叶子节点紧密排列,新增数据时不断添加新的叶子节点,需要再平衡的不是叶子节点,而是上面的索引页。而索引页具有以下特点:

  1. 索引页数量少
  2. 再平衡时,B+ 树算法调整的索引节点数量也很少
  3. 索引容量足够大:3 层索引可承载 2000 万行数据,4 层索引可承载 200 多亿行
  4. 索引页少,可以将所有索引全部载入内存,读取索引的磁盘 I/O 趋近于 0

InnoDB 是如何组织数据的

下面我们来具体认识一下 InnoDB 中的索引和数据是怎么利用 B+ 树思想在磁盘上进行组织的。

1. 页

页是 MySQL 中数据存储的基本单元,整颗 B+ 树就是一个又一个相互使用指针连接在一起的页组成的。由于 InnoDB 出现的时候,SSD 还没有出现,所以它是为了机械磁盘及其 512 字节的扇区而设计的,所以页块的默认大小被设置为了 16KB(32 个连续扇区)。

图 8-1 三层索引下的页结构图(35 行数据)

图 8-1 展示出了页之间的指针关系:

  1. 上层页对下层页拥有单向指针
  2. 同一层内相邻的页之间拥有双向指针,无论是上面的索引页层还是底层的数据页层
  3. 最底层数据页层中,每一页可以存储多行数据,每一行数据拥有指向下一行的单向指针

而在物理层面,每一页的内部结构都如图 8-2 所示。

图 8-2 InnoDB 索引页的内部结构

2. 索引页里面有什么

图 8-3 二层索引下的页结构图(15 行数据)

我们用更清晰的二层索引簇结构来展示索引页包含的关键信息,如图 8-3 所示。顶部那个彩色的页就是索引页。

除了头部和尾部的基础信息字段之外,索引页的“用户存储数据”紧密排列着指向下一层页的指针,结构为:id|页号

这里的 id 就是这张表默认主键的那个 id,一般为int(4 字节)或者bigint(8 字节)。该数字的含义是:

该页号对应的页,以及下挂的所有页,所拥有的全部数据行中,id 最小的那行数据的 id。

InnoDB 使用这个数字可以快速定位某一行数据所处的页的位置。

页号就是页的编号,在不同版本的 MySQL 上这个页编号的长度是不一样的,下面我们会通过测试来确定 MySQL 8.0 中页编号的长度。

3. 数据页里面有什么

B+ 树上层的所有页只存储索引,只用最底层的页存储数据。这是 B+ 比 B 树优秀的地方:以一丢丢写入速度为代价,让较少的索引层数内存下了更多的索引指针,可以支撑海量的数据行数。

图 8-4 数据页内部结构

如图 8-4 所示,数据页内部是分槽的,相当于自己又加了一层索引。数据页内部拥有最小记录指针和最大纪录指针,有没有觉得一花一世界,数据页内部结构和 B+ 树颇有几分神似呢?

SQL 查询过程

有了前面的铺垫,真正的 SQL 查询过程就呼之欲出了。假设我们要找出id=6的一行数据,则我们执行的 SQL 为 select * from users where id=6。我们还怎么找出这一行数据呢?只需要逐层比对即可:

  1. 将顶部页(16KB)的数据读入内存,将 6 与每个id|页号进行大小对比,找到 6 所在的页:大于等于当前 id 且小于右侧邻居的 id
  2. 将上一步找到的那一页数据读入内存,重复上述比对操作,直到找到最底层的数据页
  3. 将数据页读入内存,找出id=6索引下挂载的全部数据,这就是所需的这行数据

阅读数:26      字数:1410 最后更新:2023-10-26 10:27:31