CMU15-445-Spring-2023-Project #2 - B+Tree
前置知识:参考上一篇博文 CMU15-445-Spring-2023-Project #2 - 前置知识(lec07-010)
CHECKPOINT #1
Task #1 - B+Tree Pages
实现三个page class来存储B+树的数据。
- B+Tree Page
- internal page和leaf page继承的基类,只包含两个子类共享的信息;
- Impl:
- src/include/storage/page/b_plus_tree_page.h
- src/storage/page/b_plus_tree_page.cpp
- B+Tree Internal Page
- 一个内部页面存储 m 个有序键和 m+1 个指向其他 B+Tree 页面的子指针(作为 page_id)。这些键和指针在内部表示为一个 key/page_id 对数组。由于指针的数量不等于键的数量,因此第一个键被设置为无效,查找应始终从第二个键开始;
- 在任何时候,每个内部页面都应至少满一半。在删除过程中,可以合并两个半满的页面,或者重新分配键和指针以避免合并。在插入过程中,可以将一个完整的页面分割成两个,也可以重新分配键和指针以避免分割;
- Impl:
- src/include/storage/page/b_plus_tree_internal_page.h
- src/storage/page/b_plus_tree_internal_page.cpp
- B+Tree Leaf Page
- leaf page存储 m 个有序键及其 m 个相应的值。值应始终是tuple实际存储位置的 64 位 record_id;参阅 src/include/common/rid.h 中的 RID 类。leaf page对k/v对数量的限制与内部页面相同,并应遵循合并、拆分和重新分配键的相同操作;
- Impl:
- src/include/storage/page/b_plus_tree_leaf_page.h
- src/storage/page/b_plus_tree_leaf_page.cpp
每个 B+Tree 的leaf/internal page都与缓冲池获取的内存页的内容(即 data_ 部分)相对应。每次读取或写入leaf/internal page时,必须先从缓冲池中获取该页(使用其唯一的 page_id),然后 reinterpret cast 成leaf/internal page,并在读取或写入该页后将其unpin。
Task #2a - B+Tree Insertion and Search for Single Values
Impl:
src/storage/index/b_plus_tree.cpp
如果插入改变了根页面的 ID,则必须更新 B+Tree 索引头页面中的 root_page_id。为此,可以访问在构造函数中给出的 header_page_id_ page。然后,通过使用 reinterpret cast,将该页面解释为 BPlusTreeHeaderPage(来自 src/include/storage/page/b_plus_tree_header_page.h),并从这里更新根页面 ID。实现 GetRootPageId(目前默认返回 0)。
使用 project 1 中的page guard类来帮助防止同步问题。在访问页面时使用 FetchPageBasic(定义于 src/include/storage/page/)。以后在task 4 中实施并发控制时,可以根据需要将其改为使用 FetchPageRead 和 FetchPageWrite。
可以选择使用 Context 类(定义于 src/include/storage/index/b_plus_tree.h)来跟踪已读取或写入的页面(通过 read_set_ 和 write_set_ 字段),或存储需要递归传递到其他函数的其他元数据。
只需要在插入或删除时使用 write_set_。可能不需要使用 read_set_,这取决于实现。
在context中存储根页面 id,并在修改 B+Tree 时获取头页面的写保护。
write_set_ 的尾部保存当前节点的父节点,它应该包含访问路径上的所有节点。
如果要拆分节点(根节点除外),要确保 write_set_ 中至少还有一个节点。
要解锁header page,只需将 header_page_ 设为 std::nullopt。要解锁其他页面,只需从 write_set_ 中弹出即可。
插入后,当值的数量达到 max_size 时,分割叶节点;插入前,当值的数量达到 max_size 时,分割内部节点。这将确保在进行 InsertIntoLeaf 等操作后再重新分配时,插入叶节点不会导致页面数据溢出;这也将防止内部节点只有一个子节点。
当叶页面无法获取同级页面的latch时,需要抛出一个 std::exception 异常,以避免潜在的死锁。
每个线程将始终从头页到底部获取锁存器。释放锁存器时,请确保以相同的顺序(从页眉到底部)释放。
在插入时,即使拥有父节点的锁,也应始终获取子节点的锁。想想这样一种情况:一些线程正在使用读锁从叶子页中获取值,而另一些线程正在更新页面(例如,在聚合时)。如果不加锁,就会出现race。
- GetValue()
- 使用ReadPageGuard访问页面。通过header_page_id_访问header page,header page的root_page_id_指向根节点的第一个k/v对;
- 当获取了根节点的页面的latch后,释放header page的latch;
- 通过二分搜索key在页面中的位置,迭代向下查找到leaf page,然后找到leaf page中相应的value(rid)。
- Insert()
- 同样,先获取根页面,若根为空,通过NewPageGuarded获取一个新页面,然后插入;
- 若根节点不为空,通过write_set_维护向下搜索的path,直到到达leaf page,并且通过prev_和next_维护路径上节点的左右兄弟节点(插入分裂优化);
- 若搜索过程中某个internal page的size小于max size,就可以将write_set_中的节点弹出,因为即使叶子节点需要分裂,internal page需要插入新k/v对,size也是够的;
- 插入分裂优化:若leaf page插入后超过了max size,但是其兄弟节点没满,会将最左/右记录移动到其兄弟节点上,默认先向左移动;(参考InnoDB,充分利用索引页,还有一种方法就是在特定的递增key插入情况下,如果检测到三个连续递增的key,那么就不进行分裂,而是直接往右新建一个页面插入,避免频繁分裂)常规分裂就是50%。
- leaf page分裂会产生新的k/v,继续向上往internal page插入(根据write_set_维护的path),同样进行插入分裂优化;
- 若write_set_遍历完后还需要向上插入,那么通过NewPageGuarded获取新页面作为根节点,然后更新即可;
CHECKPOINT #2
Task #2b - B+Tree Deletions
支持key的删除,包括页面的合并或重新分配键。与插入一样,如果根页面发生变化,必须正确更新 B+Tree 的根页面 ID。
Impl:
src/storage/index/b_plus_tree.cpp
- Remove()
- 几乎与Insert同样的思路,进行合并优化,优先从兄弟节点拉取单个k/v到本节点;
Task #3 - An Iterator for Leaf Scans
添加一个 C++ 迭代器,以有效支持对leaf page中的数据进行顺序扫描。基本思路是存储同胞指针,以便高效地遍历leaf page,然后实现一个迭代器,按顺序遍历每个leaf page中的每个键值对。
- C++17 style;
- isEnd():返回此迭代器是否指向最后一个键/值对;
- operator++():移动到下一个键/值对;
- operator*():返回该迭代器当前指向的键/值对;
- operator==():返回两个迭代器是否相等;
- operator!=():返回两个迭代器是否不相等;
- Begin() & End():返回最左/右的leaf page的迭代器;
Impl:
src/include/storage/index/index_iterator.h
src/index/storage/index_iterator.cpp
src/storage/index/b_plus_tree.cpp
IndexIterator内部维护三个值:bpm、page id、page内部index。
Task #4 - Concurrent Index
FetchPageWrite or FetchPageRead
实验结果
相关文章:

