beansdb中的hash tree用来存储key对应的hash, version 以及count信息等。hash tree可以持久化到tokyo cabinet中。这样在每次打开的时候key信息就可以直接从cabinet中读出，不用做费时间的hs_scan调用。

hash tree的结构

同普通的树一样，hash tree也分为叶子节点和内节点。每个内节点有16个子节点。叶子节点中最多存放128个item。每个item中存放了key的名字，hash，version。内节点记录了他的所有的子节点存放的item数目和hash值。内节点的hash值是所有子节点的hash值的和，起一个校验的作用。

hash tree中的数据结构主要由两个部分组成：Node 和 Data。Node对应了hash tree中的内节点。 每一个Node都对应了一个Data。但是只有叶子节点对应的Data才是有用的。在获取key值对应的信息时就回到Data中去获取。当查询一个key时，首先会计算这个key值的index，然后根据index值在内节点中定位子节点。最后定位到某个叶子节点。

在插入key的过程中，如果发现item的个数超出某个限制了，就会将该节点分裂。同样，如果内节点中item的个数少于某个阈值，则会将节点合并。

最后总结一下beansdb到底提供了额外的东西呢？

1. 内建了版本支持。
2. 将memcache和tokyo cabinet合到了一起。
3. 支持查询存储数据的meta data。