磁盘文件中存储了很多数据页，数据页中存储了很多行数据。
Buffer Pool中有很多跟数据页大小一样的缓存页。
Buffer Pool中有一个Free链表，是一个双向链表，链表的节点中存储了空闲缓存页的描述信息，通过描述信息，可以找到对应的缓存页。
当执行mysql的增删改查的操作的时候，会找到对应的数据所在的数据页，然后先到Buffer Pool中查看这个数据页有没有被缓存，如果已经被缓存了，就会直接使用；如果没有被缓存，那么就到本地磁盘文件中找到这个数据页，然后根据Buffer Pool中的 Free 链表，在Free链表中找到一个节点，这个节点指向一个空闲的缓存页，把从磁盘文件中读取的数据页存储到这个空闲缓存页中。

当从磁盘上读取数据页放入Buffer Pool中的缓存页时，必然要知道哪些缓存页是空闲的?

一、Free链表的结构

image.png
Free链表是Buffer Pool中基于缓存页描述信息组织起来的双向链表。换言之，Free List中的每一个结点都是缓存页对应的描述信息。并且通过描述信息可以找到指定的缓存页。每个描述数据块里都有2个指针，一个是Free_pre，一个是Free_next。
Free链表中只有一个基础节点是不属于Buffer Pool的，约40B大小。这个基础节点会引用链表的头节点和尾节点，里面还存储了链表中有多少个描述数据块的节点，即有多少个空闲的缓存页。
Free链表工作过程：

  1. 如果一个缓存页中没有存储任何数据，那么它对应的描述信息就会被维护进Free链表中；
  2. 这时当你想把从磁盘中读取出一个数据页放入缓存页中的话，就得先从Free链表中找一个节点（Free 链表中的所有节点都会指向一个空闲的缓存页）；
  3. 那接着就可以把你读取出来的这个数据页放入到该节点指向的缓存页中；
  4. 当数据页中被放入数据之后。它对应的描述信息块会被从Free List中移出。

二、数据缓存页哈希表: 数据页有没有被缓存?

在执行增删改查的时候，肯定是先查看这个数据页有没有被缓存，若没被缓存才会走上面的逻辑。但是若已被缓存了，就会直接使用。
那么Mysql是怎么知道刚读取处理的这个数据页有没有在缓存页中呢？

其实数据库还有一个hash table数据结构，每次读取一个数据页到缓存后，都会在这个哈希表中写入一个key-value。
key = 表空间号+数据页号
value = 缓存页地址
如果存在于hash table中，那就说明该数据页已经存在于Buffer Pool中了，优先使用Buffer Pool中的缓存页。