写在最前
Soupen是一款高性能的nosql数据库，旨在能在某些方面替代Redis。它由不著名码农、秦汉史历史学家、本站站长Yebangyu同学在业余时间独立开发完成。
和Redis一样，Soupen也同样支持rank功能，但是所使用的数据结构是Treap(Redis使用的是Skip List)。Treap和Skip List都是概率性的高级数据结构。
那么，什么是Treap呢？
What is 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实现，不改变它性能的基础上，稍作简化和整理。
测试程序可以从这里下载：
编译链接这两个测试程序时，请记得加-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 这篇论文对常见的平衡树进行了全面的实验性分析，强烈推荐。