Welcome to my blog! 👋

这个 project 主要是希望我们理解 MVCC 的一些相关知识。MVCC 的设计目标是通过维护多个版本的元组（tuple），使得不同的事务能够访问到与其时间戳一致的数据版本，而无需通过锁机制完全阻塞其他事务的操作。具体来说： 每个事务在启动时会被分配一个唯一的 事务 ID 或 读取时间戳 。 数据库系统会根据事务的读取时间戳，决定该事务能看到哪些数据版本： 可见性规则 ：事务只能看到在其读取时间戳之前提交的数据版本。 不可见性规则 ：事务不能看到在其读取时间戳之后提交或未提交的数据版本。 15445 的 lab 写了太久太久了，自己懒是一方面，实力不够也是一方面，task4 后面的 lab 就不打算写了（无奈.jpg）。在这整个过程中，学到的东西还挺多的，对于代码能力也有提升，以后有时间还是可以多看看配套的课程，然后再好好读读代码，写写注释和博客去深入理解理解，毕竟 bustub 的不论是代码架构还是规范我都觉得非常棒。后面就要像 15445 网页中写到的，去多关注生活中其他感兴趣的地方了，希望能够不断提升自己~ 0. Bustub 中的 undolog bustub 中在 TransactionManager 中通过一个哈希表来保存所有 tuple 的 undolog 起点： class TransactionManager { public: ... struct PageVersionInfo { /** protects the map */ std::shared_mutex mutex_; /** Stores previous version info for all slots. Note: DO NOT use `[x]` to access it because * it will create new elements even if it does not exist....

https://leetcode.cn/problems/koko-eating-bananas/ 假设每小时吃 max(piles) 根香蕉，那么按照题意（向上取整）来说就只要 piles.length 个小时就可以吃完。而注意提示中的：piles.length <= h <= 10^9，这说明每小时吃 max(piles) 根香蕉已经是最大的速度了，再快也没用了。因此需要去找比 max(piles) 小的且满足题意的数。 那取 max(piles) 作为右边界，左边界取 1 （因为总不可能不吃吧~），然去通过二分去找最小的满足条件的速度。 class Solution { public: int minEatingSpeed(vector<int>& piles, int h) { int left = 1, right = *ranges::max_element(piles); auto check = [&](int x) { long long sum{}; for (int p : piles) { sum += (p + x - 1) / x; } return sum <= h; }; while (left <= right) { int mid = (left + right) >> 1; if (check(mid)) { right = mid - 1; } else { left = mid + 1; } } return left; } }; 相似题目：...

C++17 为模板元编程带来了一个非常有用的特性：折叠表达式（fold expressions）。它的出现让变参模板函数的编写变得更加简洁、清晰和直观。 1. 如何处理变长参数包 在 C++11/14 中，如果我们要处理变长参数包（parameter pack），通常需要递归展开，例如： template<typename T> void print(const T& t) { std::cout << t << '\n'; } template<typename T, typename... Args> void print(const T& t, const Args&... args) { std::cout << t << ", "; print(args...); } 虽然这段代码能完成任务，但却略显冗长，并且生成的汇编代码也会很多。C++17 中引入的折叠表达式，就是为了解决这个问题。 可以在 godbolt 上看看两种方法生成的汇编代码：https://godbolt.org/z/55a7q85oE 2. 什么是折叠表达式 折叠表达式是一种用运算符对参数包进行折叠的方式。折叠表达式的实例化按以下方式展开成表达式 e： （图片来源：https://zh.cppreference.com/w/cpp/language/fold） 基本语法形式： 类型 语法形式 示例 一元左折叠 (... op pack) (... + args) 一元右折叠 (pack op ...) (args + ...) 二元左折叠 (init op ....

在 C++20 及更高版本中，可以使用 Concepts 来替代传统的基于虚函数的接口设计，这种方式提供了更好的编译时检查、更高效的代码生成和更灵活的接口约束。 在之前，可能是这样的： class IDrawable { public: virtual ~IDrawable() = default; virtual void draw() const = 0; }; class Circle : public IDrawable { public: void draw() override { puts("Circle::draw()"); } }; class Squre : public IDrawable { public: void draw() override { puts("Squre::draw()"); } }; void render(IDrawable& drawable) { drawable.draw(); } 但是有了 Concept 后： template <typename T> concept Drawable = requires(T t) { { t.draw() } -> std::same_as<void>; }; class Circle { public: void draw() const { puts("Circle::draw()"); } }; class Squre { public: void draw() { puts("Squre::draw()"); } }; template <Drawable T> void render(T& drawable) { drawable....

最近 Fedora42 更新了，因此我打算升级一下玩玩。在执行完下面的命令后： sudo dnf upgrade --refresh sudo dnf system-upgrade download --releasever=42 sudo dnf system-upgrade reboot 重启开机成了这样:( 在网上搜索一圈后，执行以下命令系统就 ok 了： sudo dracut --regenerate-all --force 错误的原因可能是更新内核后没有正确生成新的 initramfs 文件，系统可能会使用旧的、不兼容的 initramfs 文件，从而导致启动失败。 而 dracut 是一个用于生成 Linux 系统 initramfs（初始内存文件系统）的工具。运行 这条命令后，dracut 会重新生成与当前系统中所有已安装内核对应的 initramfs 文件。 参考：https://www.reddit.com/r/Fedora/comments/1hfkqnq/boot_error_after_updating_to_6124200

https://leetcode.cn/problems/closest-equal-element-queries/ 通过示例1来分析： 输入： nums = [1,3,1,4,1,3,2], queries = [0,3,5] 输出： [2,-1,3] 对于queries[0] = 0, nums[queries[0]] = 1来说，其在nums中的下标集合为p = [0, 2, 4]，由于nums是一个循环数组，所以按理来说数组p的第一个元素往左需要能找到最后一个元素，最后一个元素往右能找到第一个元素。 n 为 nums 的长度， 在下标列表前面添加 4−n=−3，相当于认为在 −3 下标处也有一个 1。 在下标列表末尾添加 0+n=7，相当于认为在 7 下标处也有一个 1。 题意是需要我们查询一个 nums 中的下标 x，与 任意 其他下标 j（满足 nums[j] == nums[x]）之间的 最小 距离。我们用哈希表将每个相同值的元素的下标收集起来作为集合 p，然后在查询时使用二分查询 x 在其对应集合中的位置 i，则左边最近的元素下标为 p[i - 1]，右边最近元素下标为 p[i + 1]，那么最小距离就是 min(p[i + 1] - x, x - p[i - 1])。 class Solution { public: vector<int> solveQueries(vector<int>& nums, vector<int>& queries) { unordered_map<int, vector<int>> m; int n = nums....

在C++中，编译器会根据类的定义情况自动决定是否生成默认的特殊成员函数（如构造函数、拷贝/移动操作、析构函数）。 1. 用户显式声明相关成员函数 显式声明或删除某个函数： 如果用户显式声明（即使使用 =default 或 =delete）某个特殊成员函数，编译器将不再生成默认版本。例如： class Example { public: Example() = default; // 允许生成默认构造函数 Example(const Example&) {} // 用户定义的拷贝构造函数 // 编译器不再生成默认的移动构造函数和移动赋值运算符 }; 2. 用户定义析构函数、拷贝/移动操作的影响 定义析构函数： 如果用户定义了析构函数（即使为空），编译器会删除默认的移动操作（移动构造函数和移动赋值运算符），但拷贝操作仍可能生成（除非其他条件阻止）。 class Example { public: ~Example() {} // 用户定义的析构函数 // 移动操作被隐式删除，拷贝操作可能生成（若无其他限制） }; 定义拷贝操作： 如果用户定义了拷贝构造函数或拷贝赋值运算符，编译器会删除默认的移动操作。 class Example { public: Example(const Example&) {} // 用户定义的拷贝构造函数 // 移动操作被隐式删除 }; 定义移动操作： 如果用户定义了移动构造函数或移动赋值运算符，编译器会删除默认的拷贝操作。 #include <utility> #include <string> #include <iostream> struct Example { std::string str; Example() = default; Example(const std::string& s): str(s) { std::cout << "Example()\n"; } Example(Example&& other) { str = std::move(other....

该系列博客只是为了记录自己在写 Lab 时的思路，按照课程要求不会在 Github 和博客中公开源代码。欢迎与我一起讨论交流！ 这个 project 和之前就不一样了，开始深入数据库内核的实现了。需要理清楚一条 sql 语句是如何被执行的，方才能写出代码。 前置奶酪 一条 SQL 语句的执行 这里需要去看看一条 sql 语句传入 bustub 内部之后的代码：src/common/bustub_instance.cpp:ExecuteSqlTxn： auto BustubInstance::ExecuteSqlTxn(const std::string &sql, ResultWriter &writer, Transaction *txn, std::shared_ptr<CheckOptions> check_options) -> bool { if (!sql.empty() && sql[0] == '\\') { // 处理元命令 ... } // binder，但是在其中会使用libpg_query来解析sql语句 bustub::Binder binder(*catalog_); binder.ParseAndSave(sql); // 经过上一步后，binder中的statement_nodes_存储着所有的语句解析节点 for (auto *stmt : binder.statement_nodes_) { // 将stmt转换成BoundStatement对象，方便后面处理数据 auto statement = binder.BindStatement(stmt); // 只有不需要构建plan树、不需要进行优化的sql语句才会在switch之后继续执行 switch (statement->type_) { ... } // 生成初步的执行计划 bustub::Planner planner(*catalog_); planner....

最近把博客的构建工具从Hexo换成了Hugo，感觉Hugo配置和使用起来更简洁方便。 由于我的博客总体来说有两个仓库，一个私有仓库是放置建站工具的目录，其中包含博客 Markdown 内容、一些配置还有主题；另一个就是通过 GitHub Pages 来访问公共仓库。为了方便，之前在使用 Hexo 的使用使用了 Github Actions 来一键部署博客，换成 Hugo 后这个 actions 需要修改一下。 .github/workflows/hugo.yml： name: GitHub Pages on: push: branches: - master # 监听 master 分支的推送事件 pull_request: jobs: deploy: runs-on: ubuntu-latest steps: - uses: actions/checkout@v3 with: submodules: true # 拉取 Hugo 主题子模块 fetch-depth: 0 # 获取完整提交历史 - name: Setup Hugo uses: peaceiris/actions-hugo@v2 with: hugo-version: '0.126.2' extended: true - name: Build run: hugo --minify # 启用压缩优化 - name: Deploy uses: peaceiris/actions-gh-pages@v3 with: personal_token: ${{ secrets....

微信在不久前终于有了Linux原生版本，我的电脑是Fedora41，之前安装的是flatpak打包的微信，现在在官网下载rpm包后运行发现无法使用fcitx的中文输入法，找了一下是环境遍历的问题。 ...