项目准备

项目地址：Project #4 - Concurrency Control。

准备工作：阅读 Chapter 18 19，学习 Lecture #15 #16 #17 #18 #19 #20，以及阅读课堂笔记。

项目结构

项目的注释中有锁升级的矩阵图，但是没有兼容性的矩阵图，这里贴一下。

Task #1 - Lock Manager

实现

① 比较关键的一个问题是，LockRequestQueue 里面存什么。我之前漏掉 granted_ 成员，导致整个项目理解都有问题。一个请求会经历未获取锁、已获取锁，已释放锁三个过程，LockRequestQueue 存储所有没有被释放的锁请求，即前两个过程。因为之后能否获取锁，需要和之前已经获取的锁做兼容性判断。

② 加锁阶段：

• 代码组织：我们可以根据请求的锁模式来分类讨论，也可以根据事务的锁模式来分类讨论，也可以根据事务是否有锁进行分类讨论。我最后是选择最后一种方式，这样写起来真的简洁。如果当前事务没有该资源的锁，则将请求入队，并且根据该资源是否被其他事务上锁，从而直接拿锁或者进行等待；否则，判断能否进行锁升级。
• 锁升级：
  • 根据提示，首先判断请求的锁模式是否和事务的锁模式是否相同，如果相同则直接返回 true。我在这里有个比较疑惑的点，如果请求锁模式的级别低于当前持有的锁模式，应该也可以直接返回 true，但是注释中并没有提及，并且线上测试结果告诉我不行，必须抛出异常。似乎是设计的问题，讨论在此，而且这个讨论似乎说的也不完整。
  • 然后判断是否可以锁升级，如果可以，我们需要释放之前的锁，并等待获取升级的锁。这两个步骤可以通过修改队列中的 LockRequest 实现，将锁模式修改为新的锁模式，将 granted_ 修改为 false，然后 cv_.wait() 即可。关键是条件变量的获取锁的条件如何编写。注意，一定要在等待之前从当前事务的锁集中移除原来的锁，因为线上测试会在等待时检查锁集。
• 获取锁：如何以 FIFO 的方式获取锁，并且使兼容的锁可以同时获取，以及使锁升级的优先级最高。遍历请求队列，如果当前事务是锁升级请求，则只需判断当前请求是否和已 granted_ 的请求兼容。如果当前事务不是锁升级请求，并且存在其他事务的锁升级请求，则直接返回 false，否则不仅需要判断当前请求是否和已 granted_ 的请求兼容，还需要判断当前请求是否和在该请求之前的未 granted_ 的请求兼容。

③ 解锁阶段：按照注释模拟，需要注意从队列中移除完成的锁请求，并在最后执行 cv_.notify_all()。

④ 事务的 ABORTED 状态：如果事务被中止，那么应该取消该事务所做的操作，事务中止之后会自动调用 TransactionManager::Abort 函数来进行解锁和还原所有写操作。但是如果事务在等待锁的过程中被中止，那么就需要我们手动重置，因为 Abort 函数不会清除未获取锁的请求。步骤如下：在使用条件变量时，额外判断当前事务的状态是否是 ABORTED，如果是则直接退出等待，并从队列中移除该请求，如果是锁升级还要记得重置 upgrading_，最后调用 cv_.notify_all() 并返回 false。

补充

① 一个细节问题，在获取 map 中的 LockRequestQueue 时，我依赖 C++ 在使用 [] 访问会自动创建对象的特性，没有注意到 map 中存的是智能指针，这样默认是创建空指针，结果就会报各种奇怪的错误。

② 表解锁同样需要改变事务的状态，一开始我天真的以为只需要在行解锁的时候改变就行，因为我以为加表锁必定会加行锁，但是不是这样的，可以只加表锁（或许全表扫描就是只加表锁而不加行锁）。

③ 线上测试遇到神奇的错误，pthread_mutex_lock.c:94: _pthread_mutex_lock: Assertion ‘mutex->data.__owner == 0’ failed，而且不是每次测试都会发生。经过排查，发现又是自动补全的锅，导致重复执行 unlock() 操作，有关该错误的讨论在此。

④ 目前似乎不需要使用事务锁，单个事务加锁/解锁是单线程的。

Task #2 - Deadlock Detection

