04 free链表

1、从磁盘读取数据页到Buffer Pool的时候，free链表有什么用？

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

但是此时在从磁盘上读取数据页放入Buffer Pool中的缓存页的时候，必然涉及到一个问题，那就是哪些缓存页是空闲的？

MySQL为Buffer Pool设计一个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链表里当前有多少个节点。

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

1. 从free链表里获取一个描述数据块，对应的获取到这个描述数据块对应的空闲缓存页。
2. 把磁盘上的数据页读取到对应的缓存页里去，同时把相关的一些描述数据写入缓存页的描述数据块里去，比如这个数据页所属的表空间之类的信息
3. 最后把那个描述数据块从free链表里去除

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

数据库还会有一个哈希表数据结构，它会用表空间号+数据页号，作为一个key，然后缓存页的地址作为value。当要使用一个数据页的时候，通过“表空间号+数据页号”作为key去这个哈希表里查一下，如果没有就读取数据页，如果已经有了，就说明数据页已经被缓存了。

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