【原】MySQL - 从磁盘读取数据页到Buffer Pool的时候，free链表的作用

收藏小程序 大量资源免费分享

数据库启动的时候，如何初始化Buffer Pool的

数据库只要一启动，就会按照设置的Buffer Pool大小，稍微再加大一点，去操作系统申请一块内存区域，作为Buffer Pool的内存区域。

当内存区域申请完毕以后，数据库就会按照默认的缓存页的16KB的大小以及对应的800个字节左右的描述数据的大小，在Buffer Pool中划分出来一个一个的缓存页和一个一个的他们对应的描述数据。然后当数据库把Buffer Pool划分完毕之后，看起来就是下面图中展示的那样了。

只不过这个时候，Buffer Pool中的一个一个的缓存页都是空的，里面什么都没有，要等数据库运行起来后，当我们要对数据执行增删改操作的时候，才会把数据对应的页从磁盘文件里读取出来，放入Buffer Pool中的缓存页中。

如何判断哪些缓存页是空闲的

当数据库运行起来后，肯定会不停的执行增删改查的操作，此时就需要不停的从磁盘上读取一个一个的数据页放入Buffer Pool中对应的缓存页里去，把数据缓存起来，那么以后就可以对这个数据在内存里执行增删改查了。

从磁盘上读取数据页放入Buffer Pool中的缓存页的时候，就需要判断哪些缓存页是空闲的。默认情况下磁盘上的数据页和缓存页是一一对应起来的，都是16KB，一个数据页对应一个缓存页。所以我们必须要知道Buffer Pool中哪些缓存页是空闲的状态。

所以数据库为Buffer Pool设计一个free链表，它是一个双向链表数据结构，这个free链表里，每个节点就是一个空闲的缓存页的描述数据块的地址，也就是说，只要有一个缓存页是空闲的，那么他的描述数据块就会被放入这个free链表中。

刚开始数据库启动的时候，可能所有的缓存页都是空闲的，因为此时可能是一个空的数据库，一条数据都没有，所以此时所有缓存页的描述数据块，都会被放入这个free链表中。

可以看到上面出现了一个free链表，这个free链表里面就是各个缓存页的描述数据块，只要缓存页是空闲的，那么他们对应的描述数据块就会加入到这个free链表中，每个节点都会双向链接自己的前后节点，组成一个双向链表。

除此之外，这个free链表有一个基础节点，他会引用链表的头节点和尾节点，里面还存储了链表中有多少个描述数据块的节点，也就是多少个空闲的缓存页。

free链表占用多少内存空间

这个free链表，他本身其实就是由buffer pool里面的描述数据块组成的，可以认为是每个描述数据块里面都有两个指针，一个是free_pre，一个是free_next，分别指向自己的上一个free链表节点以及下一个free链表的节点。

通过Buffer Pool中的描述数据块的free_pre和free_next两个指针，就可以把所有的描述数据块串成一个free链表。

对于free链表而言，只有一个基础节点是不属于Buffer Pool的，他是40字节大小的一个节点，里面就存放了free链表的头结点的地址，尾节点的地址，还有free链表里当前有多少个节点。

如何将磁盘上的页读取到Buffer Pool的缓存页中

当需要把磁盘上的数据页读取到Buffer Pool中的缓存页里去的时候，是怎么做到的呢？

首先我们需要从free链表里获取一个描述数据块，然后就可以对应地获取到这个描述数据块对应的空闲缓存页。

接着我们就可以把磁盘上的数据页读取到对应的缓存页里去，同时把相关的一些描述数据写入缓存页的描述数据块里去，比如这个数据页所属的表空间之类的信息，最后把那个描述数据块从free链表里移除就可以了。

如何知道数据页有没有被缓存

我们在执行增删改查的时候，肯定是先看看这个数据页有没有被缓存，如果没有被缓存就走上面的逻辑，从free链表中找到一个空闲的缓存页，从磁盘中读取数据页写入缓存页，写入描述数据，从free链表中移除这个描述数据块。

但是如果数据页已经被缓存了，那么就会直接使用了。所以其实数据库还会有一个哈希表数据结构，他会用表空间号+数据页号，作为一个key，然后缓存页的地址作为value。

当你要使用一个数据页的时候，通过"表空间号+数据页号"作为key去这个哈希表里面查一下，如果没有就读取数据页，如果已经有了，就说明数据页已经被缓存了。

也就是说每次读取一个数据页到缓存之后，都会在这个哈希表中写入一个key-value对，key就是表空间号+数据页号，value就是缓存页的地址，那么下次如果再使用这个数据页，就可以从哈希表里面直接读取出来他已经被放入一个缓存页了。

更新Buffer Pool中的数据时，flush链表的作用

当我们在执行增删改查的时候，如果发现数据页没有被缓存，一定会基于free链表找到一个空闲的缓存页，然后将数据页读取到缓存页里，如果已经缓存了，就直接使用缓存页；无论怎样，都是在内存中直接执行增删改操作的。

一旦更新了缓存页中的数据，那缓存页中的数据和磁盘上的数据就不一致了，这个时候这个缓存页就是脏数据、脏页了

Buffer Pool中的脏缓存页最终是要被刷新回磁盘文件的，那刷新的时候，需要知道哪些缓存也需要被刷新，不会所有缓存页都刷新

数据库里面引入了一个和free链表类似的flush链表，本质也是通过缓存页的描述数据块中的两个指针，让被修改过的缓存页的描述数据块组成一个双向链表。

凡是被修改过的缓存页，都会把他的描述数据块加入到flush链表中去，flush的意思就是这也都是脏页，后续都是要flush刷新到磁盘上去的。

Buffer Pool中的缓存页不够用怎么办

基于LRU算法淘汰缓存页，从磁盘加载一个数据页到缓存页的时候，这个缓存页的描述数据块会被放到LRU链表的头部，所以所有有数据的缓存页都会在LRU链表中，最近被加载的缓存页，会被放到LRU链表的头部。

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

当没有缓存页空闲的时候，只要把LRU链表尾部的那个缓存页刷入磁盘中，然后把需要的磁盘数据页加载到空闲的缓存页中就可以了。