① 构建等待图，使用二重循环遍历 table_lock_map_ 和 row_lock_map_ 来向 waits_for_ 添加从 granted_ == false 请求到 granted_ == true 请求的边。其实这样单纯的加边是比较简单的，但是可能存在锁兼容的情况，这样构成的环是不会造成死锁的，导致误杀事务，不过测试能过就不改代码了。记得加锁。

② 因为可以存在很多环，如果检测顺序不一样，中止的事务可能完全不同，所以 NOTES 中要求我们从最小的事务开始做 DFS，按照从小到大的顺序遍历相邻节点，如果找到环，则中止环中最大的事务。如果事务被中止，则应该从图中删掉连接该事务的边，或者也可以打标记。有坑！！！HasCycle 应该包含什么代码，之前我是把最小事务编号作为参数传递，然后从该事务开始做 DFS 来检测环。但是线上 GraphTest 测试会调用 HasCycle，按照线上测试代码的逻辑，HashCycle 应该包含整个环检测代码，包括排序 waits_for_，排序 GetEdgeList 得到的边集，以及 DFS。特别注意，不要在 HashCycle 中调用 txn_manager_ 的任何方法，因为 GraphTest 测试根本就没创建事务！！！我是调试半天找不到错，才反应过来，非常无语。

③ 最后，从 HasCycle 返回时，删除中止事务的边，然后调用 TransactionManager::Abort 函数中止事务。在消除所有环之后清空 waits_for_。

Task #3 - Concurrent Query Execution

① 非常非常无语！！！就是我在 Task#1 中提到的，高级锁可以包含低级锁的需求，不应该抛出异常，结果测试不给过，Task#3 又需要我兼容这种情况，那么只能在 Executor 代码中特判了。

② 根据提示，should not acquire S/X table lock, grab IS/IX instead，只为表加 IS/IX 锁。

③ 细节问题：行加锁之后再判断行是否删除，这个错误找很长时间才发现；死锁检测在调用 Abort 函数之前，先将事务状态设置为 ABORTED，否则当前事务可能会在之后的解锁过程中被唤醒，触发 LOCK_ON_SHRINKING 异常；实现 Abort 函数时，将恢复阶段放在解锁阶段之前，不然可能会有并发问题。

Leaderboard Task (Optional)

① 初次提交。

测试结果

1
2
3
4
5
6
7
8
9
10
11
12
13

#!/bin/bash
make lock_manager_test -j$(nproc)
make deadlock_detection_test -j`nproc`
make txn_integration_test -j`nproc`
make -j`nproc` terrier-bench 
./test/lock_manager_test
./test/deadlock_detection_test
./test/txn_integration_test
./bin/bustub-terrier-bench --duration 30000
make format
make check-lint
make check-clang-tidy-p4
make submit-p4

项目小结

难点就在项目理解以及代码细节上，Task#1 和 Task#2 被队列和 HashCycle 的理解整晕了，然后要使代码能够在多线程情况下正常运行，一定要注意代码中逻辑的先后顺序！！！实现过程部分参考做个数据库：2022 CMU15-445 Project4 Concurrency Control，Task#1 的解释帮助很大。

项目准备

项目地址：Project #3 - Query Execution。

准备工作：阅读 Chapter 15 16 22，学习 Lecture #10 #11 #12 #13 #14，以及阅读课堂笔记。

项目结构

通过查看 sqllogictest.cpp，可以知道 SQL 语句的整个执行流程。首先调用 SQLLogicTestParser::Parse 将测试文件解析为多个测试记录，然后根据记录的类型分别处理。目前我们主要关注查询语句，只需查看 BustubInstance::ExecuteSqlTxn 函数的代码。如项目介绍描述的那样，代码分别执行 Binder,Planner,Optimize,ExecutionEngine。然后，本来想详细分析一下整个流程，但是由于时间原因，以及项目确实比较复杂，所以暂时搁置。

Task #1 - Access Method Executors

实现

① 遇到第一个问题，如何在 SeqScanExecutor 中遍历表，可以发现 exec_ctx 成员所属的类 ExecutorContext 中有一个 GetCatalog 方法，只要拿到 Catalog 就可以根据 plan_ 中的信息拿到 TableHeap 的迭代器 TableIterator。然后第二个问题就是如何存储迭代器，TableIterator 是不可复制的，我们可以使用 unique_ptr 来存储迭代器，并使用 make_unique 初始化。（注意，不能在构造函数初始化，一定要在 Init 函数中初始化，不然多次全表扫描会出问题！）

