15445 面经（？
这里应该会记录单机数据库内核开发的相关面经。
你是怎么实现 LRU 的，实现过程中大概用了什么数据结构？
什么时候对内存中的帧 frame bitmap - 1 操作，也就是 unpin？
实现 B+ 树索引用到了什么数据结构，你能简单说说吗？
如何从 B+ 树中删除一个节点，并保证树的平衡。
什么是 Executor 火山模型，结合 Select 说说？
你能说说怎么实现 Nested Loop Join，Hash Join 的？
看你提到了死锁避免算法，那你说说什么是死锁？
BufferPool 中脏数据如何写入（flush）磁盘？
什么场景下使用 B+ 树更适合？
B+ 树的优缺点是什么？
介绍一下 Executor 火山模型？有什么优缺点？如何改进？（优化算子树、改用 Pipeline 模型）
介绍一下 Pipeline 模型？为什么相比火山模型更快？（可以跑满 CPU 流水线）
你知道 Pipeline 有哪些具体的应用吗？（Doris 和 Tiflash）
Tiflash 是函数下推，为什么要函数下推？（列式向量计算、让计算和存储更接近）
介绍 ...
raft 面经（？
按理说，做完了 6.824 理应对 Raft 了如指掌，可那是 11 个月前了，如今的笔者只能依稀记起来 lab 中印象较深的几个坑（其实也记不太清了。
所以可证明，做完 lab ≠\not== 面经全会。
为了让面试官不阴阳怪气\委婉\盛气凌人地跟笔者说——同学，你的项目是有借鉴 Github 吗？——记录一下笔者从各大网站搜罗而来的 Raft 协议面经。
CAP 是什么？Raft 实现了 CAP 中的哪两个
CAP（Consistency, Availability, Partition tolerance）。CA 只有单机实现，毕竟分布式系统必须有 Partition tolerance。
弱一致性——最终一致性（无法实时获取最新更新的数据，但是一段时间过后，数据是一致的）
Gossip(Cassandra，Redis 的通信协议)
优先保证 AP 的 CouchDB，Cassandra，DynamoDB，Riak（一个都不了解）
强一致性
Paxos
Raft
ZAB
据 PingCAP 所分享：
一些常见的误解：使用了 Raft 或者 paxos 的 ...
codetop 100 题（暂定）思路笔记
两数之和
题目条件说答案唯一，hash 表存 target-x 即可。
时间：O(N)O(N)O(N)，空间：O(N)O(N)O(N)
三数之和
基本思路是遍历数组对每个值求两数之和，易知时间复杂度必为O(N2)O(N^2)O(N2)。
题目要求答案不可重复，但是数组中会出现重复值，如[1,2,-3,2]，使用 hash 表扫一遍还要去重，所以不使用 hash 表。
因此先排序，再使用双指针从两端遍历，双指针可以跳过重复的值。
时间：O(NlogN)O(NlogN)O(NlogN)+O(N2)O(N^2)O(N2)=O(N2)O(N^2)O(N2)，空间：O(1)O(1)O(1)
最大连续子序（子数组）和
给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
DP
DP 最优，遍历一遍，直观理解是当前序列之和<0 就可以从下一个大于 0 的元素开始继续遍历，转移方程为：
f(i)=max{f(i−1)+nums[i],nums[i]}f(i)=max\{f(i-1)+nums[i],nums[i]\}
f(i)=m ...
CMU15445 C++ 学习笔记 - 其三（Project 2）
array_ 是零长数组，解释参见（https://blog.csdn.net/gatieme/article/details/64131322）初始化的时候在内存里是不占空间的，但是它真正能使用到的空间就是固定的 page 大小减去前面成员变量之后所剩的空间。因为实际上 BUCKET_ARRAY_SIZE 是固定的，为了不使内存溢出，注释也强调了不要在下面再加别的成员了（所以挺困惑我的一点就是既然总的 page 空间大小和数组 size 都定下来了，为什么不直接在初始化的时候就申请那么大的空间呢）
CMU15445 C++ 学习笔记 - 其二（Project 1）
0.png
大力出奇迹，函数大锁。
1.png
修改了 NewPage，在写入 Evict 的页释放了函数大锁，主要目的是测试 bug。
2.png
在 FlushPage 的时候释放函数大锁加页锁，在 DeletePage 写入 Delete 的页时释放了函数大锁，结果更差了。
3.png
// 分配一个空闲 block；
// buf_pool_mutex_enter；
// 持有 page_hash x lock；
// 检查 page_hash 中是否已被读入，如果是，表示另外一个线程已经完成了 io，则忽略本次 io 请求，退出；
// 持有 block->mutex，对 block 进行初始化，并加入到 page hash 中；
// 设置 IO FIX 为 BUF_IO_READ；
// 释放 hash lock；
// 将 block 加入到 LRU 上；
// 持有 block s lock；
// 完成 IO 后，释放 s lock；
CMU15445 C++ 学习笔记 - 其一（Project 0）
换设备了之后 hexo 源文件丢失了，笔者竟然忘记（没意识到）可以在 github 仓库里新开一个 hexo branch 存放源文件。
前言
这篇文章里写好的注册课程提交课程流程笔者就不写了。
CMU 15-445/645 (Spring 2023) Database Systems 通关指北
笔者想学 C++ 但找不到做完会有成就感的项目所以一直耽搁着没学，Modern C++ 的名声在外让笔者同样畏惧。虽然笔者看了许多 C++ 的源码也学会了不少语言，但是 Modern C++ 这座大山一直没敢爬，这是本科的情况。
所以，在研究生的第一年，趁还有三年可供摆烂的时间，开始攀登这座大山。
当头一棒捏
Project 0
笔者做的是 2023 年 Fall 的课程，要是笔者能坚持下去的话，大概能和 CMU 的同学们同一时间完成它。
P0 的题目是手写 Trie 树以及利用 Copy-On-Write 让 Trie 树可以同时被多个 Reader 和一个 Writer 访问，这个在原理实在算不上难。让笔者头疼的是 Modern C++ 的语法。现记录如下，可供有一点基础（指除编程 ...
记一次折腾 J1900 的经历
第一次整软路由，笔者正处于大创报账时期，虽然不知道能不能报上去，反正挑了个合适价位的 J1900 的软路由买回来一阵折腾。由于怀着着折腾的心思，买的是裸主机，这意味着内存和硬盘都没有自带，同时 openwrt 系统就更不用说了，肯定得自己装上去。在收货当天笔者就开始了各项工作，结果还是花了好几天踩坑才将一切搞定，故记下这次极其耗神的工作。
软路由是什么
按笔者目前理解，软路由就是一台至少带了多个网口的过时主机，CPU、内存、硬盘等基本一应俱全。笔者手里这台就是 J1900CPU、四网口的一台软路由，双十二期间价钱 720+ 就拿下来了。
拥有复数个网口后，只要在主机上装一个 openwrt 系统，再给网口分配 LAN 口和 WAN 口，这台主机就是软路由了。换言之，只要有两个网口，任何电脑都可以改成软路由，只是功耗等不尽相同罢了。
与软路由相对的就是——硬路由，也就是一般我们称呼的路由器，软路由一般应用在有线网中，至于无线网则会靠额外连接一个无线 AP 来实现，而硬路由则集成这两项功能且更简单易用，当然价钱多少会高上一点。
J1900 路由器介绍
先来张内部结构图：
图中的已经 ...