CMU15-445-Spring-2023-Project #2 - B+Tree
前置知识:参考上一篇博文 CMU15-445-Spring-2023-Project #2 - 前置知识(lec07-010) CHECKPOINT #1 Task #1 - BTree Pages 实现三个page class来存储B树的数据。 BTree Page internal page和leaf page继承的基类,只包含两个…...

matplotlib:热图、箱形图、小提琴图、堆叠面积图、雷达图、子图
简介:在数字化的世界里,从Web、HTTP到App,数据无处不在。但如何将这些复杂的数据转化为直观、易懂的信息?本文将介绍六种数据可视化方法,帮助你更好地理解和呈现数据。 热图 (Heatmap):热图能有效展示用户…...

Django数据库选移的preserve_default=False是什么意思?
有下面的迁移命令: migrations.AddField(model_namemovie,namemov_group,fieldmodels.CharField(defaultdjango.utils.timezone.now, max_length30),preserve_defaultFalse,),迁移命令中的preserve_defaultFalse是什么意思呢? 答:如果模型定…...

逸学Docker【java工程师基础】2.Docker镜像容器基本操作+安装MySQL镜像运行
基础的镜像操作 在这里我们的应用程序比如redis需要构建成镜像,它作为一个Docker文件就可以进行构建,构建完以后他是在本地的,我们可以推送到镜像服务器,逆向可以拉取到上传的镜像,或者说我们可以保存为压缩包进行相互…...

基于Java SSM框架实现医院管理系统项目【项目源码】计算机毕业设计
基于java的SSM框架实现医院管理系统演示 SSM框架 当今流行的“SSM组合框架”是Spring SpringMVC MyBatis的缩写,受到很多的追捧,“组合SSM框架”是强强联手、各司其职、协调互补的团队精神。web项目的框架,通常更简单的数据源。Spring属于…...

【java八股文】之Spring系列篇
【java八股文】之JVM基础篇-CSDN博客 【java八股文】之MYSQL基础篇-CSDN博客 【java八股文】之Redis基础篇-CSDN博客 【java八股文】之Spring系列篇-CSDN博客 【java八股文】之分布式系列篇-CSDN博客 【java八股文】之多线程篇-CSDN博客 【java八股文】之JVM基础篇-CSDN博…...
关于MySQL源码的学习 这里是一些建议
学习MySQL源码需要一定的编程基础,特别是C语言和数据结构。以下是一些建议,帮助你更好地入手学习MySQL源码: 基础知识 熟悉C语言编程基本概念、数据结构和算法。了解Linux操作系统基本概念,如进程、线程、内存管理、文件系统等。…...