② 实现 Insert 时报错 “The executor will produce a single tuple of integer type as the output, indicating how many rows have been inserted into the table”，并且可以看到 Next 函数的注释中表示 “tuple The integer tuple indicating the number of rows inserted into the table”。说实话有点难以理解，我一开始以为每次调用 Next 会像迭代器模式一样，只执行一次插入，但是这样实现就会报上面的错误。然后通过查看 Discord 的讨论，发现是一次性插入所有记录，因为只要返回 true 就会打印插入的行数，返回 false 就不会打印。当插入零行时，还必须打印一个零，这说明，Next 必定要先返回 true，再返回 false。并且在构造 tuple 时需要使用 BIGINT 类型，不然会报其他错误（明明注释说的是 INTEGER 额）。

③ 在 Insert 的同时需要更新索引，一开始我是直接用普通的 tuple 作为 InsertEntry 的参数，结果在测试 p3.05-index-scan.slt 时报 stack buffer overflow 错误。通过 Debug 发现，在 InsertEntry 时会调用 GenericKey 类的 SetFromKey 函数，该函数会将 tuple 的数据拷贝到该类的 data_ 成员中，作为索引的 key 使用。所以传入的 tuple 必须只包含 key，那么如何确定 tuple 中的哪个数据是 key 呢。可以发现 Tuple 类中有 KeyFromTuple 函数，它的会生成只包含 key 的 tuple，因为需要的索引的 key，那么该函数必定需要传入和索引相关的模式，以及 key 所在列的下标，这些信息可以在 IndexInfo 中找到。（之前我有点迷糊，当成 MySQL 默认使用主键索引了，BusTub 使用的是 TableHeap，也就是说表默认是没有索引的）

④ 实现时不要使用 GetTableOid 函数，因为线上测试的函数名是 TableOid，可能是因为我 fork 的版本太新了，仓库的代码和测试代码不一样，所以只能直接使用 table_oid_ 成员。

⑤ 实现 update 时要注意，在创建新 tuple 时，使用的是 child_executor_->GetOutputSchema()，而不是 GetOutputSchema()。

⑥ 实现 index_scan 时，会使用到 b_plus_tree_index.h 中定义的别名，如 BPlusTreeIndexIteratorForTwoIntegerColumn。

⑧ 在 IndexScan 的提示中有这么一句话，“do not emit tuples that are deleted”，但是当从表中删除 tuple 时，也会从索引中删除对应的 key，所以应该不会遍历到已经删除的 key 才对，也就是说此时应该不用特判 TupleMeta 中的 is_deleted_ 成员。

⑨ 测试 p3.06-empty-table.slt 时，遇到 B+Tree 迭代器实现问题。当 B+Tree 的为 empty 时，获取迭代器我原来是抛出异常，现在改为返回一个默认构造的迭代器。

补充

① 当没有显示声明复制/移动构造函数或复制/移动运算符，以及析构函数时，编译器才会隐式生成这些函数（其他更复杂的情况可以查看 cppreference.com）。

② 创建 TupleMeta 时，会将 insertion_txn 和 deletion_txn_ 都初始化为 INVALID_TXN_ID，提示表示这些成员会在以后切换到 MVCC 存储时使用，有点遗憾没能体验一下。

③ vector 的 reserve 只会影响 capacity 的大小，而不会影响 size，讨论在此。

④ 重载前置和后置 ++ 的区别，前置 ++ 的重载声明为 operator++()，后置 ++ 的重载声明为 operator++(int)。

⑤ 为什么应该将移动构造声明为 noexcept，可以阅读 Friendly reminder to mark your move constructors noexcept。

Task #2 - Aggregation & Join Executors

实现

① 一开始实现真摸不着头脑，AggregationPlanNode 里面怎么这么多东西。group_bys 是指 GROUP BY 时对列的求值表达式，aggregates 是指使用聚合函数时对列的求值表达式，agg_types 是指聚合函数的类型。例如：GROUP BY DAY(col)、MIN(col1 + col2)。我们使用 InsertCombine 函数向哈希表插入值，参数可以使用 MakeAggregateKey 和 MakeAggregateValue 函数获得。

