1. hash表格式
在SQLite提供了一种WAL(Write-Ahead Logging)的日志模式，不同于传统的日志模式，这种模式先把数据更新写到日志，当日志中的记录大到一定程度后再把日志中的记录刷新到数据库。
在这种日志模式中，读一页数据通常先在WAL日志中查找，如果找不到再从数据库读取。如果WAL日志文件特别大的时候，要在日志中查找某一页是否存在时是一个非常耗时的工作，因此SQLite提供了WAL-index文件来辅助页面的查找。
WAL-index文件使用了进程间共享内存的技术，共享内存是一个以.shm结尾并且和数据库文件在同一个目录下的文件，这个文件有特殊之处，即内存和文件存在映射关系，取到这个文件的地址后可以像内存一样对其读写，而一般文件需要调用read、write函数才能读写。
WAL-index文件由头部和hash表组成，头部记录了数据库和WAL日志的相关信息，而hash表中记录了WAL日志中每一帧的索引和页号。
WAL-index文件按页被划分，每一页是32768字节，每一页对应一张hash表，WAL-index的头部136字节存在第一页，所以第一页的hash表记录要小一点。
这里用"u8", "u16", and "u32"分别表示8位，16位和32位的无符号整型数据类型，第一页的数据格式如下：
u8 aWalIndexHeader[136];
u32 aPgno[4062];
u16 aHash[8192];
之后每一页的格式如下：
u32 aPgno[4096];
u16 aHash[8192];
aPgno保存了WAL日志中每一帧的页号，aHash保存了每一帧的索引，除了第一页以外，aPgno能够保存4096个页号，aHash能保存8192个记录，一般情况下，aHash中的记录有大量是空着的，用0来表示。
aPgno是按顺序记录了WAL日志中每一帧的页号，如果不够了由WAL-index文件接下来每页的aPgno继续记录，所以aPgno的索引和WAL日志帧的索引是一一对应的关系。如WAL中的第10帧页号保存在WAL-index第一页的aPgno[10]中，WAL中的第(k+4062+4096*(n-2))帧的页号保存在WAL-index第n页中的aPgno[k]中
WAL-index文件主要实现了以下的查找功能，给定页号P和在WAL文件中的最大帧索引M，返回WAL文件中页号为P且不超过M的最大帧的索引，如果不存在则返回0。
只要遍历所有的aPgno数组就可以完成上面的功能，但是保存的索引很多时，这种方法还是比较浪费时间的，所以SQLite提供了aHash来加快查找。先把页号P映射成一个hash值
h = (P * 383)%8192
在往WAL-index文件添加新纪录时，把页号P的索引添加到hash表aHash[h]中，冲突了就添加到aHash[h+1]中，依次类推，因为aHash的数量远远大于aPgno的数量，所以总是能找到空的。最坏的情况是所有的页都映射成同一个hash值，此时退化成线性查找，但是按概率上来说，这是不可能的。
2.代码实现
下面主要通过代码来说明是如何实现的：
对于上面所说的数组的大小，先定义成宏：
#define HASHTABLE_NPAGE 4096 /* Must be power of 2 */
#define HASHTABLE_HASH_1 383 /* 计算hash值的一个参数Should be prime */
#define HASHTABLE_NSLOT (HASHTABLE_NPAGE*2) /*即8192 Must be a power of 2 */
//第一页的数量，即4062
#define HASHTABLE_NPAGE_ONE (HASHTABLE_NPAGE - (WALINDEX_HDR_SIZE/sizeof(u32)))
每向WAL日志中写一帧时，都要把对应的页号和索引添加到hash表中，其中iFrame表示索引，p->pgno表示对应的页号
rc = walIndexAppend(pWal, iFrame, p->pgno);
因为WAL-index文件中有多张hash表，walFramePage函数确定索引在哪一张hash表里
static int walFramePage(u32 iFrame){
int iHash = (iFrame+HASHTABLE_NPAGE-HASHTABLE_NPAGE_ONE-1) / HASHTABLE_NPAGE;
return iHash;
}
确定是哪一张hash表后，就可以通过walHashGet函数来获取对应hash表中aPgno和aHash的地址，aPgno的数组下标是从1开始的
rc = walHashGet(pWal, walFramePage(iFrame), &aHash, &aPgno, &iZero);
static int walHashGet(
Wal *pWal, /* WAL handle */
int iHash, /* Find the iHash'th table */
volatile ht_slot **paHash, /* OUT: Pointer to hash index */
volatile u32 **paPgno, /* OUT: Pointer to page number array */
u32 *piZero /* OUT: Frame associated with *paPgno[0] */
){
int rc; /* Return code */
volatile u32 *aPgno;
//获取WAL-index中的第iHash页地址放在aPgno
rc = walIndexPage(pWal, iHash, &aPgno);
assert( rc==SQLITE_OK || iHash>0 );
if( rc==SQLITE_OK ){
u32 iZero;
volatile ht_slot *aHash;
//将第aPgno[4096]的地址用作hash表
aHash = (volatile ht_slot *)&aPgno[HASHTABLE_NPAGE];
if( iHash==0 ){
//第一页的aPgno去掉文件头136字节
aPgno = &aPgno[WALINDEX_HDR_SIZE/sizeof(u32)];
iZero = 0;
}else{
iZero = HASHTABLE_NPAGE_ONE + (iHash-1)*HASHTABLE_NPAGE;
}
// 将aPgno的第一个元素改为从1开始，paPgno[1]即aPgno[0]
*paPgno = &aPgno[-1];
*paHash = aHash;
*piZero = iZero;
}
return rc;
}
接下来的代码向hash表中添加元素
static int walIndexAppend(Wal *pWal, u32 iFrame, u32 iPage){
int rc; /* Return code */
u32 iZero = 0; /* One less than frame number of aPgno[1] */
volatile u32 *aPgno = 0; /* Page number array */
volatile ht_slot *aHash = 0; /* Hash table */
rc = walHashGet(pWal, walFramePage(iFrame), &aHash, &aPgno, &iZero);
/* Assuming the wal-index file was successfully mapped, populate the
** page number array and hash table entry.
*/
if( rc==SQLITE_OK ){
int iKey; /* Hash table key */
int idx; /* Value to write to hash-table slot */
int nCollide; /* Number of hash collisions */
//第iFrame帧对应aPgno[idx]
idx = iFrame - iZero;
assert( idx <= HASHTABLE_NSLOT/2 + 1 );
/* If the entry in aPgno[] is already set, then the previous writer
** must have exited unexpectedly in the middle of a transaction (after
** writing one or more dirty pages to the WAL to free up memory).
** Remove the remnants of that writers uncommitted transaction from
** the hash-table before writing any new entries.
*/
//因为WAL的帧是按照顺序添加到aPgno，事务提交后会
//更新WAL的最大帧索引mxFrame，所以如果此时向hash表
//添加元素时aPgno[idx]已经存在，说明之前出现事务失败
if( aPgno[idx] ){
//清除aHash中记录的索引大于mxFrame的元素
walCleanupHash(pWal);
assert( !aPgno[idx] );
}
/* Write the aPgno[] array entry and the hash-table slot. */
//冲突后把iKey加1即可，hash表中之前写入了idx个元素
//所以冲突最多发生idx次
nCollide = idx;
for(iKey=walHash(iPage); aHash[iKey]; iKey=walNextHash(iKey)){
if( (nCollide--)==0 ) return SQLITE_CORRUPT_BKPT;
}
//写入页号
aPgno[idx] = iPage;
//写入索引
aHash[iKey] = (ht_slot)idx;
}
return rc;
}
最后就是本文开始提出的给定页号，查找该页号在WAL文件中的索引，理解了原理后代码很简单，从最大帧对应的hash表开始，向下遍历每一个hash表，hash表中存在元素冲突，继续寻找冲突元素的下一个直到出现0或找到为止
//要查找的页号为pgno
int sqlite3WalFindFrame(
Wal *pWal, /* WAL handle */
Pgno pgno, /* Database page number to read data for */
u32 *piRead /* OUT: Frame number (or zero) */
){
u32 iRead = 0; /* If !=0, WAL frame to return data from */
//查找的最大帧索引
u32 iLast = pWal->hdr.mxFrame; /* Last page in WAL for this reader */
int iHash; /* Used to loop through N hash tables */
int iMinHash;
//限定查找的最小帧
iMinHash = walFramePage(pWal->minFrame);
for(iHash=walFramePage(iLast); iHash>=iMinHash && iRead==0; iHash--){
volatile ht_slot *aHash; /* Pointer to hash table */
volatile u32 *aPgno; /* Pointer to array of page numbers */
u32 iZero; /* Frame number corresponding to aPgno[0] */
int iKey; /* Hash slot index */
int nCollide; /* Number of hash collisions remaining */
int rc; /* Error code */
//获取WAL-index中的第iHash页
rc = walHashGet(pWal, iHash, &aHash, &aPgno, &iZero);
if( rc!=SQLITE_OK ){
return rc;
}
//最大冲突次数8192次
//其实4096就够了，aPgno中最多4096个元素
nCollide = HASHTABLE_NSLOT;
//把pgno映射成对应的hash值key
//冲突后继续查找，直到aHash[iKey]为0
for(iKey=walHash(pgno); aHash[iKey]; iKey=walNextHash(iKey)){
//aHash[iKey]存的是iFrame在aPgno中对应的索引，将其还原
u32 iFrame = aHash[iKey] + iZero;
// iFrame对应的aPgno元素存的页号是pgno说明找到
if( iFrame<=iLast && iFrame>=pWal->minFrame && aPgno[aHash[iKey]]==pgno ){
//返回要找的帧号
iRead = iFrame;
}
if( (nCollide--)==0 ){
return SQLITE_CORRUPT_BKPT;
}
}
}
*piRead = iRead;
return SQLITE_OK;
}
![GoFrame系列：3、Windows下搭建运行环境并运行demo项目[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)