这篇文章讲的是Redis中的有序集合类型。曾几何时,我们希望将数据结构中的数据全部存储在内存中,但是为了多台机器共享内存,不得不将这块内存打包成wcf单独部署,同时考虑如何要连载,麻烦太多。..后来才知道有redis之类的东西可以把高层和低层的数据结构打包成共享内存。一:排序集(SortedSet)刚接触排序集的朋友可能会说,这个集合有哪些使用场景???我可以明确的告诉你:范围搜索的天敌是有序集,任何大数据量,找一个范围的时间复杂度总是O[(LogN)+M],其中M:返回的元素个数,为了由易到难,我们先看redis手册,选几个我们常用的方法观察一下效果。从以上17条命令来看,毫无疑问常用的命令是ZADD、ZREM、ZRANGEBYSCORE、ZRANGE。1.ZADDZADDkeyscoremember[[scoremember][scoremember]...]向有序集合key中添加一个或多个成员元素及其分值。这是官方的解释。赋值方式和hashtable类似,只是这里的key是有序的。我举个例子:我有一个水果集合,里面记录了每个水果的价格,然后我根据价格的各种操作获取对应的水果信息。有了上面的基本信息,我就把它们一一送入SortedSet,如下图:从上图不知道大家有没有发现什么异常???至少有两种。浮点数逼近的问题,比如grape,我加的时候写的是2.8,但是在redis里面给我显示的是一个近似值2.79999....这个可以,就是这样的。默认情况下,SortedSet以键的升序存储。2.ZRANGE,ZREVRANGEZRANGEkeystartstop[WITHSCORES]返回有序集合key中指定范围内的成员。成员的位置按分值递增(从小到大)排序。以上是ZRange的格式模板。其实我在讲ZAdd的时候已经说过了,但这不是重点。讲ZAdd的时候有个问题,ZRange默认是按key升序排序的吧?如果要倒序显示,怎么办???其实可以使用ZRange的镜像方式ZREVRANGE,如下图所示:3.ZRANGEBYSCOREZRANGEBYSCOREkeyminmax[WITHSCORES][LIMIToffsetcount]返回有序集合key,所有score值都在min和max之间的成员(包括那些等于min或max的)。有序集合成员按分值升序排列(从小到大)。这是SortedSet最重要的方法。正如我在文章开头所说,排序集最适合范围搜索。既然是搜索,就得有资格吧?举个例子:我要找1-4元的水果类型,当然要找葡萄,苹果,如下图:127.0.0.1:6379>zrangebyscorefruits14withscores1)"grape"2)"2.7999999999999998"3)"apple"4)"3.5"127.0.0.1:6379>我想知道在1-4区间哪个水果最接近4个???这道题是找apple选项,找到了怎么办???所有的数字倒序然后取第一条数据,对吧,代码如下。127.0.0.1:6379>zrevrangebyscorefruits41withscores1)"苹果"2)"3.5"3)"葡萄"4)"2.7999999999999998"127.0.0.1:6379>zrevrangebyscorefruits41withscoreslimit011)"苹果"71.09>7.6"...ZREMmember[ZREMmember]有序集中key中的一个或多个成员,不存在的成员将被忽略。当键存在但不是排序集类型时返回错误。与其他方法一样,zrem的目的是删除指定的值成员。比如这里我要删除scores=3.5的apple记录。127.0.0.1:6379>zremfruitsapple(整数)1127.0.0.1:6379>zrangefruits0-1withscores1)"葡萄"2)"2.7999999999999998"3)"梨"4)"4.099999999999996"5)"香蕉7)6)""坚果"8)"9.1999999999999993"127.0.0.1:6379>你会发现没有apple相关的记录,因为我已经删除了。..2:探索原理的简单操作已经演示。接下来,我们将讨论sortedset支持什么数据结构。你应该听说过CURD的摊销分析中sortedset的复杂度是Log(N),堪比平衡二叉树。它是1987年问世的一种新型的高效数据结构跳跃表(SkipList)。SkipList的神奇之处在于它跳出了树模型的思维,以multi的方式构造Log(N)-层链表。时间复杂度,无论层高是否增加,采用随机数方式,与Treap树的思想相同,用它来保持树或链表的平衡。具体我就不细说了,不然另当别论。非要懂的可以参考百度百科:http://baike.baidu.com/link?url=I8F7TW933ZjIeBea_-dW9KeNsfKXMni0IdwNB10N1qnVfrOh_ubzcUpgwNVgRPFw3iCkhewGaYjM_o51xchS8a我看了一下百科里画的图大概是这样的:,还有这张图是三个链条吧?在SkipList中,需要保证每条链中的数据必须是有序的。这是必须的。如果要在level1层找到节点6,那么就需要一个一个遍历,需要搜索6次才能正确找到数据。如果你在level2中找到节点6,那么你需要4次才能找到它。如果你在level3中找到节点6,那么你需要3次才能找到它。...现在从宏观的理解上,有没有一种感觉,层数越高,找数据需要遍历的次数就越少,对吧?这是跳表的思路,不然怎么跳?查看redis中skiplist是如何定义的。其源码在redis.h中:;unsignedlonghength;intlevel;}zskiplist;从源码可以看出以下几点:zskiplistnode是skiplist中的node节点,节点中有一个level[]数组,如果你够聪明应该知道这个level[]存放的是三个chain上图中的level1、level2、level3。level[]里面是zskiplistLevel实体,它有一个*forward指针,指向同一层的后续节点。zskiplistLevel中还有一个robj类型的*obj指针,就是RedisObject对象,里面存放的是我们的值,然后还有一个score属性,就是key值。..skiplist是根据它排序的。接下来是第二个枚举zskiplist,无意义,纯封装层,比如里面的length记录了skiplist的节点数,level记录了skiplist的当前层数,用*header,*tail来记录skiplist中第一个节点和最后一个节点的节点数。..就这样。..本文转载自微信公众号“行行码农聊技术”,可通过以下二维码关注。转载本文请联系一线码农聊聊技术公众号。
