介绍
众所周知，字典类型的实现不外乎哈希和平衡树，当然还有Google实现的B-tree版本。哈希实现是字典类型的主流，其随着键值膨胀的键冲突是这种实现的痛，目前解决的方法很多，如Redis的双哈希表然后迁移，还有BeansDB的哈希树等等。平衡树实现如C++标准库具有较好的收缩性但是其性能是个大问题，在大字典面前很乏力。Google的B-tree实现提供了传统C++ map类型的双倍性能并且减少了一半以上的内存利用。
C-Buffered-tree参考了CascaDB的思想和平衡操作，加强了No-Copy理念，实现了基本的字典类型的接口(Get,Put,Delete)，并将继续实现set类型，sorted set类型。废话不多说，看性能检测。
性能
目前暂时只选择Redis的dict实现作为比较对象，据我了解，在C实现中，Redis的dict实现应该是其中翘楚，虽然其仍然有大量可以优化的地方。
虽然只检测了顺序插入的操作，但是无论是Redis的dict结构还是C-Buffered-tree，其对顺序插入和随机插入都没有特别的性能变化(C-Buffered-tree接下来会对顺序插入做优化)。以下都采用10个字节的键和值来进行。
很显然，三种操作C-Buffered-tree都具有明显的优势，在少量数据操作上优势较少(在这个时间上主要是其他误差在影响)，在大量操作上基本都是双倍的速率。
内存利用
C-Buffered-tree具有高效的内存利用率，平均每个键值只有额外的32个字节的负载，空间利用与Redis-dict类似，但比平衡树实现至少节约5倍以上。
下一版本提供
- 性能翻番: 进一步强化No-Copy目标，调整内存布局和缓存优化，加入对顺序插入情景的优化，调整push操作的方式。
- 增加类型接口: 增加dictionary的迭代器，增加set和sorted set类型
- 采取措施加强Buffered-tree的收缩能力
- 增加不可变dictionary接口，将一个dictionary从mutable变为immutable，immutable dictionary具备更强劲的访问能力
- 加入线程安全版本
Github地址: https://github.com/yuyuyu101/C-Buffered-tree