Redis 跳跃表源码深度剖析（redis跳跃表源码分析）

Redis跳跃表是Redis自3.0以来新增的数据结构，支持O(logN)的定位，更加方便了数据的查找操作。类似于索引，但也有自己独特的优点，可以将查找效率提升至接近最优。跳跃表最大的优点就是减少查找时间，相比于其他更加高效。本文通过Redis的源码，对Redis跳跃表的深度剖析，以了解它的实现细节。

Redis跳跃表的实现以及查找操作，其实和传统的双向链表相比并没有太大的区别，基本的建表操作、插入、查找、删除等操作，思路基本上差不多。当然，Redis给了它自己的风格，源码运用了非常多redis特有的一些优化过程。

Redis跳跃表是一种高度优化的双向链表，其核心是一个带索引的结点，其索引包括键值、分值以及按照分值有序排列的指针。每个结点在插入、删除等操作时，都要先检查索引，以保证数据的正确排序，这是维护跳跃表最重要的步骤之一。如下代码为跳跃表的插入操作。

// Jump table insert operation

// 1. Create a node

zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {

// Other related operations

// …（省略）

// 2.Find the position

zskiplistNode **update = zsl->header->level;

int rank[ZSKIPLIST_MAXLEVEL];

int i;

// Find the postion for insert

for (i = zsl->level; i >= 0; i–) {

rank[i] = (i == zsl->level) ? 0 : rank[i+1];

while (update[i] != zsl->tl &&

(update[i]->score

(update[i]->score == score &&

compareStringObjects(update[i]->ele,obj)

rank[i]++;

update[i] = update[i]->level[i].forward;

}

}

// 3.Create a new node

int level = zslRandomLevel();

if (level > zsl->level) {

for (i = zsl->level+1; i

rank[i] = 0;

update[i] = zsl->header;

update[i]->level[i].span = zsl->length;

}

zsl->level = level;

}

// Create the new node

zskiplistNode *zn = zslCreateNode(level,score,obj);

// 4.Construct the forward and backward relationship

for (i = 0; i

zn->level[i].forward = update[i]->level[i].forward;

update[i]->level[i].forward = zn;

zn->level[i].span = update[i]->level[i].span – (rank[0] – rank[i]);

update[i]->level[i].span = (rank[0] – rank[i]) + 1;

}

// 5.Modify the length of the list

for (i = level+1; i level; i++) {

update[i]->level[i].span++;

}

zsl->length++;

return zn;

}

从代码中可以看出，Redis跳跃表插入操作分为五步，其中第二步是在此次插入和前一个结点间找到正确的位置，第三步给插入的结点分配正确的索引，第四步建立正确的前后级关系，第五步对跳跃表的长度及索引进行调整，保证索引正确。最后在插入完毕时，调整新的结点的键值位置，确保跳跃表的有序特性，从而保证查找操作的效率。

从源码来看，Redis跳跃表看似简单，实则巧妙，其对双向链表采用了一系列细节优化，以提高查找效率，高度实用性。Redis跳跃表提供了多种操作，在查找操作中，非常有效，而且占用空间小，可以说具有极高的应用价值。

香港服务器首选树叶云，2H2G首月10元开通。
树叶云（www.IDC.Net）提供简单好用，价格厚道的香港/美国云服务器和独立服务器。IDC+ISP+ICP资质。ARIN和APNIC会员。成熟技术团队15年行业经验。