② 根据项目介绍，AggregationExecutor::Next 返回的 tuple 应该包含 key 和 value（我没看到，找错好难）。特别需要注意，当哈希表为空时，应该返回什么：如果是对某列进行 GROUP BY 操作，那么就返回 false，因为有个测试用例有注释 no groups, no output；否则，返回 true，并且 tuple 存储聚合函数的默认值。（可以通过判断 key 模式的列数是否为零，或者 value 模式的列数是否等于 plan_ 输出模式的列数，来判断当前是否对某列进行 GROUP BY 操作）

③ 实现 NestedLoopJoinExecutor：外层循环遍历左表，内层循环遍历右表，只有当右表遍历完，才会获取下一个左表中的元组。但是，因为每找到一个匹配就会返回，所以我们应该将左表的元组作为数据成员，并且添加一个标志表示右表是否遍历完。每当右表遍历完成，都需要重置标志，获取左表中的下一个元组，并且重新 Init 右表。我们调用 EvaluateJoin 判断元组是否匹配，如果匹配，就将两个元组合并为一个元组。特别注意，如果当前是左连接，并且左元组没有匹配任何右元组，仍然需要返回一个为右元组填充 null 值的合并元组。比较迷惑的是怎么表示 null，我的想法是根据列类型获取对应的 null 值，但是找不到这样的函数，所以我就直接返回 BUSTUB_INT32_NULL 了。突然看到聚合执行器里用到 ValueFactory::GetNullValueByType 函数，太久没写项目给忘了。我还遇到一个 BUG，调试半天，发现我没有在 Init 函数中初始化 SeqScanExecutor 的迭代器，导致重复调用 Init 时不会重置迭代器。

④ 实现 HashJoin：根据提示我们可以参考 SimpleAggregationHashTable 的实现建立一个哈希表，我们创建一个 JoinKey 类作为键，然后创建一个 hash<bustub::JoinKey> 类，直接复制 aggregation_plan.h 中的代码改个名字就行（不然 C++ 真不熟，又要搞半天）。在哈希表中，将 vector<Tuple> 作为值以处理哈希冲突。搞定哈希的方式之后，我们可以像 aggregation_executor.h 一样添加两个辅助函数 MakeLeftJoinKey 和 MakeRightJoinKey。然后直接在 Init 中对左表建立哈希表，在 Next 中遍历右表，类似 NestedLoopJoinExecutor 的实现，只不过此时需要维护更多的数据成员。特别需要注意如何处理左连接，因为我们是将左表建为哈希表，那么在遍历完右表后，还需要处理没有任何匹配的左表中的元组。这可以在匹配时将元组的地址存储在 unordered_set 中，然后在遍历完右表后再遍历一次左表，并检查 unordered_set 来判断是否输出。（之前我是将元组的 RID 存储到集合中作为标识，但是这是错误的，因为左表可能是临时表，其中元组的 RID 是无效的内容；我们也可以为右表建立哈希表而不是左表，这样对于左连接来说，更好处理）

⑤ 实现 Optimizing NestedLoopJoin to HashJoin：非常的神奇，参考 nlj_as_index_join.cpp 瞎改，感觉代码是一坨，但是竟然没有任何错误，直接通过测试（激动半天）。具体实现的话，一开始我以为传入的参数就是 NestedLoopJoin 计划节点，但是似乎不是，所以我们需要遍历当前计划的子节点，递归的进行优化。之前比较令我迷惑的一点，怎么判断表达式是否是某个类型，我查找很久 API 都没有找到类似的函数，然后想到 Project #0 中好像是直接做 dynamic_cast 转换，如果返回值为 nullptr 就表示类型不匹配，查看 nlj_as_index_join.cpp 发现果然是这样。搞定表达式类型判断之后，就可以根据 ColumnValueExpression::GetTupleIdx 值来交换左右表达式，并返回转换后的节点。

Task #3 - Sort + Limit Executors and Top-N Optimization

