跳跃表是一种有序的数据结构,它通过在每个节点中存放多个指向其他节点的指针(正向的指针>=1个,反向的指针就一个)来达到快速访问节点的目的。在redis当中,其代码定义如下:
点击(此处)折叠或打开
- typedef struct zskiplistNode {
- sds ele;
- double score;
- struct zskiplistNode *backward;
- struct zskiplistLevel {
- struct zskiplistNode *forward;
- unsigned int span;
- } level[];
- } zskiplistNode;
- typedef struct zskiplist {
- struct zskiplistNode *header, *tail;
- unsigned long length;
- int level;
- } zskiplist;
- #define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */
- #define ZSKIPLIST_P 0.25 /* Skiplist P = 1/4 */
字段名称 | 含义 |
ele | 当前节点存储的元素 |
score | 当前节点存储的元素的得分 |
level[] | 当前节点向前遍历时的指针数组,数组中的每个元素包含两个属性:1). 可以到达的节点指针forward;2). 该节点与当前节点的距离span,span用于计算forward节点在当前zskiplist当中的排名,而非用于遍历。 |
backward | 当前节点向后遍历时的指针。注意这里不是数组,也就是说反向遍历只能从后往前一个一个来~~~ |
之后是zskiplist结构
字段名称 | 含义 |
header | 指向跳跃表的头结点的指针 |
tail | 指向跳跃表的尾节点的指针 |
length | 跳跃表的长度,即当前跳跃表包含的节点数目(头结点不包含在内) |
level | 跳跃表中,level数组中元素最多的那个节点的level数组的元素个数(头结点不包含在内) |
zskiplist结构当中需要多说一下的就是为什么length和level字段没有包括头结点?原因在于当创建一个zskiplist的时候,会直接把头结点设置成最大level,以便后续操作,其创建代码如下所示:
点击(此处)折叠或打开
- /* Create a new skiplist. */
- zskiplist *zslCreate(void) {
- int j;
- zskiplist *zsl;
- zsl = zmalloc(sizeof(*zsl));
- zsl->level = 1;
- zsl->length = 0;
- zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
- for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
- zsl->header->level[j].forward = NULL;
- zsl->header->level[j].span = 0;
- }
- zsl->header->backward = NULL;
- zsl->tail = NULL;
- return zsl;
- }
由于zskiplist当中不允许存在相同的sds,这一保障性工作交由调用插入操作的调用者来保证~
插入的时候需要注意的就是它是以level从大到小的顺序来遍历并更新各个指针的,详情见代码:
点击(此处)折叠或打开
- /* Insert a new node in the skiplist. Assumes the element does not already
- * exist (up to the caller to enforce that). The skiplist takes ownership
- * of the passed SDS string 'ele'. */
- zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
- zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
- unsigned int rank[ZSKIPLIST_MAXLEVEL];
- int i, level;
- serverAssert(!isnan(score));
- x = zsl->header;
- // 确定每一个level当中由那一个节点来指向新插入的节点,并记录span
- for (i = zsl->level-1; i >= 0; i--) {
- /* store rank that is crossed to reach the insert position */
- rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
- while (x->level[i].forward &&
- (x->level[i].forward->score < score ||
- (x->level[i].forward->score == score &&
- sdscmp(x->level[i].forward->ele,ele) < 0)))
- {
- rank[i] += x->level[i].span;
- x = x->level[i].forward;
- }
- update[i] = x;
- }
- /* we assume the element is not already inside, since we allow duplicated
- * scores, reinserting the same element should never happen since the
- * caller of zslInsert() should test in the hash table if the element is
- * already inside or not. */
- level = zslRandomLevel();
- // 如果超出level,则更新span
- if (level > zsl->level) {
- for (i = zsl->level; i < level; i++) {
- rank[i] = 0;
- update[i] = zsl->header;
- update[i]->level[i].span = zsl->length;
- }
- zsl->level = level;
- }
- // 创建并插入节点
- x = zslCreateNode(level,score,ele);
- for (i = 0; i < level; i++) {
- x->level[i].forward = update[i]->level[i].forward;
- update[i]->level[i].forward = x;
- /* update span covered by update[i] as x is inserted here */
- x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
- update[i]->level[i].span = (rank[0] - rank[i]) + 1;
- }
- /* increment span for untouched levels */
- for (i = level; i < zsl->level; i++) {
- update[i]->level[i].span++;
- }
- x->backward = (update[0] == zsl->header) ? NULL : update[0];
- if (x->level[0].forward)
- x->level[0].forward->backward = x;
- else
- zsl->tail = x;
- zsl->length++;
- return x;
- }
点击(此处)折叠或打开
- int zslRandomLevel(void) {
- int level = 1;
- while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
- level += 1;
- return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
- }
节点的删除工作就比较的中规中矩了
点击(此处)折叠或打开
- /* Internal function used by zslDelete, zslDeleteByScore and zslDeleteByRank */
- void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
- int i;
- for (i = 0; i < zsl->level; i++) {
- if (update[i]->level[i].forward == x) {
- update[i]->level[i].span += x->level[i].span - 1;
- update[i]->level[i].forward = x->level[i].forward;
- } else {
- update[i]->level[i].span -= 1;
- }
- }
- if (x->level[0].forward) {
- x->level[0].forward->backward = x->backward;
- } else {
- zsl->tail = x->backward;
- }
- while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
- zsl->level--;
- zsl->length--;
- }