枞阳县住房和城乡建设局网站,桂林网站制作培训班,上海的网络推广公司,嘟嘟嘟在线观看播放免费本篇说一下Redis中的 有序集合类型#xff0c;曾几何时#xff0c;我们想把所有数据存到内存中的 数据结构 中#xff0c;但为了多机器共享内存#xff0c;不得不将这块内存包装成wcf单独部署#xff0c;同时还要考虑怎么序列化#xff0c;烦心事太多太多。。。后来才知道… 本篇说一下Redis中的 有序集合类型曾几何时我们想把所有数据存到内存中的 数据结构 中但为了多机器共享内存不得不将这块内存包装成wcf单独部署同时还要考虑怎么序列化烦心事太多太多。。。后来才知道有redis这么????????的东西能把高级的低级的数据结构单独包装到一个共享内存中。一有序集合SortedSet 可能有些初次接触SortedSet集合的朋友可能会说这个集合的使用场景都有哪些我可以明确的告诉你范围查找 的天敌就是有序集合任何大数据量下查找一个范围的时间复杂度永远都是 O[(LogN)M]其中M返回的元素个数为了从易到难我们还是先看一下redis手册挑选几个我们常用的方法观摩观摩效果。从上面的17个命令中毫无疑问常用的命令为ZADDZREMZRANGEBYSCOREZRANGE。1. ZADD
ZADD key score member [[score member] [score member] ...]
将一个或多个 member 元素及其 score 值加入到有序集 key 当中。这个是官方的解释赋值方式和hashtable差不多只不过这里的key是有序的而已。下面我举个例子我有一个fruits集合其中记录了每个水果的price然后我根据price的各种操作来获取对应的水果信息。有了上面的基本信息接下来我逐一送他们到SortedSet中如下图从上面的图中不知道你有没有发现到什么异常至少有两种。浮点数近似值的问题比如grape我在add的时候写明的是2.8在redis中却给我显示近似值2.79999....这个没关系本来就是这样。默认情况下SortedSet是以key的升序排序的方式进行存放。2. ZRANGEZREVRANGE
ZRANGE key start stop [WITHSCORES]返回有序集 key 中指定区间内的成员。其中成员的位置按 score 值递增(从小到大)来排序。上面就是ZRange的格式模版前面我在说ZAdd的时候其实我也已经说了但是这个不是重点在说ZAdd的时候留下了一个问题就是ZRange,默认是按照key升序排序的, 对吧那如果你想倒序显示的话怎么办呢其实你可以使用ZRange的镜像方法ZREVRANGE 即可如下图3. ZRANGEBYSCORE
ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count]返回有序集 key 中所有 score 值介于 min 和 max 之间(包括等于 min 或 max )的成员。有序集成员按 score 值递增(从小到大)次序排列。这个算是对SortedSet来说最最重要的方法了文章开头我也说了有序集合最利于范围查找既然是查找你得有条件对吧下面我举个例子我要找到1-4块钱的水果种类理所当然我会找到 葡萄苹果如下图
127.0.0.1:6379 zrangebyscore fruits 1 4 withscores
1) grape
2) 2.7999999999999998
3) apple
4) 3.5
127.0.0.1:6379 我要找到1-4区间中最接近4块的水果是哪个这个问题就是要找到apple这个选项那如果找到呢仔细想想我可以这么做将1-4区间中的所有数倒序再取第一条数据即可对吧如下代码。
127.0.0.1:6379 zrevrangebyscore fruits 4 1 withscores
1) apple
2) 3.5
3) grape
4) 2.7999999999999998
127.0.0.1:6379 zrevrangebyscore fruits 4 1 withscores limit 0 1
1) apple
2) 3.5
127.0.0.1:6379 4. ZREM
ZREM key member [member ...]移除有序集 key 中的一个或多个成员不存在的成员将被忽略。当 key 存在但不是有序集类型时返回一个错误。跟其他方法一样zrem的目的就是删除指定的value成员比如这里我要删除scores3.5 的 apple记录。
127.0.0.1:6379 zrem fruits apple
(integer) 1
127.0.0.1:6379 zrange fruits 0 -1 withscores
1) grape
2) 2.7999999999999998
3) pear
4) 4.0999999999999996
5) banana
6) 5
7) nut
8) 9.1999999999999993
127.0.0.1:6379你会发现已经没有apple的相关记录了因为已经被我删除啦。。。二探索原理 简单的操作都已经演示完毕了接下来探讨下sortedset到底是由什么数据结构支撑的大家应该早有耳闻sortedset在CURD的摊还分析上都是Log(N)的复杂度可以与平衡二叉树媲美它就是1987年才出来的新型高效数据结构跳跃表(SkipList),SkipList牛逼的地方在于跳出了树模型的思维用多层链表的模式构造了Log(N)的时间复杂度层的高度增加与否采用随机数的模式这个和 Treap树 的思想一样用它来保持树或者链表的平衡。详细的我就不说了哈不然的话又是一篇文章啦如果非要了解的话大家可以参见一下百度百科http://baike.baidu.com/link?urlI8F7T W933ZjIeBea_-dW9KeNsfKXMni0IdwNB10N1qnVfrOh_ubzcUpgwNVgRPFw3iCkhewGaYjM_o51xchS8a我大概看了下百科里面画的这张图就像下面这样这幅图中有三条链对吧在SkipList中是必须要保证每条链中的数据必须有序才可以这是必须的。如果要在level1层中找到节点6那么你需要逐一遍历需要6次查找才能正确的找到数据。如果你在level2层中找到节点6的话那么你需要4次才能找到。如果你在level3层中找到节点6的话那么你需要3次就可以找到。。。。现在宏观理解上是不是有一种感觉如果level的层数越高相对找到数据需要遍历的次数就越少对吧这就是跳跃表的思想不然怎么跳哈接下来我们来看看redis中是怎么定义这个skiplist的它的源码在redis.h 中
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {robj *obj;double score;struct zskiplistNode *backward;struct zskiplistLevel {struct zskiplistNode *forward;unsigned int span;} level[];
} zskiplistNode;typedef struct zskiplist {struct zskiplistNode *header, *tail;unsigned long length;int level;
} zskiplist;从源码中可以看出如下几点zskiplistnode就是skiplist中的node节点节点中有一个level[]数组如果你够聪明的话你应该知道这个level[]就是存放着上图中的 level1level2level3 这三条链。level[]里面是zskiplistLevel实体这个实体中有一个 *forward指针这个指针就是指向同层中的后续节点。在zskiplistLevel中还有一个 robj类型的*obj指针这个就是RedisObject对象哈里面存放的就是我们的value值接下来还有一个score属性这个就是key值啦。。。skiplist就是根据它来进行排序的哈。接下来就是第二个枚举zskiplist这个没什么意思纯粹的包装层比如里面的length是记录skiplist中的节点个数level记录skiplist当前的层数用*header,*tail 记录 skiplist 中的首节点和尾节点。。。仅此而已。。。
