MongoDB,Redis与投票排名

科普文,关于需求与设计.

MongoDB的索引与计数

MongoDB提供了sort,limit,skip,lt,gt与count查询,很多情况下有人用它们进行文章分页,用作投票排名.
在分页时,用db.article.find().skip(page_num * articles_of_each_page).limit(articles_of_each_page).sort({_id:-1})来查找第page_num页的内容,在投票时,使用db.person.find({score:{$lte:my_score}}).count()来计算某人的排名.
在数据量较小时,往往不会有什么问题,但是随着数据量的增多,性能问题就开始变得明显,如果了解到MongoDB的索引形式是b树,应该不难理解性能出现问题的原因.
举个简单的例子:

            7
        10  |   5||
    12  |   8|| |  3||
16  |   9||

先来看一下为什么find({field:xxx})较快,等于查找只需要从头开始,左右进行比较,在树的深度合适的情况下,复杂度为$log_{2}n$.
不管是分页还是投票,本质上是计算一个元素的排名,比如要计算上图中元素10的排名,在b+树中,我们知道10的所有左枝中的元素都比10大,但是有多少元素,无法得知,因此需要遍历10的所有左枝元素进行计数,复杂度为$n$.

优化方法

有没有什么办法解决,从根本上是没有的,索引的数据结构决定了没有好的算法去计算排名,不过在分页上,有一定的优化余地,我们第一页可以用db.article.find().limit(articles_of_each_page),并记录最后一片文章的_id(或者其他排序值),之后查询db.article.find({_id:{$lt:_id_stored}}).limit(articles_of_each_page)来查找下一页或者类似的,上一页的文章,可以避免大量计数.
对于投票排名,MongoDB没有什么好的办法,如果有这种需求,可以考虑一下redis的zset.

Redis的zset

zset可以在$log_{2}n$的复杂度内完成插入,查询,删除,更新以及确定排名,原因在于数据的存储结构为增加了span的skiplist与字典相结合.

跳跃表

简单介绍一下skiplist.

1------------------------------------->null  lev3
|                                       |
1------------->6------------------>15->null  lev2
|              |                    |   |
1---->3------->6------->9--------->15->null  lev1
|     |        |        |           |   |
1->2->3->4->5->6->7->8->9->10->12->15->null  lev0

一般的skiplist形式大约这样,查找由高层向低层,复杂度大约为$log_{2}n$,写入大致类似,需要处理一些维护数据结构的工作,具体可以wiki.

Redis的改进

1------------------------------------->null  lev3
|                                       |
1(4)---------->6(5)--------------->15->null  lev2
|              |                    |   |
1(1)->3(2)---->6(2)---->9(2)------>15->null  lev1
|     |        |        |           |   |
1->2->3->4->5->6->7->8->9->10->12->15->null  lev0

在这种结构下,是不能在$log_{2}n$的复杂度下确定排名的,但是redis对每个元素增加了span值,表示相邻节点越过的节点数,lev0中所有元素的span都是0,高层中如括号所示,这样我们在查找的同时可以进行计数.
同时,为可以更快地根据member查找score,zset还额外增加了字典来记录member-score的对应,散列的复杂度为$o(1)$.
如果有较强的投票排名需求,redis的zset是一个很好的选择.