Mysql是怎样运行的--下
文章目录 Mysql是怎样运行的--下查询优化explainoptimizer_trace InnoDB的Buffer Pool(缓冲池)Buffer Pool的存储结构空闲页存储--free链表脏页(修改后的数据)存储--flush链表 使用Buffer PoolLRU链表的管理 事务ACID事务的状态事…...

yum来安装php727
yum 安装php727,一键安装,都是安装在系统的默认位置,方便快捷 先确定linux平台中centos的版本信息,一下内容针对el7 查看linux版本 : cat /etc/redhat-release 查看内核版本命令: cat /proc/version (0)如果有安装好…...
基于jackson封装的json字符串与javaBean对象转换工具
文章目录 一、概述二、编码实现1. pom文件引入组件2. 核心代码 三、功能测试1. 测试文件2. 测试代码 四,完整代码 一、概述 带有API接口交互的web项目开发过程中,json字符串与javaBean对象之间的相互转换是比较常见的需求,基于jackson Objec…...
js中的数据类型
JavaScript 中有以下几种常见的数据类型: 基本类型(原始类型): 字符串(String):表示文本数据。数字(Number):表示数值数据。布尔(Boolean…...
vue3+vant+cropper.js实现移动端图片裁剪功能
一、前言 最近做项目中遇到一个需求,需要对海报图片按照一定的比例进行裁剪并上传到oss。一开始这个需求思路有两个,使用canvas原生或者寻找现成的第三方库,对比了一番觉得canvas实现时间耗费较长,且秉承着不重复造轮子的原则&am…...

springCould中的Bus-从小白开始【11】
目录 🧂1.Bus是什么❤️❤️❤️ 🌭2.什么是总线❤️❤️❤️ 🥓3.rabbitmq❤️❤️❤️ 🥞4.新建模块3366❤️❤️❤️ 🍳5.设计思想 ❤️❤️❤️ 🍿6.添加消息总线的支持❤️❤️❤️ ǹ…...
xshell和xftp
1.xshell和xftp的关系 Xftp和Xshell都是Xmanager Power Suite的组件,它们的功能和用途有所不同。 Xshell是一个用于MS Windows平台的强大的SSH、telnet和rlogin终端仿真软件,它使得用户能轻松和安全地从Windows PC上访问Unix/Linux主机。 Xftp是一个用…...
python for...else用法,一个实例就能让你明白
直接上代码,很简单,不用讲解吧,看不懂的话,就需要补充下基础知识了。 def funct2():for i in range(4):try:assert i>2print("success")breakexcept Exception as e:print(error)continueelse:print(循环不合预期)d…...
windows 设置ip命令bat脚本
您可以使用以下命令创建一个批处理文件(.bat)来添加IP地址: echo off set ipaddress set subnetmask set gatewaynetsh interface ip set address name"以太网" sourcestatic address%ipaddress% mask%subnetmask% gateway%gatewa…...
Openharmony 对应Android内存查看
众所周知,内存查看是一个很重要的部分,大多数情况,我们都是使用dumpsys的方法对android的内存进行查看,但是对于openharmony而言好像又不太一样了。 Android内存查看 命令行: adb shell dumpsys meminfo <packag…...
R语言【paleobioDB】——pbdb_interval():通过ID选择,返回一个地层年代段的基本信息
Package paleobioDB version 0.7.0 paleobioDB 包在2020年已经停止更新,该包依赖PBDB v1 API。 可以选择在Index of /src/contrib/Archive/paleobioDB (r-project.org)下载安装包后,执行本地安装。 Usage pbdb_interval (id, ...) Arguments 参数【id】…...

spring boot mybatis plus mapper如何自动注册到spring bean容器
##Import(AutoConfiguredMapperScannerRegistrar.class) ##注册MapperScannerConfigurer ##MapperScannerConfigurer.postProcessBeanDefinitionRegistry方法扫描注册mapper ##找到mapper候选者 ##过滤mapper 类 候选者 ##BeanDefinitionHolder注册到spring 容器...
What is `@PathVariable` does?
PathVariable 是SpringMVC中的注解,用于将HTTP请求的URI路径变量映射到Controller方法参数上。 当URL路径中包含占位符(由大括号 {} 包围的部分)时,可以使用此注解来绑定这些动态部分到方法参数。 使用样例 获取单个路径变量 …...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...