B-tree vs hash

B-tree vs hash

2010-08-02 12:53

B-tree相对于普通的有序树，它有两个优点，一是它的复杂度天然就是严格O(logn)，不像普通的二叉树，可能退化成O(N)的，也不像AVL一样得写得很辛苦才可以平衡；二是利用了存储系统的特点，B-tree是有序的，而且是基于比较有序的，所以它的复杂度不可能低于O(logn)，所以比较的次数不会比别的树少，但是它利用了存储系统一次读大块数据比多次读小量数据要快的特点，一个节点有M个儿子，这M个儿子可以连续存储，也可以一次读进来，所以B树调优很重要一点就是根据硬件的特点，选择M。

但是B树还是太复杂了。一般的CODER，别说写了，连理解都困难。所以一般情况下，习惯用HASH作查找，一般的HASH也就一百行代码以内。一般来说，还会和内存池配合使用，内存池代码也在一百行以内吧。从性能上来说，HASH是O(1)的。简单可依赖。

但是还是会有人用B-TREE，这是因为B-TREE还有别的优势，

一是B-TREE是有序的，这点可以做很多事情，比如排序，比如查找距离最近的数，比如查找区间；

二是B-TREE的扩展更缓和，在B-TREE里增加节点很容易，复杂度也可控，而在HASH里，HASH表负载过高之后性能会急剧下降，如果要扩大HASH表，这是一个很痛苦的过程，会带来内存碎片，多线程下要考虑读写安全，会造成当次增加耗时很大，不适于实时服务，当然也有很多算法可以解决这个问题，但是用了这些算法之后，HASH就不再简单了。

三是HASH的时间复杂度O(1)只是一个数学期望值，最坏情况下可能是O(N)的，所以很多场合不适用，比如实时控制

具体还可以参照一下KNUTH写的TAOCP，第三卷介绍完HASH后，有一段对比HASH与树状结构的。

B-TREE还有一个优势是，做快照比较容易。这应该是树状结构都有的优点，在每次增删的时候，把增删的路径上的节点都备分一下，就是一个快照了，时间空间复杂度都很低。HASH也可以做快照，方法就没这么优雅了。比如加时间戳，或者主表、附表之类的。

一般的key-value存储系统，用HASH行了，用B树就太麻烦了