如果Buffer Pool中的缓存页不够了，如何淘汰部分缓存？

1、如果Buffer Pool中的缓存页不够了怎么办？

当要执行CRUD操作的时候，无论是查询数据，还是修改数据，实际上都会把磁盘上的数据页加载到缓存页里来，在加载数据到缓存页的时候，必然是要加载到空闲的缓存页里去的，所以必须要从free链表中找一个空闲的缓存页，然后把磁盘上的数据页加载到那个空闲的缓存页里。随着不停的把磁盘上的数据页加载到空闲的缓存页里去，free链表中的空闲缓存页是不是会越来越少？因为只要把一个数据页加载到一个空闲缓存页里去，free链表中就会减少一个空闲缓存页。

当不停的把磁盘上的数据页加载到空闲缓存页里去，free链表中不停的移除空闲缓存页，迟早有那么一瞬间，会发现free链表中已经没有空闲缓存页了这个时候，还要加载数据页到一个空闲缓存页的时候，怎么办呢？如下图：

2、如果要淘汰掉一些缓存数据，淘汰谁？

如果所有的缓存页都被塞了数据了，此时无法从磁盘上加载新的数据页到缓存页里去了，那么此时只有一个办法，就是淘汰掉一些缓存页。

那什么叫淘汰缓存页呢？

顾名思义，必须把一个缓存页里被修改过的数据，给它刷到磁盘上的数据页里去，然后这个缓存页就可以清空了，让它重新变成一个空闲的缓存页。接着再把磁盘上需要的新的数据页加载到这个腾出来的空闲缓存页中去，如下图。

那么下一个问题来了，如果要把一个缓存页里的数据刷入磁盘，腾出来一个空闲缓存页，那么应该把哪个缓存页的数据给刷入磁盘呢？

3、缓存命中率概念的引入

假设现在有两个缓存页，一个缓存页的数据，经常会被修改和查询，比如在100次请求中，有30次都是在查询和修改这个缓存页里的数据。那么此时我们可以说这种情况下，缓存命中率很高。

为什么呢？因为100次请求中，30次都可以操作缓存，不需要从磁盘加载数据，这个缓存命中率就比较高了。

另外一个缓存页里的数据，就是刚从磁盘加载到缓存页之后，被修改和查询过1次，之后100次请求中没有一次是修改和查询这个缓存页的数据的，那么此时我们就说缓存命中率有点低，因为大部分请求可能还需要走磁盘查询数据，要操作的数据不在缓存中。

所以针对上述两个缓存页，假设此时让你做一个抉择，要把其中缓存页的数据刷入到磁盘去，腾出来一个空闲的缓存页，此时你会选择谁？

那还用想么，当然是选择第二个缓存页刷入磁盘中了！

4、引入LRU链表来判断哪些缓存页是不常用的

接着就要解决下一个问题了，就是怎么知道哪些缓存页经常被访问，哪些缓存页很少被访问？

此时就要引入一个新的LRU链表了，这个所谓的LRU就是Least Recently Used，最近最少使用的意思。

通过这个LRU链表，可以知道哪些缓存页是最近最少被使用的，那么当缓存页需要腾出来一个刷入磁盘的时候，不就可以选择那个LRU链表中最近最少被使用的缓存页了么。

这个LRU链表大致是怎么个工作原理呢？

假设从磁盘加载一个数据页到缓存页的时候，就把这个缓存页的描述数据块放到LRU链表头部去，那么只要有数据的缓存页，它都会在LRU里了，而且最近被加载数据的缓存页，都会放到LRU链表的头部去。如下图所示：

然后假设某个缓存页的描述数据块本来在LRU链表的尾部，后续只要查询或者修改了这个缓存页的数据，也要把这个缓存页挪动到LRU链表的头部去，也就是说最近被访问过的缓存页，一定在LRU链表的头部，如下图：

那么这样的话，当缓存页没有一个空闲的时候，是不是要找出来那个最近最少被访问的缓存页去刷入磁盘？此时就直接在LRU链表的尾部找到一个缓存页，它一定是最近最少被访问的那个缓存页！

然后就把LRU链表尾部的那个缓存页刷入磁盘中，然后把需要的磁盘数据页加载到腾出来的空闲缓存页中就可以了！