公需道德与能力建设培训网站,曼联vs恩波利比分,做网站怎么挣钱赚钱,青海住房和建设厅网站PROJECT#2-BTree
在 PROJECT#2 中#xff0c;我们需要实现一个B plus Tree#xff0c;用过 MySQL 的同学肯定对它不陌生#xff0c;BTree是实现高效数据检索的核心组件#xff0c;其内部节点的作用是引导搜索过程#xff0c;而实际的数据项则存于叶子节点中。该索引结构能…PROJECT#2-BTree
在 PROJECT#2 中我们需要实现一个B plus Tree用过 MySQL 的同学肯定对它不陌生BTree是实现高效数据检索的核心组件其内部节点的作用是引导搜索过程而实际的数据项则存于叶子节点中。该索引结构能够实现快速的数据检索无需对数据库表中的每一行数据进行扫描可实现快速随机查找以及对有序记录的高效扫描。
举个例子如果我们要用某个给定的 id 来检索某个货物的记录没有索引结构的情况下我们只能从第一条记录开始遍历每个货物的记录直到找到某个ID和我们给定的ID一致的记录时间复杂度是O(N)。常见的索引结构有二叉树、红黑树、哈希表和BTree而如果我们维护了一个以ID为KEY的索引结构我们可以通过这个索引结构查询这个ID对应的货物所在的位置然后直接从这个位置读取数据BTree能保证 O (log n) 时间复杂度的检索操作。
在着手项目开发前建议先系统学习 B 树数据结构的核心原理预先夯实知识基础。
BTree
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 树节点存储索引与数据记录的复合信息当用户数据记录尺寸远大于索引键时会引发两大问题
非目标节点的数据记录加载会消耗额外 I/O 资源无效数据占用内存空间降低缓存命中率。
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标识。
内部节点的结构如下图所示 每个内部节 Inner Nodes 点都由 [P,K] 组成P指向子树根结点的指针K 表示关键字值也就是索引。 内部节点的关键字值有如下规律 K 1 K 2 … K c − 1 K₁K₂…K_{c-1} K1K2…Kc−1 叶子节点的结构如下图所示
叶子节点的值指向磁盘中的某块数据地址存在指针 P_next 指向下一个叶子节点方便遍历查询。 关于 B 树的插入、删除可参考文章B树看这一篇就够了B树查找、插入、删除全上 - 知乎
参考为什么 MySQL 采用 B 树作为索引 | 小林coding
TASK#1-BTree Pages
了解完 B 树的基础知识后便可以着手实现 TASK#1。
我们现在很清楚一个完整的 B 树由根节点、内部节点和叶子节点三部分组成其实三者都是同一类型只不过根据位置不同不同节点存储的数据对象不同。
在 Project 中B 树所有节点都以 BTree Page 的形式存在根据节点类型不同又分为 BTree Internal Page 和 BTree Leaf Page二者均继承自 BTree Page区别只在于二者存储的数据类型不同
BTree Internal Page 的 Value 为子树根节点的索引BTree Leaf Page 的 Value 为元组 RID。
本节的目的就是实现以下三个页
BTree PageBTree Internal PageBTree Leaf Page
Base-Tree 需要修改的文件 src/include/storage/page/b_plus_tree_page.hsrc/storage/page/b_plus_tree_page.cpp 文件中的抽象类 BPlusTreePage 是B树所有节点类型的公共抽象包含了内部节点和叶节点共享的核心属性和方法我们实现的函数多数是 Get/Set因此比较简单。
因为内部节点和叶子节点都是 BPlusTreePage 的派生因此每个 B 树页面的起始位置都包含了三元素PageType (4) | CurrentSize (4) | MaxSize (4)分别代表
PageType4 字节标识页面类型CurrentSize4 字节当前页面中的键值对数量MaxSize4 字节页面可容纳的最大键值对数量
一共 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 树的所有节点均以 BTree Page 的形式存在但和 lab1 的 Page 是有本质上的区别BPlusTreePage 实际对应BPM 中 Page 对象的 data_ 存储区域。因此在读取或写入节点时首先需要通过 BPM.CheckedReadPage(page_id) 获取受保护可读的 std::optionalReadPageGuard 对象获取可写对象也如此再将其 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.hsrc/storage/page/b_plus_tree_internal_page.cpp B 树和 B 树最大的区别就是 B 树的内部节点存储的是索引信息而不是数据且 m 个 key 对应 m1 个 child这种设计使得每个键成为两个相邻子树的分隔符如下图所示 由于 child 的数量不等于 key 的数量因此将第一个键设置为无效key_array_[0] KeyType()并且查找方法应始终从第二个键开始简单来说就是牺牲空间获取效率举个例子说明 假如存在 key_array_ [5102030]且 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_[i1])若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一个页通常为 4KBHEADER占据 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() 在实现时需要设置边界禁止访问 index0 的无效键而 ValueAt() 可以访问 index0 的子指针。
Leaf Page 需要修改的文件 src/include/storage/page/b_plus_tree_leaf_page.hsrc/storage/page/b_plus_tree_leaf_page.cpp 和内部节点不同叶子节点存储 m 个有序键及其对应的 m 个值值的类型的 64 位的 RID指向数据记录的物理位置并且在 header 区域多了一个 NextPageId 字段该字段是下一个叶节点的指针用于将叶节点串成单向链表。
叶子节点的页面结构如下图 函数实现很简单不过多赘述。 一个完整的BTree结构如下所示
图片来源https://www.cnblogs.com/zhiyiYo/p/17472784.html test
TASK#1 没有测试完成 TASK#2 后进行。