Easy！只有两点需要注意：一个是每次调用 Init 时都要初始化所有数据成员，不然下次调用会包含上次调用的数据；第二个是 C++ 的 priority_queue 默认是大顶堆，并且比较器和 Java 中的用法完全相反。

Optional Leaderboard Tasks

① 初次提交。

② 之后优化。

测试结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#!/bin/bash
make sqllogictest -j$(nproc)

./bin/bustub-sqllogictest ../test/sql/p3.00-primer.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.01-seqscan.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.02-insert.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.04-delete.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.03-update.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.05-index-scan.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.06-empty-table.slt --verbose

./bin/bustub-sqllogictest ../test/sql/p3.07-simple-agg.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.08-group-agg-1.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.09-group-agg-2.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.10-simple-join.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.11-multi-way-join.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.12-repeat-execute.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.14-hash-join.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.15-multi-way-hash-join.slt --verbose

./bin/bustub-sqllogictest ../test/sql/p3.16-sort-limit.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.17-topn.slt --verbose

./bin/bustub-sqllogictest ../test/sql/p3.18-integration-1.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p3.19-integration-2.slt --verbose

make format
make check-lint
make check-clang-tidy-p3
make submit-p3

项目小结

项目难度主要在项目理解上，常常是不理解某些变量的实际含义，或者知道该怎么做，却找不到对应的 API，或者对返回值理解有错误，而函数文档也不清晰。最后，看到实现的代码能够执行各种 SQL 语句，感觉还是很不错的。

项目准备

项目地址：Project #2 - B+Tree

准备工作：阅读 Chapter 14.5 24.5 14.1-14.4 18.10.2，学习 Lecture #07 #08 #09，以及阅读课堂笔记。

Task #1 - B+Tree Pages

实现

① 第一个比较迷惑的点就是 max_size_ 的含义，对官方提供的B+Tree进行插入操作，发现叶子节点的 size_ 不会到达 max_size_。难道叶子节点实际只能包含 max_size_ - 1 个 key 吗？通过查看项目地址中的 Requirements and Hints 可以发现，官方建议叶子节点在插入后大小达到 max_size_ 时，进行分裂，内部节点在插入前大小达到 max_size_ 时进行分裂。所以对于内部节点，max_size_ 表示它能包含的指针数量；对于叶子节点，max_size_ 表示它能包含的键值对数量。

② GetMinSize 的实现，同样参考官方示例，对于非叶子节点，返回 (max_size_ + 1) / 2；对于叶子节点，返回 max_size_ / 2。为什么要这样，参考第 ① 点也就明白了，这样可以保证分裂后的两个节点的大小都至少为最小大小，所以该方法的实现实际上取决于分裂的具体实现（即何时分裂）。

补充

① 如何理解 MappingType array_[0]，注释表示它是 Flexible array member for page data，参见维基百科Flexible array member。似乎是 C 语言的特性，C++ 标准不支持，但是 C++ 的编译器普遍会支持。

② 在内部节点和叶子节点中，array_ 的唯一区别就是在搜索内部节点时不能使用 array[0]_.first，因为它并不能准确表示 array_[0].second 中 key 的范围（向 array_[0].second 中插入一个更小的 key，它就失效了）。

Task #2a - B+Tree Insertion and Search for Single Values

实现

① 比较纠结的是既然要使用二分查找，如何保证节点内部 key 的有序性，因为是使用数组存储的，所以似乎只能花费 \(O(n)\) 时间来移动元素了？或者可以加一个数据结构存下标，来保证有序性，但是涉及分裂和删除操作还是比较难搞的，暂时不优化。

② 可以在 BPlusTreeInternalPage 和 BPlusTreeLeafPage 中添加 Search 函数，来实现二分查找指定 key。内部节点一定可以找到一个满足条件的位置（因为我们找的实际上是指针），而叶子节点如果找不到指定 key，那么就返回 -index - 1（方便之后插入，类似 Java 中的 BinarySearch）。具体的实现逻辑：

• 内部节点从位置 1 开始找第一个大于 key 的键，返回它左边位置，即 index - 1。
• 叶子节点从位置 0 开始找第一个大于等于 key 的键，如果越界或者键值不等于 key，则返回 -index - 1，否则返回 index。

