当前位置： 首页 > news >正文

CMU-15445(6)——PROJECT#2-BPlusTree-Task#1

news 2025/7/3 19:04:38

PROJECT#2-B+Tree

在 PROJECT#2 中，我们需要实现一个B plus Tree，用过 MySQL 的同学肯定对它不陌生，B+Tree是实现高效数据检索的核心组件，其内部节点的作用是引导搜索过程，而实际的数据项则存于叶子节点中。该索引结构能够实现快速的数据检索，无需对数据库表中的每一行数据进行扫描，可实现快速随机查找以及对有序记录的高效扫描。

举个例子，如果我们要用某个给定的 id 来检索某个货物的记录，没有索引结构的情况下，我们只能从第一条记录开始遍历每个货物的记录，直到找到某个ID和我们给定的ID一致的记录，时间复杂度是O(N)。常见的索引结构有二叉树、红黑树、哈希表和B+Tree，而如果我们维护了一个以ID为KEY的索引结构，我们可以通过这个索引结构查询这个ID对应的货物所在的位置，然后直接从这个位置读取数据，B+Tree能保证 O (log n) 时间复杂度的检索操作。

在着手项目开发前，建议先系统学习 B + 树数据结构的核心原理，预先夯实知识基础。

B+Tree

DB 的数据一般保存在磁盘上，这样的好处是持久化，但也有很大的缺点：读写特别慢。

磁盘读写的最小单位是扇区，扇区的大小只有 512B 大小，操作系统一次会读写多个扇区，所以操作系统的最小读写单位是块(Block)。Linux 中的块（页）大小为 4KB ，也就是一次磁盘 I/0 操作会直接读写8个扇区。

由于数据库的索引是保存到磁盘上的，因此当我们通过索引查找某行数据的时候，就需要先从磁盘读取索引到内存，再通过索引从磁盘中找到某行数据，然后读入到内存，也就是说查询过程中会发生多次磁盘//O，而磁盘 I/0 次数越多，所消耗的时间也就越大（如果没有索引结构，那么就需要从头开始将每一行数据的索引从磁盘读到内存和目标索引进行对比，I/O次数会特别多）。

所以，我们希望索引的数据结构能在尽可能少的磁盘的 1/0 操作中完成查询工作，因为磁盘 I/0 操作越少，所消耗的时间也就越小。

因此，一个合格的数据结构需要满足以下要求：

  • 能在尽可能少的磁盘的 /O 操作中完成查询工作；
  • 要能高效地查询某一个记录，也要能高效地执行范围查找;

如果可以将索引按顺序（增序或降序），那么可以通过二分查找来降低查询时间复杂度到O(logN)，进一步优化到二分查找树、自平衡二叉树、B树…，这一部分内容可参考文章：

>>>为什么 MySQL 采用 B+ 树作为索引？ | 小林coding<<<

索引结构的迭代优化总结起来其实就是以下内容：

在数据结构的索引场景中，若将索引存储于数组结构，线性查找的时间复杂度为 O (N)，而采用二分查找可将复杂度降至 O (logN)。尽管数组的线性存储方式实现简单，但插入操作需移动后续所有元素，导致 O (N) 级的时间开销。由此引出二叉树结构，其通过指针链接节点实现非连续存储，兼具二分查找特性，但当二叉搜索树退化为单支树（如全右子树或全左子树）时，时间复杂度会退化为 O (N)。

为解决此类平衡性问题，AVL 树与红黑树等平衡二叉搜索树应运而生。然而，无论何种平衡树结构，其树高仍随数据量呈 O (logN) 增长，这直接导致磁盘 I/O 次数随树高增加而显著上升。B 树的出现通过提升节点扇出能力（单个节点可包含多个子节点）有效降低树高，但传统 B 树节点存储索引与数据记录的复合信息，当用户数据记录尺寸远大于索引键时，会引发两大问题：

  1. 非目标节点的数据记录加载会消耗额外 I/O 资源；
  2. 无效数据占用内存空间，降低缓存命中率。

B+树其实就是B树的升级，MySQL 中索引的数据结构就是采用了 B+ 树，B+ 树结构如下图：

在这里插入图片描述

图片来源：https://xiaolincoding.com/mysql/index/why_index_chose_bpuls_tree.html#%E4%BB%80%E4%B9%88%E6%98%AF-b-%E6%A0%91-2

