“This is the 30th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Sorted-Set stores the underlying data structure

3.4.2 Checking the Insertion Position

We want to insert a new element 21, as shown in Figure 3.3:

Let’s take a look at the source code to find the insertion location:

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; }Copy the code

Find the insertion position of the node (score=21, level=2), the logic is as follows: 1) first for loop, I =1. X is now the head of the skip list; Select * from ZSL ->level-1; select * from ZSL ->level-1; Header ->level[1]. Forward ->score(1)* < score(*score); Rank [1]=1, **x and update[1]** are the first nodes (score=1).

5) For loop enters the second time, I =0. Select * from ZSL ->level-1; select * from ZSL ->level-1; select * from ZSL ->level-1; select * from ZSL ->level-1; X ->level[0]->forward; x->level[0]->forward; x->level[0]. Foreard ->score(23) = score(23); foreard->score(23) = score(23); X and update[0]** are both second nodes (score=11), as shown in Figure 3.5:

At this point we find the insertion position between elements 11 and 23.

3.4.3 Adjusting the height of the jumper

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;
}
Copy the code

If rank[2] = 0, update[2]** to the head node, then we need to adjust the height of the entire table. If rank[2] = 0, update[2]** to the head node, then we can only enter the loop once. * * update [2] – > level [2]. The span = 3 * *, * * ZSL – > level = 3 * *, adjust height, such as * * as shown in figure 3.6:

3.4.4 Inserting elements

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;
}

for (i = level; i < zsl->level; i++) {
  update[i]->level[i].span++;
}
Copy the code

The value of level is 3, so the for loop can be executed three times, inserting as follows:

For loop first pass:

X ->level[0]. Score =23; x->level[0];

**update[0] level[0]**

Rank 3) * * [0] * a value of 0, * * update [0] – > level [0]. Span = 1 * *, so * x – > level [0]. Span = 1, the update [0] – > level [0]. Span = 1.

Let’s look again at our structure after the first for loop, as shown in Figure 3.7:

Update [1] update[1] update[1] update[1] update[1] update[1] update[1] update[1] update[1] update[1] update[1] update[1] update[1] **update[1] level[1]** * * rank 3) [1] * has a value of 1, * * update [1] – > level [1]. The span is equal to 2 * *, so * x – > level [1]. The span = 1 to 4) the update [1] – > level [1]. The span = 2.

Let’s look again at our structure after the second for loop, as shown in Figure 3.8:

Update [2] update[2] update[2] update[2] update[2] update[2] update[2] update[2] update[2] update[2] update[2] update[2] update[2] update[2] update[2] update[2] Update [2]** level[2]*; Rank 3) * * * * has a value of 2 [2], because * * update [2] – > level [2]. The span is equal to the * * * 3, the total length of the jump table so x – > level [2]. The span = 1 * *; 4) the update [2] – > level [2]. The span = 3.

Let’s look again at our structure after the third for loop, as shown in Figure 3.9:

At this point, our insertion is complete.

3.4.5 Adjust BACKWARD and update the length of the hop table

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++;
Copy the code

X – > value is equal to the backward, determine the update [0] = = ZSL – > header is equal, if want to be on behalf of the jump table is empty, the value is NULL, if not, put the update [0] * * assigned to it, That is, a backward that points to **score = 11.

The second step is to determine whether it is a tail node, if not, adjust the corresponding BACKWARD, if it is, update the tail direction of the hop table.

Finally, update the length = 4 of the hop table, and the adjusted structure is shown in Figure 3.10:

Well, our insert element source code analysis to this end, this section through the analysis of insert element 21 process with you to analyze the meaning of each sentence of the source code, I hope to help you understand the insert process.

3.5 Sorted -set queries the source analysis of an element

Here is the zslGetRank function to look at the process of querying an element, the following is the specific source code:

unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) { zskiplistNode *x; unsigned long rank = 0; int i; X = ZSL ->header; For (I = ZSL ->level-1; i >= 0; I -) {/ / starting from the top to find first 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 += x->level[i].span; x = x->level[i].forward; } /* x might be equal to ZSL ->header, so test if obj is non-null * rank if (x->ele && sdscmp(x->ele,ele) == 0) { return rank; }} return 0; }Copy the code

We can see from the source code, in fact, to find an element with our insert process to find the insert position of the code is basically the same, the specific query process will not be expanded in detail in this section, (you can see the insert process to find the insert position of the detailed explanation).

3.6 Sorted-Set query multiple elements source analysis

3.6.1 Overall source code analysis

Query multiple elements we through zrange and ZRevrange command implementation to source analysis:

void zrangeGenericCommand(client *c, int reverse) { robj *key = c->argv[1]; robj *zobj; int withscores = 0; long start; long end; long llen; long rangelen; // omit the useless code..... 3.9.1 llEN = zsetLength(zobj); If (start < 0) start = llen+start; if (end < 0) end = llen+end; if (start < 0) start = 0; /* Invariant: start >= 0, So this test will be true when end < 0. * The range is empty when start > end or start >= length. end || start >= llen) { addReply(c,shared.emptymultibulk); return; If (end >= llen) end = llen-1; rangelen = (end-start)+1; /* Return the result in form of a multi-bulk reply */ addReplyMultiBulkLen(c, withscores ? (rangelen*2) : rangelen); If (zobj->encoding == OBJ_ENCODING_ZIPLIST) {unsigned char *zl = zobj-> PTR; unsigned char *eptr, *sptr; unsigned char *vstr; unsigned int vlen; long long vlong; if (reverse) eptr = ziplistIndex(zl,-2-(2*start)); else eptr = ziplistIndex(zl,2*start); serverAssertWithInfo(c,zobj,eptr ! = NULL); sptr = ziplistNext(zl,eptr); while (rangelen--) { serverAssertWithInfo(c,zobj,eptr ! = NULL && sptr ! = NULL); serverAssertWithInfo(c,zobj,ziplistGet(eptr,&vstr,&vlen,&vlong)); if (vstr == NULL) addReplyBulkLongLong(c,vlong); else addReplyBulkCBuffer(c,vstr,vlen); if (withscores) addReplyDouble(c,zzlGetScore(sptr)); if (reverse) zzlPrev(zl,&eptr,&sptr); else zzlNext(zl,&eptr,&sptr); } else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {zset *zs = zobj-> PTR; zskiplist *zsl = zs->zsl; zskiplistNode *ln; sds ele; /* Check if starting point is trivial, before doing log(N) lookup. * if (reverse) {ln = ZSL ->tail; If (start > 0) {// if (start > 0) {// if (start > 0) {// if (start > 0) {// if (start > 0) {// if (start > 0) { } else {// start from the first node ln = ZSL ->header->level[0]. if (start > 0) ln = zslGetElementByRank(zsl,start+1); While (rangelen--) {// Assert serverAssertWithInfo(c,zobj,ln! = NULL); ele = ln->ele; 3.9.3 AddreBulkCBuffer (c,ele,sdslen(ele)) // Write data to the buffer of the client. // Write score(double) to the buffer, see 3.9.4 addReplyDouble(c,ln->score); // Find the next node with a backward if you get it from the back, find the previous node with a backward if you get it from the back, ln = reverse? ln->backward : ln->level[0].forward; } } else { serverPanic("Unknown sorted set encoding"); }}Copy the code

So this is a very simple process, and we’re going to use two diagrams to describe the process of taking elements from the beginning and from the end.

3.6.2 Zrange Query process

Zrange mytest 0-1 **, fetching elements from the header, 1 -> 11 -> 21 -> 23 end As shown in figure 3.12:

3.6.3 Zrevrange Query Process

Command: zrevrange mytest 0-1 **, fetching elements from tail, 23 -> 21 -> 11 -> 1 end. As shown in figure 3.13: