介绍
众所周知,字典类型的实现不外乎哈希和平衡树,当然还有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具备更强劲的访问能力
- 加入线程安全版本