Posts

一些工具 BusTub B+Tree PrinterCMU官方在线的B+树的生成工具。我主要用来细节实现的时候进行参考。 JavaScript B+ TreeB+树插入和删除的动态演示。 Graphviz Online可视化自己的树。在debug的时候会用到。将生成的dot文件转换成svg图片。 Log In | Gradescope在线评测网站,邀请码：PXWVR5， Project #2 - B+Tree | CMU 15-445/645 :: Intro to Database Systems (Fall 2022)最重要的当然还是课程网站了 课程的视频，还有对应的教材还是推荐看一下的上面有很多实现细节的。非常值得参考。 如何Debug自己的🌳 大致上可以分为两种方式 可视化的用自带的printer将树生成dot文件然后复制到上面的可视化网站。 由于本项目采用的是cmake构建的，所以可以很方便的在测试文件中打上断点。进行调试。 ==可视化调试== 在终端中执行以下命令，构建和执行printer。 ➜ build git:(main) make b_plus_tree_printer -j2 // 构建printer ➜ build git:(main) ./bin/b_plus_tree_printer // 执行printer 执行完之后就会有以下提示： 按照这个提示就可以生成dot文件，然后复制到上述的网站进行可视化。（当你看到自己的树呈现出来的时候还是非常有成就感的😁） ==非可视化== 可以很方便的直接打断点，然后在vscode中的cmake插件中选择调试进行debug。 官方还提供了一种大打log的方式进行debug，我是不太习惯这种方式所以没有进行很深入的研究。感兴趣的可以自己进行了解😗。 两种debug的方式是相辅相成的，在你过不了本地样例的时候好好的用非可视化的方式进行debug，线上样例过不了大部分原因是细节处理上出问题了。用可视化的方式会更加的直观。 请不要公开代码，尊重Andy劳动成果 概览 Project2是实现B+树索引，整个project大致被分为了两个部分 checkpoint1：实现一个单线程的b+树。 checkpoint2：实现一个多线程的b+树。 实验代码中给出的自由发挥的空间非常的大，只给出了Getvalue(),Insert(),Remove()这三个函数的接口，剩下的所有的实现都非常的自由，整个实验实现的过程就像一个黑盒一样，只在乎输入和输出。 本实验需要完成b+ index部分，b+树中的页（page）都需要从上一个实验中实现的buffer pool中取。 Checkpoint-1 Task #1 - B+Tree Pages 需要完成以下三个page，主要都是一些getter和setter的函数，重在理解各部分的组成。 B+Tree Parent Page B+Tree Internal Page B+Tree Leaf Page 其中parentPage是internal page和leaf page的父类。我更倾向于把这几个page类型理解为 从buffer pool中取回来的Page的不同解释形式。Page还是那个Page。主要就是在于你如何去解释它的组成部分。 ...