B+ 树与 B 树差异的点，主要是以下这几点：

  • 叶子节点（最底部的节点）才会存放实际数据（索引+记录），非叶子节点只会存放索引；
  • 所有索引都会在叶子节点出现，叶子节点之间构成一个有序链表；
  • 非叶子节点的索引也会同时存在在子节点中，并且是在子节点中所有索引的最大（或最小）。
  • 非叶子节点中有多少个子节点，就有多少个索引；

如下图所示（课程ppt示例图）：
在这里插入图片描述

所有数据均保存至叶子结点 Leaf Nodes；内部节点 Inner Node 仅仅充当控制查找记录的媒介，并不代表数据本身，所有的内部结点元素都同时存在于子结点中，是子节点元素中是最大（或最小）元素。

如上图，5 是其子结点的最大值， 9 是其子结点的最小值，所有的数据 [1,3,6,7,9,13...] 均保存至叶子结点中，而根结点 [5,9]均不是数据本身，只是充当控制查找记录的媒介。

总而言之，一个完整的 B+ 树由根节点、内部节点、叶子节点三部分组成。每个节点均有键（key）和值（value）组成，区别在于内部节点的值指向子节点的指针（通常是页 ID，用于导航到下一层节点），而叶节点的值指向实际数据记录的引用（通常是 RID，用于定位存储在磁盘上的完整元组）。每个节点通常对应数据库缓冲池中的一个物理页面，通过唯一的页 ID标识。

内部节点的结构如下图所示：

  1. 每个内部节 Inner Nodes 点都由 [P,K] 组成，P指向子树根结点的指针；K 表示关键字值，也就是索引。

  2. 内部节点的关键字值有如下规律：
    K 1 < K 2 < … < K c − 1 K₁<K₂<…<K_{c-1} K1​<K2​<…<Kc−1​

在这里插入图片描述

叶子节点的结构如下图所示：

  1. 叶子节点的值指向磁盘中的某块数据地址；
  2. 存在指针 P_next 指向下一个叶子节点，方便遍历查询。

在这里插入图片描述

关于 B+ 树的插入、删除可参考文章：B+树看这一篇就够了（B+树查找、插入、删除全上） - 知乎

参考：为什么 MySQL 采用 B+ 树作为索引？ | 小林coding

TASK#1-B+Tree Pages

了解完 B+ 树的基础知识后，便可以着手实现 TASK#1。

我们现在很清楚一个完整的 B+ 树由根节点、内部节点和叶子节点三部分组成，其实三者都是同一类型，只不过根据位置不同，不同节点存储的数据对象不同。

在 Project 中，B+ 树所有节点都以 B+Tree Page 的形式存在，根据节点类型不同，又分为 B+Tree Internal Page 和 B+Tree Leaf Page，二者均继承自 B+Tree Page，区别只在于二者存储的数据类型不同：

  1. B+Tree Internal Page 的 Value 为子树根节点的索引；
  2. B+Tree Leaf Page 的 Value 为元组 RID。

本节的目的就是实现以下三个页：

  • B+Tree Page
  • B+Tree Internal Page
  • B+Tree Leaf Page

Base-Tree

需要修改的文件：

  • src/include/storage/page/b_plus_tree_page.h
  • src/storage/page/b_plus_tree_page.cpp

文件中的抽象类 BPlusTreePage 是B+树所有节点类型的公共抽象，包含了内部节点和叶节点共享的核心属性和方法，我们实现的函数多数是 Get/Set，因此比较简单。

因为内部节点和叶子节点都是 BPlusTreePage 的派生，因此每个 B + 树页面的起始位置都包含了三元素：PageType (4) | CurrentSize (4) | MaxSize (4)，分别代表：

  • PageType：4 字节，标识页面类型
  • CurrentSize：4 字节，当前页面中的键值对数量
  • MaxSize：4 字节，页面可容纳的最大键值对数量

一共 12B 的不包含键值对的信息被称为 HEADER，分别对应 BPlusTreePage 的成员变量：

private:// Member variables, attributes that both internal and leaf page shareIndexPageType page_type_ __attribute__((__unused__));// Number of key & value pairs in a pageint size_ __attribute__((__unused__));// Max number of key & value pairs in a pageint max_size_ __attribute__((__unused__));

其中，IndexPageType 是定义的枚举类：

