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路径中包含占位符(由大括号 {} 包围的部分)时,可以使用此注解来绑定这些动态部分到方法参数。 使用样例 获取单个路径变量 …...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...

Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...

docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...