③ 特别注意 PageGuard 的使用，只有当操作完页面之后，才对其进行 Drop 操作（移动赋值以及匿名对象的析构都会导致该操作）。并且用完页面后及时 Drop，这样可以尽早释放页面的锁以及 Unpin 页面。插入时，利用 latch crabbing 技巧，先拿到下个页面的锁，然后根据页面大小判断是否 Drop 上个页面（使用 Context）。注意拿锁和 Drop 的顺序，以及该大小判断依赖于分裂的实现，详细见 Task #1 - B+Tree Pages ①。

④ 获取页面需要进行类型转换，如果只读不写就使用 page_guard.h 中提供的 As 函数，只有需要写页面时才使用 AsMut 函数，因为该函数会将页面置为脏页。先将其转换为 BPlusTreePage，然后再根据页面类型，将其转换为内部节点或叶子节点，注意 BPlusTree 类中已经为我们提供了别名：

1
2

using InternalPage = BPlusTreeInternalPage<KeyType, page_id_t, KeyComparator>;
using LeafPage = BPlusTreeLeafPage<KeyType, ValueType, KeyComparator>;

一开始我没有注意，在对内部节点转换时，误将其 page_id_t 转为 ValueType，导致完全误解了整个项目的结构。

⑤ 分裂叶子节点和内部节点时，注意判断当前节点是否是根节点。我们可以在 BPlusTreeInternalPage 和 BPlusTreeLeafPage 中添加 Split 函数，来实现分裂。

叶子节点的分裂操作比较简单，就是移动然后设置大小，为了不让页面类和其他类耦合（BufferPoolManager，Context），我将分裂函数的参数设计为 BPlusTreeInternalPage &new_page，它会返回将插入到上层的 key，即新节点的第一个 key。

内部节点的分裂操作比较复杂，并发测试时遇到边界样例才发现，因为内部节点的分裂是插入前分裂，所以还需要考虑插入的那个键的大小。如果 key 比 array_[GetMinSize() - 1] 小，则插入到当前节点，否则插入到新分裂的节点。并且，在插入新分裂的节点时，可能会插入到索引为 0 的位置，这一点要特别注意。最后，也是返回新节点的第一个 key（指的是 array_[0].first，因为分裂的时候复制了）。

⑥ 同理，在内部页面和叶子页面类中可以添加 Insert 函数。需要注意的是，这两个函数的实现有些点不同。对于内部节点，当 B+Tree 的根节点分裂时，该情况会将 page_id 插入到内部节点的第一个没有键的位置，所以我们可以将参数设计为 const std::optional<KeyType> &opt 来区分这种情况。对于叶子节点，由于不能有相同的键，所以根据 Search 的实现，当 index ≥ 0 时返回 false，否则继续插入。

调试

调试时可以先使用可视化网站查看 B+ 树，方便定位问题，我们可以使用 shell 脚本一键生成文件（解决方案）：

1
2
3

#!/bin/bash
make b_plus_tree_printer -j$(nproc)
{ echo 2 3; echo i 1; echo i 2; echo g my-tree.txt; echo q; } | ./bin/b_plus_tree_printer

在生成文件时可能会报 [b_plus_tree.cpp:356:Draw] WARN - Drawing an empty tree 错误，原因是我们没有实现 b_plus_tree.cpp 中的 IsEmpty 函数。

补充

① 如何使用 upper_bound 和 lower_bound（Java 选手表示踩了很多坑），可以看看 cppreference 的示例代码，尤其注意 lambda 表达式的使用（参数顺序，以及大小的比较）。

② 测试时忽略 iterators 的测试。

③ GetValue 注意特判根节点是否存在，否则可能引发空指针异常（依赖于 BufferPoolManager 的实现）。

Task #2b - B+Tree Deletions

实现

① 删除操作可以分为两种情况，相邻节点重新分配和相邻节点合并。进一步可以划分为操作当前节点的左节点，还是右节点。需要注意的是，我们只有对相同父节点的两个子节点执行上述操作，一个非根节点必定有一个同父的左节点或右节点。（如果不这样限制，实现起来会很麻烦，需要找到最近公共祖先，做键值的替换。）为了能够获取左右节点的页面，我们在从上到下找 key 对应的页面时，可以同时保存左右页面的 page_id。