enum class IndexPageType { INVALID_INDEX_PAGE = 0, LEAF_PAGE, INTERNAL_PAGE };
  • INVALID_INDEX_PAGE = 0：无效页面（初始状态或已释放的页面）
  • LEAF_PAGE：叶子节点页面（存储实际数据记录的引用）
  • INTERNAL_PAGE：内部节点页面（存储索引键和子节点指针）

此外，尽管这里 B+ 树的所有节点均以 B+Tree Page 的形式存在，但和 lab1 的 Page 是有本质上的区别，BPlusTreePage 实际对应BPM 中 Page 对象的 data_ 存储区域。因此在读取或写入节点时，首先需要通过 BPM.CheckedReadPage(page_id) 获取受保护可读的 std::optional<ReadPageGuard> 对象（获取可写对象也如此），再将其 data_ 部分 reinterpret_cast 为 BPlusTreePage，最后根据对应的 page_type_ 强转为 Internal/Leaf page，然后在读取或写入后取消固定该页面。具体数据排布如下图所示：

在这里插入图片描述

实现整体比较简单，需要注意的只有GetMinSize() ，对于内部节点和叶子节点，最小大小有不同的计算方式。

最大键值对数量为 N 时，节点的最少键值对数量存在三种情况：

  • 根节点：
    • 根节点是叶节点时，内部至少需要 1 个键值对，这个很好理解，空树插入首个元素时，根节点必须至少有 1 个键值对（如初始插入场景）
    • 根节点是内部节点时，内部至少需要 2 个键值对，因为内部节点需指向至少 2 个子节点（左子树和右子树），因此至少需要 1 个有效键（实际用于索引查询的键值对） + 1 个哨兵键（内部节点最左侧的无效键）
  • 内部节点：节点插入数据之后可能溢出，这时需要进行分裂操作，为了简化分裂代码的编写，内部节点和根节点会留出一个键值对的位置作为哨兵，实际最大键值对数量为 N−1，加上最左侧的无效键，最小键值对数量为 ⌈(N−2)/2⌉+1；
    • (N−2)：减去哨兵键和 1 个分裂键
    • 加 1 是因为哨兵键必须保留在左子树
  • 叶节点：最小键值对数量为 ⌈(N−1)/2⌉，因为叶节点无需哨兵键，最大有效键值对为 N−1（留出 1 个空位用于分裂）

Internal Page

需要修改的文件：

  • src/include/storage/page/b_plus_tree_internal_page.h
  • src/storage/page/b_plus_tree_internal_page.cpp

B+ 树和 B 树最大的区别就是 B+ 树的内部节点存储的是索引信息而不是数据，且 m 个 key 对应 m+1 个 child，这种设计使得每个键成为两个相邻子树的分隔符，如下图所示：

在这里插入图片描述

由于 child 的数量不等于 key 的数量，因此将第一个键设置为无效（key_array_[0] = KeyType()），并且查找方法应始终从第二个键开始，简单来说就是牺牲空间获取效率，举个例子说明：

在这里插入图片描述

假如存在 key_array_ = [5，10，20，30]，且 key_array_[0] 有效，则 child 的含义变为：

  • P0指向<5的键（但B+树根节点的最小键是整个 B + 树中所有键的最小值，在左子树中不存在比5小的键，因此这个区间为空）
  • P1指向[5,10)的键
  • P2指向[10,20)的键
  • P3指向[20,30)的键
  • 还需额外的子指针指向≥30的键（但数组已无空间）

因为子指针page_id_array_[i]指向的子树包含键值范围：[key_array_[i], key_array_[i+1])，若key_array_[0]存储有效键，查找最左侧子树时需特殊处理，因为不存在小于 key_array_[0] 的区间，所以左子树只能通过判断是否小于 key_array_[1] ：

// 假设key_array_[0]有效，查找最左侧子树的代码
if (key < key_array_[1]) {return page_id_array_[0]; 
}

正常我们希望的判断逻辑为：

// 实际查找逻辑（从key_array_[1]开始）
int index = 1;
while (index < GetSize() && key >= key_array_[index]) {index++;
}
return page_id_array_[index-1];  // 无需特殊处理最左侧子树

P0指向的区间永远为空，浪费一个子指针位置，且4 个键需要 5 个子指针，但数组只有 4 个位置。因此有必要将 key_array_[0] 无效。

在这里插入图片描述

