Yebangyu's Blog

Fond of Concurrency Programming and Machine Learning

Soupen源码解析之rank实现

写在最前

Soupen是一款高性能的nosql数据库,旨在能在某些方面替代Redis。它由不著名码农、秦汉史历史学家、本站站长Yebangyu同学在业余时间独立开发完成。

Github请访问这里 ,Python客户端请点击这里

和Redis一样,Soupen也同样支持rank功能,但是所使用的数据结构是Treap(Redis使用的是Skip List)。Treap和Skip List都是概率性的高级数据结构。

那么,什么是Treap呢?

What is Treap

Treap

(图片来源于WikiMedia)

简单说来,Treap是这样的树:Treap中的每个节点至少包含key和优先级两个字段,其中key满足搜索树性质,优先级满足堆序性。如上图所示,数字是优先级字段,字母是key字段。其中优先级构成了一个大根堆。

也就是说,在Treap中,key组成了一个二叉搜索树,优先级组成了一个堆。所谓Treap = Tree + Heap。

插入一个节点时,随机生成一个优先级。这时候可能堆序性被破坏,而这可以通过旋转来恢复。由于只可能有左右单旋转两种情形,因此它的代码编写比AVL树、Red-Black Tree要简单的多,并且可以证明旋转的期望次数小于2。

在Treap上的删除、插入、查找的期望时间复杂度都是O($lgn$)。

Soupen PK Redis

Soupen中的Treap实现

Soupen中的treap实现在src/ds/soupen_treap.cpp中,可以从这里下载。

说明:

1,对于score相同的节点,我们通过它们的ele的字典序来决定序。

2,rank的思路也比较自然:从根开始,如果score小于节点的score,那么继续访问该节点的左子树;如果大于节点的score,说明该节点和该节点左子树的所有节点都小于score,因此score的rank应该加上左子树的大小,然后访问该节点的右子树。

所以,SoupenTreapNode中包含了size字段。注意,在计算某个节点的size字段时,除了左右子树,也把该节点本身考虑在内。

3,显然,递归地实现Treap比较方便和容易。

测试程序

我们将Soupen和Redis进行比较。其中Redis的代码来自于它的SkipList实现,不改变它性能的基础上,稍作简化和整理。

测试程序可以从这里下载:

Soupen

Redis

编译链接这两个测试程序时,请记得加-lrt选项。

测试结果

测试环境是Ubuntu 14.04 64位系统 + 8GB内存 + gcc4.8,开启-O2优化选项。

对于200W个整数有序插入的测试结果:

Redis:insert,362263271ns = 0.36s,rank,172763924ns = 0.17s

Soupen:insert,300028059ns = 0.30s,rank,106218516ns = 0.11s

对于200W个整数随机打乱后插入的测试结果:

Redis:insert,1682160424ns = 1.68s,rank,1729983233ns = 1.73s

Soupen:insert,1484001788ns = 1.48s,rank,1182535652ns = 1.18s

可以看出不管在insert还是rank上,Soupen的性能都是要完胜Redis的。

参考文献

1,Mark Allen Weiss的《Data Structures & Algorithm Analysis in C++》中介绍了Treap,这也是我第一次接触和知道Treap的地方。

2,《Introduction to Algorithms》中在某个章节里,以习题的形式介绍了Treap。

3,之前陈利人童鞋在微博上推荐了某大学的某学生写的Treap资料,他们都说好。我没看,也没兴趣。

4,A Disquisition on The Performance Behaviour of Binary Search Tree Data Structures 这篇论文对常见的平衡树进行了全面的实验性分析,强烈推荐。