sorted set是set的一个升级版本,它在set的基础上增加了一个顺序属性,这一属性在添加修改元素的时候可以指定,每次指定后,zset会自动重新按新的值调整顺序,可以理解为有两列的mysql表,一列存value,一列存顺序,操作中key理解为zset的名字.

和set一样sorted set也是string类型元素的集合,不同的是每个元素都会关联一个double类型的score。sorted set的实现是skip list和hash table的混合体。

当元素被添加到集合中时,一个元素到score的映射被添加到hash  table中,所以给定一个元素获取score的开销是O(1),另一个score到元素的映射被添加到skip list，并按照score排序，所以就可以有序的获取集合中的元素。添加，删除操作开销都是O(log(N))和skip list的开销一致,redis 的skip list实现用的是双向链表,这样就可以逆序从尾部取元素。sorted set最经常的使用方式应该是作为索引来使用.我们可以把要排序的字段作为score存储，对象的id当元素存储.

下面讲一个使用 Sorted Sets 的例子:

mysql中有一张表,假设名字为 summary_data吧,记录数为30M左右,有一个字段first_path 为varchar(256),需要找到出现次数最多的10个first_path.

方法一,直接sql语句,sql语句很好写,代码如下:

SELECT first_path, COUNT(*) AS c FROM summary_data GROUP BY first_path ORDER BY c DESC LIMIT 10;

表上面是有索引的,但是索引的长度为 KEY `first_path` (`first_path`(255)),也许是这个原因导致了无法使用索引.

1. id: 1 
2. select_type: SIMPLE 
3. table: summary_data 
4. type: ALL 
5. possible_keys: NULL 
6. key: NULL 
7. key_len: NULL 
8. ref: NULL 
9. rows: 28136948 
10. Extra: Using temporary; Using filesort 

这条sql运行了9分钟,把first_path都导出来,生成文件 input/first_path,每行一条记录,话说这个导出的过程真的很慢.

方法二:sort 与 uniq

sort  input/first_path | uniq -c |sort -nr | head -n 10

排好序的状态,就是分组的状态了.

uniq -c 用来统计每组的数量.

sort -nr 再对统计结果进行降序.

一分半钟搞定.

方法三:redis的sorted set

用这种方法,只因为突然想到sorted set就是为此而生的嘛.

client libary 准备用 hiredis.

安装很简单:make && make install

可以看到库文件安装到了 /usr/local/lib/ 目录头文件安装到了 /usr/local/include/hiredis/ 目录,需要把 /usr/local/lib/ 添加到 /etc/ld.so.conf.

然后ldconfig,编译一下,代码如下:

1. gcc -I /usr/local/include/hiredis -lhiredis ./example.c  
2. #include <stdio.h> 
3. #include <stdlib.h> 
4. #include <string.h> 
5.  
6. #include <hiredis.h> 
7.  
8. int main(int argc, char **argv) { 
9.     unsigned int j; 
10.     redisContext *c; 
11.     redisReply *reply; 
12.     const char *hostname = (argc > 1) ? argv[1] : "127.0.0.1"; 
13.     int port = (argc > 2) ? atoi(argv[2]) : 6379; 
14.  
15.     struct timeval timeout = { 1, 500000 }; // 1.5 seconds 
16.     c = redisConnectWithTimeout(hostname, port, timeout); 
17.     if (c == NULL || c->err) { 
18.         if (c) { 
19.             printf("Connection error: %sn", c->errstr); 
20.             redisFree(c); 
21.         } else { 
22.             printf("Connection error: can't allocate redis contextn"); 
23.         } 
24.         exit(1); 
25.     } 
26.  
27.         FILE * fp; 
28.  
29.  
30.         fp = fopen(argv[3], "r"); 
31.         if (!fp) exit(1); 
32.  
33.         char line[256]; 
34.  
35.         while(fgets(line, sizeof(line)-1, fp ) != NULL) { 
36.                 reply = redisCommand(c, "ZINCRBY myzset_firstpath  1 %s"        , line); 
37.                 freeReplyObject(reply); 
38.         } 
39.  
40.         fclose(fp); 
41.  
42.         reply = redisCommand(c, "ZREVRANGEBYSCORE myzset_firstpath +inf -inf WITHSCORES LIMIT  0 10"); 
43.  
44.                 if (reply->type == REDIS_REPLY_ARRAY) { 
45.                         for (j = 0; j < reply->elements; j+=2) { 
46.                                 printf("%u) %s  %sn", (unsigned int)(j/2), reply->element[j]->str, reply->element[j+1]->str); 
47.                         }  //phpfensi.com 
48.                 } 
49.  
50.  
51.         freeReplyObject(reply); 
52.     /* Disconnects and frees the context */ 
53.     redisFree(c); 
54.  
55.     return 0; 
56. } 

16分钟出结果,not good enough.

Tags: redis sorted sets

分享到：