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

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继承的基类,只包含两个子类共享的信息;
    • image.png
    • 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

实验结果

image.pngimage.png

相关文章:

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&#xf…...

vue3+vant+cropper.js实现移动端图片裁剪功能

一、前言 最近做项目中遇到一个需求,需要对海报图片按照一定的比例进行裁剪并上传到oss。一开始这个需求思路有两个,使用canvas原生或者寻找现成的第三方库,对比了一番觉得canvas实现时间耗费较长,且秉承着不重复造轮子的原则&am…...

springCould中的Bus-从小白开始【11】

目录 🧂1.Bus是什么❤️❤️❤️ 🌭2.什么是总线❤️❤️❤️ 🥓3.rabbitmq❤️❤️❤️ 🥞4.新建模块3366❤️❤️❤️ 🍳5.设计思想 ❤️❤️❤️ 🍿6.添加消息总线的支持❤️❤️❤️ &#x1f9…...

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内存查看

众所周知&#xff0c;内存查看是一个很重要的部分&#xff0c;大多数情况&#xff0c;我们都是使用dumpsys的方法对android的内存进行查看&#xff0c;但是对于openharmony而言好像又不太一样了。 Android内存查看 命令行&#xff1a; adb shell dumpsys meminfo <packag…...

R语言【paleobioDB】——pbdb_interval():通过ID选择,返回一个地层年代段的基本信息

Package paleobioDB version 0.7.0 paleobioDB 包在2020年已经停止更新&#xff0c;该包依赖PBDB v1 API。 可以选择在Index of /src/contrib/Archive/paleobioDB (r-project.org)下载安装包后&#xff0c;执行本地安装。 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中的注解&#xff0c;用于将HTTP请求的URI路径变量映射到Controller方法参数上。 当URL路径中包含占位符&#xff08;由大括号 {} 包围的部分&#xff09;时&#xff0c;可以使用此注解来绑定这些动态部分到方法参数。 使用样例 获取单个路径变量 …...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...