Hi, 👋, I’m Cookie

catch2用法 定义测试案例 测试案例在 Catch2 中通过 TEST_CASE 宏定义。TEST_CASE 宏接受两个参数：测试案例的名称和一个可选的标签。 #define CATCH_CONFIG_MAIN // 这行让 Catch 自己提供一个 main() 函数 #include <catch2/catch.hpp> TEST_CASE("A test case", "[tag]") { REQUIRE(1 == 1); } 如果你有多个测试文件，只需要在一个文件中定义 CATCH_CONFIG_MAIN。 断言 Catch2 提供了多种断言宏，最常用的是 REQUIRE 和 CHECK： REQUIRE：如果断言失败，当前的测试案例会立即停止。 CHECK：即使断言失败，当前的测试案例也会继续运行，允许多个断言失败。 TEST_CASE("Testing addition") { REQUIRE(1 + 1 == 2); CHECK(2 + 2 == 4); } 测试固件 测试固件允许你在每个测试案例之前和之后运行一些代码。测试固件允许你设置和清理测试环境，这对于需要在多个测试案例中重用相同的初始化和清理逻辑非常有用。测试固件通过定义一个结构体或类来实现，你可以在其中定义构造函数（用于设置）和析构函数（用于清理）。然后，使用 TEST_CASE_METHOD 宏来指定哪个固件类应该被用于哪个测试案例。 struct DatabaseFixture { Database db; DatabaseFixture() : db("my_database") { // 初始化代码，比如打开数据库连接 db.connect(); } ~DatabaseFixture() { // 清理代码，比如关闭数据库连接 db....

实验中给出的 B+ 树接口非常简单，基本只有查询、插入和删除三个接口，内部基本没有给出别的辅助函数，可以让我们自由发挥（无从下手）。因此，任何合法的 B+ 树实现都是允许的。 B+ 树索引在 Bustub 中的位置如图所示: B+树种需要的page都需要使用在 Project 1 中实现的 buffer pool manager 来获取。 Checkpoint1 Single Thread B+Tree Checkpoint1 分为两个部分： Task1: B+Tree pages，B+树中的各种 page。在 Bustub 索引 B+ 树中，所有的节点都是一个 page。包含 leaf page，internal page ，和它们的父类 tree page。 Task2：B+Tree Data Structure (Insertion, Deletion, Point Search)。Checkpoint1 的重点，即 B+树的插入、删除和单点查询。 Task1 B+Tree Pages task1 主要实现leaf page和internal page这两个类，都继承自BPlusTreePage这个父类，实现一些Getter和Setter方法。 首先介绍一下page的内存布局 其中，data_ 是实际存放 page 数据的地方，大小为 BUSTUB_PAGE_SIZE，为 4KB。其他的成员是 page 的 metadata。 B+树中的 tree page 数据均存放在 page 的 data 成员中，也就是B+树中的节点是Page的data数据成员。...

