TCHDB实现机制初探

TC(Tokyo Cabinet )是日本人平林幹雄开发的一款 Key-Value 键值数据库。Tokyo Cabinet实现的数据库类型分为：TCHDB 哈希数据库、TCBDB B+Tree数据库、TCFDB 定长数据库、TCTDB 表格数据库、TCMDB 哈希数据库、TCNDB 内存B+Tree数据库。

 

下载了TC-0.2.9的源代码（比较老的一版，只实现了TCHDB），简要的了解了一下TCHDB的实现机制，详细的TC文档参考：

 

TCHDB使用hash的方式存储key/value，对于发生冲突的key，采用hash链的方式解决冲突，如上图所示。

 

每一个TCHDB对应一个文件，TCHDB将待存储的key/value按某种格式存储在对应的文件中。TCHDB的文件主要被分成四个区域：头部区，hash桶区，空闲块池区，以及记录区，其中前三个区域的大小都是固定的。

 

1. 头部区主要包含TCHDB的一些全局描述信息，包括魔数、数据库类型、空闲块池大小、hash桶中元素个数、记录个数等。

2. hash桶区存储每个hash桶对应的第一个key的存储位置（相对于文件开头的offset）。

3. 空闲块池区存储数据库内空闲块的信息，每一块空闲区域以（offset、size）标示。

4. 记录区依次存储各个key/value记录。

TCHDB的hash机制

1．一级索引对应的是bucket array，如上图第一行，通过key计算出一个hash值bidx，bidx号桶的值对应key/value的存储位置（相对于文件开头的偏移）。最开始hash表是空的，随着key/value的不断存储，相应的桶被设置为对应key/value的存储偏移值。

2．由于hash算法存在冲突，当不同的key计算出相同的bidx时，仅用一个bucket array是不能区分的，TCHDB引入了一个第二hash值hash2（通过第二hash还是会出现冲突的，最终还是要通过对比key来判断，引入第二hash只是为了提高效率）。每个记录中包含一个hash2的字段。

3．对于bidx相等的所有记录是利用记录的left和right字段链接起来，从而解决hash冲突。记录的查找需要遍历整个hash冲突链，直到找到对应的key。

 

put接口的实现

首先根据key计算出hash桶号bdix以及第二hash值hash2。

如果hash桶是空的（对应的offset值为0），则从空闲块池中找到一块足够的区域，将key/value存储在该区域（这样的记录left、right指针都为0），并将对应的hash桶的值设为区域的offset，如果空闲池超过key/value总大小的两倍，则需要将多余的空间放回空闲块池，否则多余的空间直接作为padding。

注：每一项记录和空闲区域的第一个字节都是魔数，用于表示其类型，后面的遍历会用到。

如果发生冲突，即hash桶对应的位置已经存放了至少一个记录，则新的记录会被链接到以桶中第一个记录为根的二叉排序树上，通过记录中的left、right字段实现链接。put接口就相当于二叉排序树的插入，从根开始遍历，如果新纪录hash2值比当前记录小，则转向left对应的记录，否则转向right字段对应的记录；如果hash2值相等，则比较key值，如果新纪录的key比当前记录小，则转向left对应的记录，否则转向right字段对应的记录，如果key值相等说明对应的记录已经存在。

为新纪录分配空闲块并存储，同时修改其父节点的链接指针。如果记录已经存在，TCHDB支持覆盖和保留两种模式，如果是保留则不做任何操作返回，如果是覆盖，先判断已经存在的记录+padding的总长度是否能容纳新纪录，如果可以，则直接覆盖原有记录，否则需要找一个新的足够大的空闲块来存储记录。

get接口的实现

首先根据key计算出hash桶号bdix以及第二hash值hash2。

如果对应的hash桶中值为0，则说明记录不存在，get失败。否则，从hash桶对应记录上开始执行二分查找，查找过程与put中的查找类似。找到记录后读取并返回。

out（删除）接口的实现

首先根据key计算出hash桶号bdix以及第二hash值hash2。

如果对应的hash桶中值为0，则说明记录不存在，out失败。否则，从hash桶对应记录上开始执行二分查找，查找过程与put中的查找类似。找到记录后，执行删除操作，这里主要讨论left、right指针都不为0的情况下的删除。

《数据结构》树上介绍的删除节点操作通常采用递归的方式实现，这里如果采用递归，逻辑就比较复杂了。有两种非递归的方式：

（1）在待删节点的left子树上，查找最右的节点，将待删节点的right子树作为最右节点的右子树，用待删节点的left子树代替待删节点。

（2）在待删节点的right子树上，查找最左的节点，将待删节点的left子树作为最左节点的左子树，用待删节点的right子树代替待删节点。

TCHDB的实现中采用第一种方式。

 

空闲块池的管理

空闲块池的描述符的个数在数据库打开前就确定了，默认是1024，当描述符的使用个数超过一半时，会进行merge操作，将相邻的空闲块进行合并。空闲块池提供了基于offset和size排序的两种接口，前者主要用于合并操作，后者主要用于查找和插入操作。

 

记录的遍历

TCHDB提供了遍历接口，但遍历顺序是确定的，从记录区的开始，tchdbiternext返回遍历过程中的下一个key，该接口依次读取记录，根据记录的魔数，判断是记录还是空闲区，如果是记录则返回key，用户可以根据key调用get接口获取记录值，直到达到记录区的末尾，整个遍历完成。

 

TCHDB特性总结

1．TCHDB将头部和hash桶区直接映射到内存，以提高访问效率。

2．TCHDB使用空闲块池管理数据库的空闲区域。

3．TCHDB采用二叉排序树来组织冲突记录，相比链式效率高。

4．TCHDB提供遍历数据中所有记录的接口。