TC(Tokyo Cabinet )是日本人平林幹雄开发的一款 Key-Value 键值数据库。Tokyo Cabinet实现的数据库类型分为:TCHDB 哈希数据库、TCBDB B+Tree数据库、TCFDB 定长数据库、TCTDB 表格数据库、TCMDB 内存哈希数据库、TCNDB 内存B+Tree数据库。
下载了TC-0.2.9的源代码(比较老的一版,只实现了TCHDB),简要的了解了一下TCHDB的实现机制,详细的TC文档参考:http://fallabs.com/tokyocabinet/
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提供遍历数据中所有记录的接口。