15445 面经（？

这里应该会记录单机数据库内核开发的相关面经。

LRU 算法，LRU 刷盘时一致性的保证 (考虑到宕机的情况) 参考 mysql

你是怎么实现 LRU 的，实现过程中大概用了什么数据结构？

LRU 与 LFU 的区别以及后续的优化

LRU-K 算法、Mysql 的 LRU 有 young、old 区域优化。

实现 B+ 树索引用到了什么数据结构，你能简单说说吗？

如何从 B+ 树中删除一个节点，并保证树的平衡。

为什么要用 B+ 树而不用其它的树如红黑树？B+ 树有什么优势？什么场景下使用 B+ 树更适合？B+ 树的优缺点是什么？

详情见 The Difference Between B-Tree, B+Tree, Red-Black Tree, LSM Tree and SkipList。

B+ 树执行操作时是如何加锁的？

考虑节点分裂和合并

什么时候对内存中的帧 frame bitmap - 1 操作，也就是 unpin？

看你提到了死锁避免算法，那你说说什么是死锁？

你知道死锁出现的 4 个前提条件吗？

回答：互斥条件、请求和保持条件、不可剥夺条件、循环和等待条件

你是如何使用 Wound-Wait 算法预防死锁的？

回答的核心是：不要让线程一直等待，如果一直等待则需要根据 Wound-Wait 算法 Kill 掉相关线程。

老读不杀新读，老读杀新写，老写通杀。

什么是死锁？你是如何实现全局的 Lock Manager 管理 R/W 锁，如何使用 Wound-Wait 算法避免死锁的？

Wound-Wait 算法避免死锁时如何避免某些线程饥饿状态，即某些线程经常性的被 Kill？

BufferPool 中脏数据如何写入（flush）磁盘？Mysql 怎么说？

什么是 Executor 火山模型，结合 Select 说说？

介绍一下 Executor 火山模型？有什么优缺点？如何改进？（优化算子树、改用 Pipeline 模型）

介绍一下 Pipeline 模型？为什么相比火山模型更快？（可以跑满 CPU 流水线）

你知道 Pipeline 有哪些具体的应用吗？（Doris 和 Tiflash）

Tiflash 是函数下推，为什么要函数下推？

列式向量计算、让计算和存储更接近

你能说说怎么实现 Nested Loop Join，Hash Join 的？

介绍一下 Hash Join 是怎么实现的？

追问：有没有考虑过 Hash 对 id/key 进行散列后得到的值很分散，那么得到的 Hash Table 很大，内存占用会很大？你的测试数据集规模有多大，有做过压测吗？查看实际的内存占用。

回答：换用其它 Hash 函数，被面试官说并不是 Hash 函数的问题。

Hash Join 是一种用于数据库管理系统中实现连接操作的有效方法，特别适用于大型数据集。其基本思想是利用哈希函数将参与连接的两个表中的记录根据连接键（join key）进行分类，以便快速找到匹配的记录。

Hash Join 的实现步骤大致如下：

构建阶段 (Build Phase)：选择较小的输入（如果大小已知），使用连接键作为哈希函数的输入，对这个输入构建一个哈希表。每个键值对应的数据项会被插入到哈希表中相应的桶 (bucket) 里。
探测阶段 (Probe Phase)：对另一个较大的输入，再次使用相同的哈希函数处理其连接键，并尝试在之前构建的哈希表中查找对应的桶来找到匹配的记录。一旦找到匹配，就产生输出结果。

关于你的追问

当你提到“有没有考虑过 Hash 对 id/key 进行散列后得到的值很分散，那么得到的 Hash Table 很大，内存占用会很大？”的问题时，实际上涉及到了 Hash Join 的一个潜在挑战——内存使用效率。然而，面试官指出这不是哈希函数本身的问题，而是其他因素导致的。

不是哈希函数的问题：这意味着问题不在于哈希函数的选择或设计上（例如，哈希函数的均匀性）。即使是最理想的哈希函数，也无法解决所有与内存相关的挑战。
可能的问题所在：
- 数据倾斜 (Data Skew)：这是指某些键比其他键具有更多的记录，这会导致这些键所在的哈希桶变得非常大，从而消耗大量的内存。
- 内存限制：当数据量极大时，即使是高效的哈希表也可能因为物理内存的限制而无法容纳所有的桶和数据。
- 分区策略：有时需要考虑如何有效地将数据划分成更小的部分来处理，以避免单个节点上的内存溢出。

因此，面试官所说的“不是 hash 函数的问题”指的是解决方案不应仅仅集中在改变哈希函数上，而应该更多地关注于如何处理数据倾斜、优化内存管理策略以及合理设计分区算法等方面。对于测试数据集规模和压测的实际经验，这通常依赖于具体的应用场景和系统配置，但重要的是理解上述概念并能够灵活应用到不同的情况中。

所以怎么解决数据倾斜呢，我也不知道。以后再问问 ai。

如何实现三种隔离级别？（RU、RC、RR）

参考 Mysql 锁机制笔记

什么是幻读？