大家好，我是大头，职高毕业，现在大厂资深开发，前上市公司架构师，管理过10人团队！
我将持续分享成体系的知识以及我自身的转码经验、面试经验、架构技术分享、AI技术分享等！
愿景是带领更多人完成破局、打破信息差！我自身知道走到现在是如何艰难，因此让以后的人少走弯路！
无论你是统本CS专业出身、专科出身、还是我和一样职高毕业等。都可以跟着我学习，一起成长！一起涨工资挣钱！
MySQL零基础教程
本教程为零基础教程，零基础小白也可以直接学习。
基础篇和应用篇已经更新完成。
接下来是原理篇，原理篇的内容大致如下图所示。
零基础MySQL教程原理篇之缓冲池实现
MySQL中的buffer pool(缓冲池)是InnoDB存储引擎的重要组件，它负责在内存中管理数据库中的数据和索引的缓存。
它加速了数据库的运行速度，是数据库和磁盘之间的一个中间层。如果没有缓冲池，那么所有的数据库操作都需要进行磁盘IO，有了缓冲池，就不需要频繁的IO操作了。
本次我们的目标是使用C++实现一个缓冲池，这也是CMU15445这门课的Project1。
基于BusTub学术数据库管理系统构建一个面向磁盘的存储管理器。在这样的存储管理器中，数据库的主要存储位置在磁盘。
缓冲池负责在主内存和磁盘之间来回移动物理页面。它允许数据库管理系统支持比系统可用内存量更大的数据库。缓冲池的操作对系统其他部分是透明的。
例如，系统使用其唯一标识符 （ page_id_t ）向缓冲池请求一个页面，它不知道这个页面是否已经在内存中，或者系统是否需要从磁盘中检索它。
实现需要是线程安全的。多个线程将并发访问内部数据结构，并且必须确保它们的临界区受到latches的保护（在操作系统中这些被称为“锁”）。
实现总共分为三个部分：
- 实现LRU-K淘汰策略
- 实现磁盘调度程序
- 实现缓冲池管理器
实现LRU-K淘汰策略
关于LRU-K淘汰策略的一些信息可以看上一篇文章零基础MySQL教程原理篇之缓冲池原理及实现
本次实现主要都在这两个文件中：
- 头文件
src/include/buffer/lru_k_replacer.h - 实现文件
src/buffer/lru_k_replacer.cpp
LRU-K 算法会淘汰替换器中反向 k 距离最大的页帧。反向 k 距离是指当前时间戳与第 k 次先前访问的时间戳之间的时间差。少于 k 次历史访问的页帧其反向 k 距离被赋予+inf。当多个页帧具有+inf 反向 k 距离时，替换器会淘汰具有最早整体时间戳的页帧（即记录访问最久远的页帧，在所有页帧中整体上最不常被访问的页帧）。
LRUKReplacer 的最大大小与缓冲池的大小相同，因为它包含了 BufferPoolManager 中所有页帧的占位符。然而，在任意时刻，替换器中的所有页帧并非都被视为可被淘汰。 LRUKReplacer 的大小由可被淘汰页帧的数量表示。 LRUKReplacer 被初始化为空。只有当页帧被标记为可被淘汰时，替换器的大小才会增加。
总共要实现以下方法：
- Evict(frame_id_t* frame_id):将与所有其他被跟踪的可淘汰帧相比具有最大向后k距离的帧驱逐。将
帧id存储在输出参数中并返回 True 。如果没有可淘汰帧，则返回 False 。 - RecordA***ess(frame_id_t frame_id)：记录给定帧 id 在当前时间戳被访问。此方法应在页面被固定在
BufferPoolManager后调用。 - Remove(frame_id_t frame_id)：清除与帧关联的所有访问历史。此方法仅在页面被删除在
BufferPoolManager时调用。 - SetEvictable(frame_id_t frame_id, bool set_evictable): 此方法控制帧是否可被淘汰。它还控制
LRUKReplacer的大小。当您实现BufferPoolManager时，您将知道何时调用此函数。具体来说，当页面的固定计数达到 0 时，其对应的帧被标记为可淘汰，并且替换器的大小增加。 - Size()：该方法返回当前在
LRUKReplacer中的可淘汰帧数。
你可以假设不会内存耗尽，但你必须确保你的实现是线程安全的。
以上是实现要求.
接下来讨论一下实现的思路。关于LRU-K在数据库中的实现有一篇论文可以参考一下LRU-K
先来看RecordA***ess方法吧，这个方法算是比较简单的了，也是整个LRU-K算法的入口方法，因为每次访问一个page，都需要调用该方法。
首先，我们可以看到在头文件中有LRUKNode的一个类型定义：