buffer pool是负责在内存和磁盘之间移动页面(数据库文件是以页来组织的)。buffer pool的操作对于系统的其他组件是 透明的，也就是说系统只需要使用一个page_id（这是唯一的）去像buffer pool请求这个页面，是不知道这个页是不是已经在内存中了，还是需要从磁盘中读。 可拓展hash table 第一个任务是需要实现一个可拓展hash table，这个hash table的作用是负责管理page_id到buffer pool中页面id(frame_id)的映射。buffer pool管理N个页面的内存空间，一个页面的内存空间就叫做frame。需要读取一个页面时，就将一个frame分配这个页面，然后用hash table记录这个映射关系。 在实现之前需要理解一些可拓展哈希表中的概念：[参考文献](Extendible Hashing (Dynamic approach to DBMS) - GeeksforGeeks) 目录dir：这个容器存储指向桶的指针。每个dir给定一个唯一的id，当扩张发生时id可能随之改变。哈希函数返回这个目录的id，这个id被用来指向合适的桶。dir的数量 = 2^{全局深度} 桶: 存储哈希键。目录指向桶。如果局部深度小于全局深度时，一个桶可能包含不止一个指针指向它。 全局深度：它跟目录相关联。它们表示哈希函数使用的比特位数目去分类这些键。全局深度=目录id的比特位数 局部深度：和全局深度类似，局部深度是跟桶关联，而不是跟目录。当桶溢出发生时，局部深度根据全局深度去决定执行的行为。局部深度通常小于等于全局深度。 桶分裂：当桶的元素超过了特定的大小，那么桶分裂成两个部分。 目录扩容：当桶溢出时，可能会有目录扩容。当溢出桶的局部深度等于全局深度时，目录扩容被执行。 首先需要实现的是Bucket，Bucket采用的std::list<pair<K,V»来作为存储数据的数据结构，stl可以让我们很方便的实现数据的增删查改。查找一个key可以通过std::find_if或者遍历这个list，插入时需要判断是否超出这个桶的大小。 有了Bucket，就可以开始实现我们的可拓展hash表，它的全局深度首先被初始化为0，由于桶的数量是2^全局深度，所以在开始时只有一个桶，即dir中只有一个Bucket指针。 重点是insert操作(插入一个key，value对)的实现。首先是根据hash函数计算出key的dir index，然后再在对应的桶中实现插入。在插入到桶中时可能因为桶已满而插入失败，这时候我们就需要进行目录扩张和桶分裂。需要注意的是：并不是桶满了就需要执行目录的分裂，而是当桶的局部深度=全局深度时，才需要进行桶的分裂。在桶的局部深度小于全局深度时是不需要扩张目录的，此时是有多个指针指向同一个桶，我们只需要再创建一个新桶，然后再将这个已满桶中的元素重新分配即可，创建新桶需要将局部深度+1。在桶扩张时，将新扩张的dir(桶指针)指向同一个桶，当需要时再去创建新的桶。 eg: global_depth = 2, local_depth = 2, dir_size = 2^2 = 4，插入kv到idx = 3 的桶，但这个桶已经满了。则需要执行dir扩张，扩张为原来的2倍，即dir_size = 2^2* « 1,扩张为8。idx = 3 = 011，3 + old_dir_size = 7 = 111，7的位置则是新建的桶。其他新扩张应该指向之前的桶，等到之间的桶满，再创建。即4指向0指向的桶，等等。 由于是要支持并发操作的，因此也需要在合适的地方加锁。 造成死锁的一种情况：当一个函数中已经加锁再去调用另一个需要同一把锁的函数，这会造成死锁。 lru_k替换策略 在frame中page，在整个buffer pool中的所有frame都被使用时，这时候则需要选择一个victim来替换。常使用的是lru算法，lru_k则是再lru的基础上多加了一个访问k次以上的页，是要比那些小于k次更晚被换出。简单的理解就是，将所有在frame中的页面分为访问小于k次的和大于等于k次的，两种都是采用lru算法，但是是先替换小于k次的页面，小于k次页面的全部不能被替换或者当没有小于k次还需要Evict一个page时，才去Evict一个大于k次的页面。 不能被替换的page是那些被pin的，也就是还在使用的page。 std::vector<LRUKFrameRecord *> frames_ 记录buffer pool中所有frame的一个访问记录，LRUKFrameRecord 是记录一个frame的最多k次访问记录。...