数值类型 整数类型 整数就是没有小数部分的数字。之前使用过的 i32 类型，表示有符号的 32 位整数（ i 是英文单词 integer 的首字母，与之相反的是 u，代表无符号 unsigned 类型）。下表显示了 Rust 中的内置的整数类型： 整型溢出 在使用编程的过程中难免会发生数的范围超过了类型范围这时候就会发生溢出的现象。 有趣的是：在debug模式下编译器会检测有没有发生整形溢出的现象，如果有发生整数溢出的现象编译就会发生panic. 但是在release模式下，编译器不会进行整数溢出的的检测。当发生整数溢出的时候会按照补码循环溢出进行处理。简单来讲就是取余。 要显式的处理可能的溢出，可以使用标准库提供的类型。 使用warpping_*的方法在所有模式下都按照补码循环溢出的规则进行处理 使用check_*方法发生溢出的时候返回None值。 使用overflowing_*方法返回该值和是否溢出的一个bool值 使用saturating_*的方法返回最大值或者最小值 下面是一个演示warpping_*的一个示例代码 fn main() { let a : u8 = 255; let b = a.wrapping_add(20); println!("{}", b); // 19 } 最后这个输出结果也没有出乎意料。 浮点类型 浮点类型是带有小数点的数字。在Rust中浮点数类型也有两种表示f32,f64. 分别表示32位和64位。在现代CPU中32位的运算速度几乎和64位是一样的。所以默认是f64. 浮点数陷阱 浮点数在其底层表示上有很大的特殊性，这就导致了如果在使用的时候不够谨慎就会造成危险。主要有以下两个原因。 浮点数是一种近似的表达。由于所有的生活中的数字我们都是用十进制进行标识但是计算机用二进制在底层进行表示，所以我们很难非常准确的表示十进制的小数。 浮点数在某一些事情上是反直觉的。例如很多人都觉得浮点数是可以进行比较的对吧。但是实际上如果我们编写如下的代码会发生什么呢？ fn main(){ assert!(0.1+0.2==0.3); } 程序将会panic，因为二进制精度 的问题，0.1+0.2将会在N位之后与0.3发生偏差。 为了避免掉入陷阱当中，我们需要注意以下两点。 避免在浮点数上测试相等性 当结果在数学上存在未定义的时候我们需要格外的小心 但是如果非要进行比较呢？ 可以考虑用这种方式 (0.1_f64 + 0.2 - 0.3).abs() < 0.00001 ，具体小于多少，取决于你对精度的需求。 ...

一些关于为什么要学rust的想法 其实在大一的时候我就有了解过rust语言，当时甚至还看了一周b站的视频，在我最近准备再看rust的时候发现我大一装的环境还在，我甚至自己都不记得有这件事了。 rust语言据说有非常好的内存管理机制和安全措施，以及极高的执行效率，所以近些年被用作开发底层非常的多，而我对这方面也是非常的感兴趣，也算是兴趣驱动吧。希望能有助于提高一下自己的编程能力，让自己也多了解一下rust语言。

auto 在概念上auto已经极简了，但是实际上仍然要微妙许多。它可以节约声明类型，也可以避免许多手动类型的正确性和声明问题。但是从结果的角度来说，尽管auto很努力在做事了，但是仍然可能是错误的。如果出现这种情况我们要知道如何去引导auto让他成为正确的类型，因为退回使用手动声明类型仍然是下下策。 接下来的内容会涵盖auto的所有细节 Item 5: Prefer auto to explicit type declarations. 不仅可以避免出现为初始化的变量，避免啰嗦又繁杂的类型声明，能直接持有闭包，还可以避免一些因为“类型捷径”出现的问题。 eg1. 有一些程序员会对类型发生误判，到时用范围较小的类型在32位机器上能够运行但是在64位机器上发生了改变，导致程序在移植的时候出现问题。 eg2. 上述代码看起来没什么问题，但是当实际运行之后并没有对哈希表m进行操作。原因在于哈希表中的kay值是const类型的，手动声明的类型不一样的话编译器会进行一个神奇的操作，它会讲m中的内容复制成为临时变量将key的类型改为和声明一致的，再将p绑定到临时变量上。 Summary auto说到底只是一个可选项罢了，不是必选项，如果你觉得你的项目使用显式的声明能够使得项目变得更加的可读和高效，当然可以继续使用。但是c++引入auto并不是一个多新鲜的东西，只是一个在其他语言中被称为“类型推导”的东西罢了。在其他的静态类型语言中类型推导都或多或少存在。而且动态语言还为类型推导积累了大量的经验。而且此类技术并不会于大型的工程项目产生冲突。 一些人觉得用完auto之后会让变量的类型变得不是一眼可以识别，但是这个问题随着ide的优化和适配已经被解决的相当完美了。 事实上手动声明变量经常是在画蛇添足，无论是正确率还是效率上。 Item 6: Use the explicitly typed initializer idiom when auto deduces undesired types. 纵使auto有万般好，但是auto也会出现推断的类型和你心目中期待的不一样的情况（当然也不完全是auto错了哦😀） 下面举一个auto推断不符合预期的例子。 上述声明了一个返回vector< bool >类型的函数，使用了auto之后虽然仍然能够直接进行编译和运行但是结果却不是所想要的。 而发生这样错误的原因是，在c++的设计当中回避了bit的引用所以返回的不是bool&，实际上c++中设计了一个代理类来完成向bool的转换操作，这就不展开细说了，但是代理类并不少见，我们经常使用的两个智能指针就是一种代理类。 代理类的设计在使用的时候尽量少的对程序员暴露内部细节，这些代理类的使用往往会在文档中标识出来，如果在文档中没有体现的话，也避免不了在头文件中漏出一些破绽，最不济在debug的时候可能也会发觉是使用了代理类。 但是这些都不重要了，现在重要的事怎么把auto引导到正确的道路上🙃。 就是使用一个强制的类型转换，让它去到该去的位置，虽然看起来有点滑稽，给人一种头痛医脚的感觉🤣。虽然在这些时候你也可以放弃使用auto，但是在这个踩坑的过程中不是也收获了新的知识么?😁 总之记住以下两点 隐形的代理类可能会让auto推断出错误的类型。 显式的类型转换可以让auto走向正确道路。 Moving to Modern C++ 接下来这一章会详细介绍现代c++的一些细节特性。我自己会记录几个我认为比较实用的。并不是全部。 Item 8: Prefer nullptr to 0 and NULL. 非常显然的是0的类型是int，不是一个指针，但是在一个本应该出现指针类型的地方出现了0，编译器也会勉强吧0解释为空指针，但这毕竟是不得已而为之的行为🙉， 总之0是int，不是指针。 nullptr’s advantage is that it doesn’t have an integral type. To be honest, it doesn’t have a pointer type, either, but you can think of it as a pointer of all types. nullptr’s actual type is std::nullptr_t, and, in a wonderfully circular definition, std::nullptr_t is defined to be the type of nullptr. The type std::nullptr_t implicitly converts to all raw pointer types, and that’s what makes nullptr act as if it were a pointer of all types. ...

环境搭建 按照P0的指导中进行环境的搭建，由于我本人现在时WIN平台，课程没有提供一键配置环境的脚本，所以我选择云服务器进行环境的构建，很稳。 但是我的云服务器配置只有2核2G在编译的时候会爆内存。这里还有个故事，在爆内存之后我已经意识到这个问题，我给阿里云客服提了个工单试图能白嫖一些配置，客服还是很有水平的，直接就分析出来我是内存爆了导致的，但是直接建议我加钱升级配置，不告诉我设置swap分区，有点不厚道了。 话说回来，设置完swap分区之后就没有再出现过爆内存的现象。用VScode的远程开发，体验还是很不错的。 Overview p1主要是内存管理部分的内容，这门课程的课本和录制视频还是很有必要看一下的。 主要的任务是以下三个部分： 可扩展的哈希表 LRU-K的淘汰策略的视线 Buffer Pool的一个实例 在开始梳理项目之前我想要先解释清楚一下三个任务之间的关系，以及各个部分的负责。 frame更像是一个载体，而page是其中的内容。打个比方来说，一个仓库（buffer pool）只有100辆货车（frame），而货物（page）成千上万种，每次都是仓库告诉货车需要什么货物然后由货车带着货物来到仓库，而可扩展的哈希表就是登记货车和货物的对应关系。因为只有100辆货车，当每辆车都是满的时候（没有闲置的车辆free_list不为空）就需要根据task2的LRU-K算法挑选出一个符合要求的货车清空后去装载指定的货物。 而task3就是负责整个的管理和交互。 大概解释了一下，可能比方不是很恰当，做的时候一定要多看文档和注释，因为漏看注释给我带来了极大的痛苦。 Task #1 -ExtendibleHashTable 相关函数 Find(K,V): 查询一个Key是否存在，如果存在则将其V指针指向相关的值，返回true，否则返回false Insert(K,V): 插入一个（K，V），如果插入失败需要进行一下步骤的重试： 插入失败肯定是桶满了，但是桶满了分为两种不同的情况。 一种是global深度和桶的local深度不相同的时候，需要对桶进行重新的分配。 当两个深度相同的时候说明桶是真的满了，需要对哈希表进行扩展 Remove(K): 在哈希表中移除对应的（K，V）对，但是需要进行哈希表缩小的操作。 IndexOf(K): 当前global深度下的映射规则。 项目架构 首先要清楚这个是自己动手实现一个可扩展哈希表用于保存frame和page的映射关系的。我觉得首先要明白frame和page之间的关系。不清楚的可以回看上文的解释。 Bucket 存储桶 在可可以扩展的哈希表种引入和Bucket的概念，用于解决哈希冲突的问题，每一个Bucket的大小都是固定的，当一个Bucket满了的时候就需要进行哈希表的扩展。 Bucket的组成 depth_：表示本地深度的一个标识，用于识别当前的深度是否和全局深度相同。要特别注意这个变量。 list_：发生哈希冲突时保存多个（K，V）映射的双向链表。 size：为了保证效率，list的长度不能无限延伸，所以达到一定长度的时候要进行哈希表的扩展。 可扩展的哈希表结构 Bucket_size:用于限制每个bucket的list的长度 dir_:用于哈西运算后保存映射关系。 global_depth_:全局深度，在插入的时候根据全局深度和局部深度来确定这个桶是否要进行重新的分配。 num_buckets:用于统计现在一共有多少bucket。 ReHash的过程详解 1.hash的规则是什么样的 template <typename K, typename V> auto ExtendibleHashTable<K, V>::IndexOf(const K &key) -> size_t { int mask = (1 << global_depth_) - 1; return std::hash<K>()(key) & mask; } 上述函数就是该哈希表的映射规则，总的来说就是取hash函数值的低global_depth位 假如现在global_depth_的值为3。 那么 1 << global_depth_的值就是8转换为二进制就是 1000 。mask=8-1=7，转换为二进制就是 111. mask 的作用就是取一个位数和global_depth_一样的全1的二进制数，为了取低global_depth_位做铺垫。 现在假如key的值进行完hash之后是 10110100011010 和 mask进行进行 & 的操作之后就变成了 010 （低3位） ...