key_array_[0] 无效时， child 的含义变为：

  • 子指针P0指向<10的所有键
  • 子指针P1指向[10,20)的所有键
  • 子指针P2指向[20,30)的所有键
  • 子指针P3指向≥30的所有键
    在这里插入图片描述

特别注意，宏 INTERNAL_PAGE_SLOT_CNT 表示 B + 树内部页面最多能存储的键值对数量

\#define INTERNAL_PAGE_SLOT_CNT \
((BUSTUB_PAGE_SIZE - INTERNAL_PAGE_HEADER_SIZE) / ((int)(sizeof(KeyType) + sizeof(ValueType))))  // NOLINT

一个页通常为 4KB，HEADER占据 12B，最大键对值数量取决于键值对占用空间，假如 sizeof(int) + sizeof(int) = 4 + 4 = 8 字节，那么一个页能存储的键值对数量为 (4096 - 12) / (4 + 4) = 510.5 → 向下取整为 510。

因此，每个内部页面实际最多存储 510 个键和 511 个子指针（因首个键无效），理论上可容纳 510 个有效键，实际最大有效键数量为 509（因需预留一个位置用于分裂）；最小有效键数量 = ⌈510/2⌉ - 1 = 255 - 1 = 254，当页面键数量降至 254 以下时，可能触发与兄弟节点的合并，当页面键数量达到 510 时，插入操作将触发分裂。

内部节点页的结构如下图所示，它比父类多了一个 array 数组成员，用于存放 key | page_id 键值对，其中 page_id 是子节点的页 id：

在这里插入图片描述

在这里插入图片描述

函数实现比较简单不过多赘述，需要注意的只有 KeyAt() 和 SetKeyAt() 在实现时，需要设置边界，禁止访问 index=0 的无效键；而 ValueAt() 可以访问 index=0 的子指针。

Leaf Page

需要修改的文件：

  • src/include/storage/page/b_plus_tree_leaf_page.h
  • src/storage/page/b_plus_tree_leaf_page.cpp

和内部节点不同，叶子节点存储 m 个有序键及其对应的 m 个值，值的类型的 64 位的 RID（指向数据记录的物理位置），并且在 header 区域多了一个 NextPageId 字段，该字段是下一个叶节点的指针，用于将叶节点串成单向链表。

叶子节点的页面结构如下图：

在这里插入图片描述

函数实现很简单，不过多赘述。

在这里插入图片描述

一个完整的B+Tree结构如下所示：
在这里插入图片描述

图片来源：https://www.cnblogs.com/zhiyiYo/p/17472784.html

test

TASK#1 没有测试，完成 TASK#2 后进行。

http://www.lqws.cn/news/602371.html

相关文章：

  • 记一次Ubuntu22安装MongoDB8并同步本地数据过程
  • 应急响应类题练习——玄机第四章 windows实战-emlog
  • 微信小程序使用秋云ucharts echarts
  • 高阶数据结构------并查集
  • 数据结构day7——文件IO
  • STM32——存储器映射（Memory mapping）
  • 反向传播 梯度消失
  • OSE3.【Linux】练习:编写进度条及pv命令项目中的进度条函数
  • 07CSRF 漏洞保护
  • vite项目中引入tailwindcss，难倒AI的操作
  • Modbus协议
  • 数字图像处理学习笔记
  • Spring IOC容器核心阶段解密：★Bean实例化全流程深度剖析★
  • 菜谱大全——字符串处理艺术：从文本解析到高效搜索 [特殊字符][特殊字符]
  • 城市灯光夜景人像街拍摄影后期Lr调色教程，手机滤镜PS+Lightroom预设下载！
  • 自由学习记录（66）
  • RESTful API 设计原则深度解析
  • 转录组分析流程(六)：列线图
  • 笨方法学python-习题12
  • JavaScript 安装使用教程
  • 解码知识整理，使您的研究更高效！
  • 分区表设计：历史数据归档与查询加速
  • [论文阅读] 人工智能 + 软件工程 | 从软件工程视角看大语言模型：挑战与未来之路
  • python训练day46 通道注意力
  • 2025-0701学习记录19——“问题-方法-洞见”框架做汇报
  • 半导体和PN结
  • socket编程
  • Android11 添加自定义物理按键事件监听回调
  • Vite 7.0 与 Vue 3.5：前端开发的性能革命与功能升级
  • 【Linux】进程