Cấu trúc skip list trong Redis không được định nghĩa trong hai tệp riêng biệt. Trong phiên bản 5.0.7, khai báo và định nghĩa cấu trúc được đặt trong tệp server.h, trong khi các hàm liên quan được định nghĩa trong tệp t_zset.c, tất cả các hàm bắt đầu bằng zsl.
I. Cấu trúc dữ liệu
typedef struct zskiplistNode {
// khóa, duy nhất
sds ele;
// điểm số, có thể trùng lặp
double score;
// con trỏ ngược lại
struct zskiplistNode *backward;
// các tầng
struct zskiplistLevel {
// con trỏ tiến
struct zskiplistNode *forward;
// khoảng cách đến nút tiếp theo trên tầng này, dùng để tính rank
unsigned long span;
} level[];
} zskiplistNode;
zskiplistNode định nghĩa cấu trúc của mỗi nút trong skip list, đây là một cấu trúc có độ dài thay đổi.
1 /*
2 +------------------------+
3 |sds ele | /+-----------------------------+
4 +------------------------+ / |struct zskiplistNode *forward|
5 |double score | / +-----------------------------+
6 +------------------------+ / |unsigned long span |
7 |zskiplistNode * backward| / +-----------------------------+
8 +------------------------+/ . .
9 |zskiplistLevel level[] | . .
10 +------------------------+\ . .
11 \ +-----------------------------+
12 \ |struct zskiplistNode *forward|
13 \ +-----------------------------+
14 \ |unsigned long span |
15 \+-----------------------------+
16 */
Được biểu diễn như sau:
1 /*
2 +--------+
3 |level[1]|
4 |1(span) |
5 +--------+
6 |level[0]|
7 |1(span) |
8 +--------+
9 |backward|
10 +--------+
11 |score |
12 +--------+
13 |ele |
14 +--------+
15 */
Ví dụ:
1 /*
2 +--------+ +--------+ +--------+
3 |level[1]|--------------->|level[1]|--------------->|level[1]|
4 |2 | |2 | |0 |
5 +--------+ +--------+ +--------+ +--------+ +--------+
6 |level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|
7 |1 | |1 | |1 | |1 | |0 |
8 +--------+ +--------+ +--------+ +--------+ +--------+
9 |backward|<--|backward|<--|backward|<--|backward|<--|backward|
10 +--------+ +--------+ +--------+ +--------+ +--------+
11 |1 | |2 | |3 | |4 | |5 |
12 +--------+ +--------+ +--------+ +--------+ +--------+
13 |a | |b | |c | |d | |e |
14 +--------+ +--------+ +--------+ +--------+ +--------+
15 */
Skip list:
1 typedef struct zskiplist {
2 // nút đầu/đuôi
3 struct zskiplistNode *header, *tail;
4 // tổng chiều dài
5 unsigned long length;
6 // tổng số tầng
7 int level;
8 } zskiplist;
Nút đầu cố định là nút rỗng, do đó cấu trúc tổng thể:
1 /*
2 +--------+ +--------+ +--------+
3 |level[1]|--------------->|level[1]|--------------->|level[1]|
4 |2 | |2 | |0 |
5 +--------+ +--------+ +--------+ +--------+ +--------+
6 |level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|
7 |1 | |1 | |1 | |1 | |0 |
8 +--------+ +--------+ +--------+ +--------+ +--------+
9 |backward|<--|backward|<--|backward|<--|backward|<--|backward|
10 +--------+ +--------+ +--------+ +--------+ +--------+
11 |0 | |2 | |3 | |4 | |5 |
12 +--------+ +--------+ +--------+ +--------+ +--------+
13 |NULL | |b | |c | |d | |e |
14 +-->+--------+ +--------+ +--------+ +--------+ +--------+<--+
15 | |
16 | +--------+ |
17 +---|header | |
18 +--------+ |
19 |tail |-------------------------------------------------------+
20 +--------+
21 |length=4|
22 +--------+
23 |level=2 |
24 +--------+
25 */
Mỗi tầng level đều là một danh sách liên kết đơn, trong đó level[0] chứa tất cả các phần tử.
II. Tạo nút và skip list
Tạo một nút skip list dựa trên số tầng đã chỉ định:
1 zskiplistNode *createSkipListNode(int level, double score, sds ele) {
2 zskiplistNode *node = (zskiplistNode *)malloc(sizeof(*node) + level * sizeof(struct zskiplistLevel));
3 node->score = score;
4 node->ele = ele;
5 return node;
6 }
Tạo một skip list:
1 #define MAX_LEVEL 64 /* Đủ cho 2^64 phần tử */
2
3 zskiplist *createSkipList(void) {
4 int i;
5 zskiplist *list = (zskiplist *)malloc(sizeof(*list));
6 list->level = 1;
7 list->length = 0;
8 list->header = createSkipListNode(MAX_LEVEL, 0, NULL);
9 for (i = 0; i < MAX_LEVEL; i++) {
10 list->header->level[i].forward = NULL;
11 list->header->level[i].span = 0;
12 }
13 list->header->backward = NULL;
14 list->tail = NULL;
15 return list;
16 }
Redis định nghĩa mức tối đa là 64 tầng. Khi tạo mới, sẽ tạo một nút đầu rỗng, giúp không cần phải xử lý các trường hợp đặc biệt khi số lượng nút từ 0 đến 1 hoặc từ 1 đến 0.
Cấu trúc skip list sau khi tạo (với 4 làm mức tối đa):
1 /*
2 +--------+
3 |level[3]|-->NULL
4 |0 |
5 +--------+
6 |level[2]|-->NULL
7 |0 |
8 +--------+
9 |level[1]|-->NULL
10 |0 |
11 +--------+
12 |level[0]|-->NULL
13 |0 |
14 +--------+
15 NULL<-|backward|
16 +--------+
17 |0 |
18 +--------+
19 |NULL |
20 +-->+--------+
21 |
22 | +--------+
23 +---|header |
24 +--------+
25 |tail |-->NULL
26 +--------+
27 |length=0|
28 +--------+
29 |level=1 |
30 +--------+
31 */