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.                         }  //Vevb.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.