This is the fourth day of my participation in Gwen Challenge
To introduce myself
XDM Ok, I’m a skip list, an ordered data structure, and each of my nodes has an array that maintains Pointers to other nodes that can be accessed quickly, and that’s why I’m a skip list.
My average time complexity is O(logN), O(N) at worst, and I can match the efficiency of balancing trees in most cases, but my implementation is much simpler than his.
What are the usage scenarios in Redis
I’m one of the underlying implementations of ordered collections in Redis (along with the dictionary we talked about earlier), but there’s no such thing as a free lunch, and his use of me as the underlying implementation is conditional. This applies when there are many elements or when the members of an ordered set are long strings. There are only a few usage scenarios in Redis. There are only two places where I am used, one is the ordered collection and the other is used as internal data structure in cluster nodes.
The realization of the I
I look like this:
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
Copy the codeAs you can see, my structure first has two Pointers, one header and one tail, respectively pointing to my head node and my tail node. There is also a length to record the number of my nodes. Level records the maximum height of the middle layer of all my nodes. My header node is a very special node that doesn’t hold any data but just a pointer to the next node at the same level and the corresponding span.
Here’s my node. It looks like this:
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
} zskiplistNode;
Copy the code- Ele is our key
- Score is the score value of our ordered set, which is sorted according to this field
- Backward is a pointer to the previous node, which makes it easy to look backwards
- The level array has a forward pointer to the next node, and a span pointer to the span (how many nodes are between the current node and the node to which the pointer points).
Come to have a look at the source code?
I have a bunch of operations, zslCreate, zslFree, zslInsert, zslDelete, and so on, so I’m just going to start with mine
Implementation of zslInsert! XDM takes a look at the code.
/* 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; 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(); 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; }Copy the codeIn fact, you can see the main logic of this piece:
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;
}
Copy the codeThe logic here is to find the location of the insertion node. The logic here is a bit convoluted. It is the level array of the initial node from back to front to find a score less than the score of the current insertion node. And then we’re going to go back from this node and we’re going to execute the code in the while and we’re going to find our x and the node that we’re going to insert is going to be behind our x.
It’s interesting to see how XDM can focus on this insertion process (if there is any confusion, please return it in the comments section). It’s also interesting to see that the skip list in Redis is an ascending storage structure.
XDM through the source we can find when the score is the same when the skip list is how to sort?
SDSCMP (x->level[I]. Forward ->ele,ele) < 0) is a comparison of their SDS objects, and the code is posted to XDM
int sdscmp(const sds s1, const sds s2) { size_t l1, l2, minlen; int cmp; l1 = sdslen(s1); l2 = sdslen(s2); minlen = (l1 < l2) ? l1 : l2; cmp = memcmp(s1,s2,minlen); if (cmp == 0) return l1>l2? 1: (l1<l2? 1:0); return cmp; }Copy the codeThere is also the notion that the height of the jumper is between 1 and 64 (32 before 3.2)
Finally XDM code word is not easy, if read some help to give a thumbs-up ~ I am going to infusion miss you night!