15445 面经（？

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

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

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

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

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

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

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

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

B-tree、B+tree 对比红黑树

核心在于缓存友好，申请内存操作是耗时的，我们希望次数尽可能少，还希望想找的几条数据最好挨在一起，因此更大节点的 B-tree 会比红黑树更好。

缓存利用率：由于 B+ 树节点较宽，单次磁盘读取可以加载较多的关键字到内存中，这样在进行查找时，每次磁盘 I/O 可以获得更高的关键字命中率，进而提高整体性能。
磁盘 I/O 效率：B 树和 B+ 树设计时考虑到了减少磁盘 I/O 操作的需求，因为它们允许每个节点拥有多个子节点，从而降低了树的高度。相比之下，红黑树作为二叉树的一种，其高度相对较高，在处理大量数据时会导致更多的磁盘访问。

上述理由同样合适于 rust 的 TreeMap 为什么采用 B-tree 而不是红黑树？。

范围查询其实是 B+tree 的特性，跟 B-tree 这个系列不太有关。

范围查询：B+ 树中的所有叶子节点都通过指针相连，支持高效的范围查询。而在红黑树中进行范围查询则可能需要多次独立的查找，效率较低。

B+tree 对比 B-tree

B+tree 主要优化了节点大小，同时有了范围查询，

缓存友好性：B+ 树的内部节点仅用于索引，这使得它们能容纳更多键值对，有助于降低树的高度并减少 I/O 操作次数。同时，这种结构对于现代计算机系统的缓存机制更加友好。
范围查询优化：B+ 树的叶子节点之间通过指针相连，极大地优化了范围查询的效率。而 B 树虽然也能进行范围查询，但效率不如 B+ 树高。

查询效率上不能说好了多少，只能说有些理由是扯出来的（比如查询效率一致性会更好，因为每次都稳定地查到叶子节点，而 B-tree 则会提前返回，这合适吗？）。

这里仍然可以参考 rust 的 TreeMap，为什么用 B-tree 而不是 B+tree 了，因为 B-tree：

优势：省内存，不需要多做一层索引。
劣势：Iter 略慢，next() 最差会出现 log n 的复杂度，B+Tree 可以稳定 O(1)。
劣势：不能区分 index 和数据，也就不能把 index 做的很小，放进更快但是更小的存储中。

首先 Rust 的 BTreeMap 是全放在内存里的，第三条基本上就没啥用，第二条的性能提升微乎其微，但是第一条的省内存可是实实在在的，所以 B+Tree 在这个使用场景下 GG。

B+tree 对比 LSM tree

写入性能：LSM 树（Log-Structured Merge Tree）在写入密集型应用中通常表现更好，因为它将写操作批量处理后合并到较大的排序文件中，减少了随机写入的数量。而 B+ 树在写入时可能会涉及到节点分裂，导致更多的随机 I/O 操作。
读取性能：B+ 树一般提供更稳定的读取性能，尤其是对于点查询而言，而 LSM 树为了达到较高的写入性能，可能需要在读取时检查多个文件或执行合并操作，增加了读取延迟。
空间开销：LSM 树可能会有较高的空间开销，因为它需要维护多层的文件结构以及定期进行压缩以控制空间增长。而 B+ 树的空间利用率相对更高，特别是在更新操作较少的应用场景下。

希望这些对比能够帮助你更好地理解为什么在某些情况下选择 B+ 树是更有利的。

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 锁机制笔记

什么是幻读？