② 重新分配操作，需要区分左右。如果从右节点取，则需要更新右节点对应父节点中的 key；如果从左节点取，则需要更新当前节点对应父节点中的 key。操作完可以直接返回。

③ 合并操作同理，只不过不是更新，而是删除对应父节点中的 key（递归删除）。注意，如果合并叶子节点，需要同时更新 next_page_id_。（合并之后右侧的页面永远都不会被使用，或许需要对其执行 DeletePage 操作，在 DeletePage 之前需要 Drop/Unpin 页面。有个疑问，DeletePage 之前 Drop 之后，如果有线程 Fetch，那么删除页面的操作就会失败。）

调试

实现的思路弄明白后，大方向上就不会出错，但是很多细节容易写错：变量名字，重复执行 pop_back() 操作，删除页面后对页面进行操作等等。不过，说实话官方提供的可视化类真好用，Debug 全靠可视化来定位问题。磨磨蹭蹭，花费一天时间，做得有点慢。

Task #3 - An Iterator for Leaf Scans

基本上没有难度，遇到唯一的错误就是把 GetSize 打成了 GetMaxSize（因为用的自动补全）。

Task #4 - Concurrent Index

① 遇到问题，先定位它是什么问题。首先，应该解决非并发问题，我们可以在插入和删除的开头加一把大锁，然后利用并发测试 MixTest2，来混合查找、插入和删除操作，看看是否存在问题。为了尽可能引发问题，可以将叶子节点和内部节点的最大大小修改为 2 3，将 total_keys 修改为 1000，尽可能的触发分裂和合并操作（这个测试，比线上测试还强，多跑几次线上能过的给报错了）。在混合时，可以分别混合查找和插入，查找和删除，插入和删除，这样方便定位问题出在哪里。然后，再去进行并发优化，一点一点优化，边优化边测试，这样就不会因为找不到 Bug 的位置而发愁啦。

② 遇到错误，[disk_manager_memory.h:104:ReadPage] WARN - page not exist，发现是 BufferPoolManager 的 Bug，需要跑回去修复。一天后，终于真正的把 Bug 修好了，代码也稍微重构了一下，哈哈，真的 99% 不会报错（有个 FetchPageBasic/Read/Write 返回 nullptr 的错误没修复，报错概率很低，以后有问题再修），不得不说本地测试用例修改后是真的强劲，线上强度不够啊。（但是重构了个寂寞，效率没变，难受啊）

③ B+Tree 的并发问题其实基本没有，都是单线程问题或者 BPM 的并发问题，B+Tree 的并发只要注意 Fetch 和 Drop 的顺序就 OK。

(Optional) Leaderboard Task

① 初次提交通过，排名还挺高。额，多次提交能差七八万。感觉测试有问题，平均 QPS 也就十万多。

② 优化暂时搁置。

测试结果

Checkpoint #1 说简单也不简单，感觉有些细节总是写错，包括下标的处理，C++ 二分查找函数的使用，变量名称，以及一些边界条件。说难也不难，线上测试首次提交就通过了。总共花了一天半吧。

Checkpoint #2 总共花了两天，任务三四没什么难度，主要时间还是在删除操作，以及修复插入操作中的 Bug。

1
2
3
4
5
6
7
8
9
10

#!/bin/bash
make b_plus_tree_insert_test b_plus_tree_sequential_scale_test b_plus_tree_delete_test b_plus_tree_concurrent_test -j$(nproc)
./test/b_plus_tree_insert_test
./test/b_plus_tree_sequential_scale_test
./test/b_plus_tree_delete_test
./test/b_plus_tree_concurrent_test
make format
make check-lint
make check-clang-tidy-p2
make submit-p2

项目小结

开始做项目之前，对插入和删除具体怎么操作还是比较迷糊的，实际实现起来发现原来是这样的。特别需要注意别打错变量名，我用自动补全总是搞混 MaxSize 和 MinSize，还有各种变量都敲错，运行起来找 Bug 就头疼了。还要注意，内部节点和叶子节点分裂的时机不同，实现也不同，以及在分裂时如何对待内部节点的第一个 key。然后删除操作就是个分类讨论，弄明白就不难了。并发错误我也真是见识到了，BPM 优化需谨慎啊。（做得还是很慢，对大佬来说，其实就是个复杂点的模拟题吧）