概览 需要实现一个数据结构为Trie树的kv存储，Trie一种高效的有序树数据结构，用于检索给定键的值。Trie中的每个节点存储一个key的单个字符，并且可以很多字节点，子节点代表key的下一个字符。key的末尾字符的节点(终端节点)会用一个flag标记这是一个key的结束，并存储相应的val。 下面这个Trie树，有ab->1,ac->“val”，两个kv对，注意val可以是任何类型。 实现 TrieNode TrieNode类代表树中的单个节点，代表一个key中的单个char。一个TrieNode可以有很多子节点，因此用unordered_map来存储每个子节点的字符和子节点指针的映射。此外还需要一个flag来表示该节点是否是一个key的结尾。为了避免内存泄露，采用智能指针。 TrieNodeWithValue 该类代表一个key的终端节点，它继承了TrieNode，并且增加了自己特有的属性，即需要存储的val. 可以有两种方式来创建终端节点： 插入一个key，创建一个新的终端节点。 插入一个key，将非终端节点转换为终端节点，即将TrieNode转为TrieNodeWithValue。因此需要给该类实现一个TrieNodeWithValue(TrieNode &&trieNode, T value)有参构造，用于将已有的非终端节点转为终端节点，这个构造需要去调用TrieNode的移动构造将trieNode的资源转移到终端节点，包括表示的字符和子节点map。 Trie 成员变量有root节点的指针，指向一个根节点(用字符‘\0’标识)；为了支持并发，还需要一个读写锁 ReaderWriterLatch latch_ 需要实现增删查三个功能 Insert 插入一个kv对到Trie中，一个key的每个字符都是一个节点，因此需要做的就是从root节点开始，一层一层的插入新节点，如果有该字符的节点了，我们应该重用它。key最后一个字符需要特殊处理，而不是直接在父节点中插入新节点。 需要判断是否该结尾字符已经在Trie树中，如果是，再判断这个节点是不是一个终端节点，如果是终端节点，则插入失败，因为不支持重复的key，如果不是终端节点，则需要将非终端的TrieNode转为终端节点TrieNodeWithValue。 如果结尾字符不在Trie树中，创建新的TrieNodeWithValue，然后插入到父节点中，插入完成。 同时在Insert操作中，应该是上写锁，返回时应该解锁。 Remove 移除给定key的val，同时需要删除一些没用节点。首先是根据这个key从root开始一层一层遍历，找到该key的终端节点，没有该key对应的终端节点则直接返回false。找到终端节点后，将其flag设为false，表示这不是一个终端节点，逻辑上删除这个kv。下一步我们需要从该节点开始向上递归的删除那些没有任何子节点的非终端节点，因为这些节点肯定是不再会被用到的，既不是一个key的结尾，也不是一个key的中间节点。实现上可以通过从root开始将遍历到该节点的路径保存，然后在路径中从后往前遍历每个节点，判断是否属于这种情况，是则在其父节点的map中移除。 同样的在Remove操作中，应该是上写锁，返回时应该解锁。 GetValue 返回指定key对应的val，注意这个val的类型是任意的，所以这是一个函数模板。还是首先从根节点开始一层一层遍历key的每个字符找到最后一个字符所在的节点，然后不是终端节点或者没有该节点，失败直接返回。有这个key所对应的终端节点，那么返回这个终端节点的val。这样就ok了吗？其实不是，由于val是任意类型的，所以还需要判断这个val是不是我们所要的val类型。要检查这两个类型是否相同，将终端 TrieNode 通过dynamic_cast转为 TrieNodeWithValue。 如果转换结果不是 nullptr，则类型 T 是正确的类型。在类型不匹配时，即使有key所对应的终端节点，也应该失败直接返回。只有在类型匹配时，才正确返回其val。 同样的在GetValue操作中，应该是上读锁，返回时应该解锁。 ReaderWriterLatch 在c++中可以通过std::shared_mutex mutex_很容易得实现一个读写锁。在bustub中已经有一个实现好的读写锁，上写锁mutex_.lock() ,上读锁mutex_.lock_shared(),对应的解锁操作分别是：mutex_.unlock() 和mutex_.unlock_shared()。 源码 //===----------------------------------------------------------------------===// // // BusTub // // p0_trie.h // // Identification: src/include/primer/p0_trie.h // // Copyright (c) 2015-2022, Carnegie Mellon University Database Group // //===----------------------------------------------------------------------===// #pragma once #include <memory> #include <stdexcept> #include <string> #include <unordered_map> #include <utility> #include <vector> #include "common/exception....

文件目录结构 $ tree . ├── add.c ├── div.c ├── head.h ├── main.c ├── mult.c └── sub.c # 指定使用的 cmake 的最低版本，可选，非必须，如果不加可能会有警告 cmake_minimum_required(VERSION 3.0) # 定义工程名称，并可指定工程的版本、工程描述、web主页地址、支持的语言 project(CALC) # 定义工程会生成一个可执行程序，语法add_executable(可执行程序名 源文件名称) add_executable(app add.c div.c main.c mult.c sub.c) # 定义变量，语法: set(VAR VALUE [CACHE TYPE DOCSTRING [FORCE]]).[]里是可选的 # eg.将文件名对应字符串存起来。 # 方式1: 各个源文件之间使用空格间隔 # set(SRC_LIST add.c div.c main.c mult.c sub.c) # 方式2: 各个源文件之间使用分号 ; 间隔 set(SRC_LIST add.c;div.c;main.c;mult.c;sub.c) add_executable(app ${SRC_LIST}) # 指定c++标准 # 使用g++时: $ g++ *.cpp -std=c++11 -o app # C++标准对应有一宏叫做DCMAKE_CXX_STANDARD，在CMake中想要指定C++标准有两种方式： # 在cmakelists....