SQLite缓存机制

SQLite实现过程中，模块性比较强，基本上所有的模块都提供了一个对外的接口，SQLite对该模块做了一个实现，如果使用者对这个模块不满意，可以按照自己的意愿重新对该模块进行编写。SQLite的缓存模块就是一个典型的例子。内存管理也是这样实现的，SQLite提供了五种内存管理的实现，以供使用者选择。

SQLite缓存替换算法是LRU（Least Recently Used，最近最少使用算法）。实现比较简单，主要是由两部分组成：

1. hash表。hash表主要是加快对缓存中数据页的查找速度。hash表后面是一串链表，保存满足该hash函数的所有的页。SQLite是通过页号来进行hash操作的，hash完找到链表的头结点，然后依次查找。
2. LRU链表。LRU链表是通过SQLite操作hash表中的元素的来实现的。SQLite对hash表中页进行一次操作，就会将该页放到LRU链表的头部，因为该页是最近最常用到的。如果缓存需要替换，则需要从LRU链表尾部取出，然后回写到数据库文件中。

所以，在内存中对页的操作至少需要四个指针，两个实现hash表的后续链表，两个实现LRU链表。

具体的缓存如下图：