开始正式的研究key-value形式的持久化存储方案了，第一个阅读的项目是tokyo cabinet，版本号是1.4.19.
tokyo cabinet支持几种数据库形式，包括hash数据库，B+树数据库，fix-length数据库，table数据库。目前我仅看了第一种hash数据库的实现。之所以选择这个，是因为第一这种类型的数据库似乎是TC中使用的最多的一种，其次它的算法比之B+树又更简单一些而效率上的表现也丝毫不差。
看看TC中代码的组织。关于上面几个分类的数据库实现，实际上在TC项目的代码组织中各自以单个文件的形式出现，比如hash数据库的代码全都集中在 tchdb.c/h中，也只不过4000多行罢了。除去这几种数据库的实现文件，其余的代码文件功能可以大体上分为两类，一类是辅助性质的代码，给项目中各个部分使用上的，另一部分就是单独的管理数据库的CLI程序的代码，比如tchmgr.c/h就是用于管理HASH数据库的CLI程序的代码。之所以要交代一下项目中代码的组织，无非是为了说明，其实如果将问题集中在HASH数据库或者其他形式的数据库实现上，起码在TC中，所要关注的代码是不多的。
首先来看数据库文件是如何组织的。
从图中可以看到，hash数据库文件大致分为四个部分：数据库文件头，bucket 数组，free pool数组，最后的是真正存放record的部分。下面对这几部分做一个说明。
1）数据库文件头
数据库文件头部分存放的是关于该数据库的一些总体信息，包括这些内容：
| name |
offset |
length |
feature |
| magic number |
0 |
32 |
identification of the database. Begins with "ToKyO CaBiNeT" |
| database type |
32 |
1 |
hash (0x01) / B+ tree (0x02) / fixed-length (0x03) / table (0x04) |
| additional flags |
33 |
1 |
logical union of open (1<<0) and fatal (1<<1) |
| alignment power |
34 |
1 |
the alignment size, by power of 2 |
| free block pool power |
35 |
1 |
the number of elements in the free block pool, by power of 2 |
| options |
36 |
1 |
logical union of large (1<<0), Deflate (1<<1), BZIP2 (1<<2), TCBS (1<<3), extra codec (1<<4) |
| bucket number |
40 |
8 |
the number of elements of the bucket array |
| record number |
48 |
8 |
the number of records in the database |
| file size |
56 |
8 |
the file size of the database |
| first record |
64 |
8 |
the offset of the first record |
| opaque region |
128 |
128 |
users can use this region arbitrarily |
需要说明的是，上面这个表格来自tokyocabinet的官方文档说明，在
这里。同时，数据库文件中需要存放数据的地方，使用的都是小端方式存放的，以下就不再就这点做说明了。从上面的表格可以看出，数据库文件头的尺寸为256 bytes。
在操作hash数据库的所有API中，都会用到一个对象类型为TCHDB的指针，该结构体中存放的信息就包括了所有数据库文件头的内容，所以每次在打开或者创建一个hash数据库的时候，都会将数据库文件头信息读入到这个指针中（函数tchdbloadmeta）。
2）bucket 数组
bucket array中的每个元素都是一个整数，按照使用的是32位还是64位系统，存放的也就是32位或者64位的整数。这个数组存放的这个整数值，就是每次对 key 进行hash之后得到的hash值所对应的第一个元素在数据库文件中的偏移量。
3）free pool数组
free pool数组中的每个元素定义结构体如下：
typedef struct { // type of structure for a free block
uint64_t off; // offset of the block
uint32_t rsiz; // size of the block
} HDBFB;
很明显，仅有两个成员，一个存放的是在数据库文件中的偏移量，一个则是该free block的尺寸。free pool数组用于保存那些被删除的记录信息，以便于回收利用这些数据区，后续会针对free pool相关的操作，API做一个详细的分析。
4）record数据区
每个record数据区的结构如下表：
| name |
offset |
length |
feature |
| magic number |
0 |
1 |
identification of record block. always 0xC8 |
| hash value |
1 |
1 |
the hash value to decide the path of the hash chain |
| left chain |
2 |
4 |
the alignment quotient of the destination of the left chain |
| right chain |
6 |
4 |
the alignment quotient of the destination of the right chain |
| padding size |
10 |
2 |
the size of the padding |
| key size |
12 |
vary |
the size of the key |
| value size |
vary |
vary |
the size of the value |
| key |
vary |
vary |
the data of the key |
| value |
vary |
vary |
the data of the value |
| padding |
vary |
vary |
useless data |
当然，上面这个结构只是该record被使用时的结构图，当某一项record被删除时，它的结构就变为：
| name |
offset |
length |
feature |
| magic number |
0 |
1 |
identification of record block. always 0xB0 |
| block size |
1 |
4 |
size of the block |
对比两种情况，首先是最开始的magic number是不同的，当magic number是0XB0也就是该record是已经被删除的free record时，那么紧跟着的4个字节存放的就是这个free record的尺寸，而record后面的部分可以忽略不计了。
分析完了hash数据库文件的几个组成部分，从最开始的数据库文件示意图中还看到，从文件头到bucket array这一部分将通过mmap映射到系统的共享内存中，当然，可以映射的内容可能不止到这里，但是，数据库文件头+bucket array这两部分是一定要映射到共享内存中的，也就是说，hash数据库中映射到共享内存中的内容上限没有限制，但是下限是文件头+bucket array部分。
同时，free pool也会通过malloc分配一个堆上的内存，存放到TCHDB的fbpool指针中。
这几部分（除了record zone），通过不同的方式都分别的读取到内存中，目的就是为了加快查找的速度，后面会详细的进行说明。