Redis实现skipList(跳表) 代码有详解

**Redis 实现 Skip List (跳表)**Skip List 是一种高效的数据结构，用于快速查找、插入和删除元素。它通过在一个链式列表中维护多个级别的索引来实现这一点，每个级别代表一个不同的层次。Redis 中的 Skip List 实现是基于 Levelled Linked List 的。

**Skip List 结构**

Skip List 由以下几个部分组成：

* **Level**: 每个元素都有一个或多个级别，表示该元素在不同层次上的位置。
* **Head**: 表示链式列表的头部，每个级别都有一个对应的 Head 节点。
* **Next**: 每个元素都有一个 Next 指针，指向下一个元素。
* **Level Pointer**: 每个元素都有一个 Level Pointer，指向当前级别的下一个元素。

**Redis Skip List 实现**

以下是 Redis 中 Skip List 的实现代码：

c// skiplist.htypedef struct {
 int level; // 当前级别 void* value; // 元素值} sdsSkipListNode;

typedef struct {
 int maxLevel; // 最大级别 sdsSkipListNode** levels; // 每个级别的头部} sdsSkipList;

c// skiplist.csdsSkipList* sdsSkipListCreate(int maxLevel) {
 sdsSkipList* sl = zmalloc(sizeof(sdsSkipList));
 sl->maxLevel = maxLevel;
 sl->levels = (sdsSkipListNode**)zmalloc(maxLevel * sizeof(void*));
 for (int i =0; i < maxLevel; i++) {
 sl->levels[i] = NULL;
 }
 return sl;
}

void sdsSkipListFree(sdsSkipList* sl) {
 for (int i =0; i <= sl->maxLevel; i++) {
 sdsSkipListNode* node = sl->levels[i];
 while (node != NULL) {
 sdsSkipListNode* next = node->next;
 zfree(node);
 node = next;
 }
 }
 zfree(sl->levels);
 zfree(sl);
}

c// skiplist.csdsSkipListNode* sdsSkipListNodeCreate(void* value, int level) {
 sdsSkipListNode* node = zmalloc(sizeof(sdsSkipListNode));
 node->value = value;
 node->level = level;
 return node;
}

void sdsSkipListInsert(sdsSkipList* sl, void* value, int maxLevel) {
 int level =1;
 while (level <= maxLevel && random() %2 ==0) {
 level++;
 }
 sdsSkipListNode* node = sdsSkipListNodeCreate(value, level);
 for (int i = level -1; i >=0; i--) {
 if (sl->levels[i] != NULL) {
 sdsSkipListNode* next = sl->levels[i]->next;
 while (next != NULL && next->level > i) {
 next = next->next;
 }
 node->next = next;
 sl->levels[i]->next = node;
 } else {
 sl->levels[i] = node;
 }
 }
}

c// skiplist.csdsSkipListNode* sdsSkipListFind(sdsSkipList* sl, void* value) {
 for (int i = sl->maxLevel -1; i >=0; i--) {
 if (sl->levels[i] != NULL && sl->levels[i]->value == value) {
 return sl->levels[i];
 }
 }
 return NULL;
}

cint main() {
 sdsSkipList* sl = sdsSkipListCreate(10);
 sdsSkipListInsert(sl, "hello",10);
 sdsSkipListInsert(sl, "world",10);
 sdsSkipListNode* node = sdsSkipListFind(sl, "hello");
 if (node != NULL) {
 printf("%s
", node->value);
 }
 return0;
}