We all know that the fatal weakness of a single linked list is that it takes at least O(n) time to find any node, which requires traversing the whole list. So is there any way to improve the search efficiency of the linked list?
SkipList is a data structure that uses a time-for-space strategy to speed up search efficiency by creating multiple indexes for linked lists. We first introduce the basic theory of SkipList and then take a look at the implementation in Redis.
SkipList
This is a two-ended list with sentinels, as is the case in most scenarios. The advantage of this is that both head and tail inserts are of constant time complexity, as is deletion. The downside is that if you want to query a node, you need O(n).
What if we added an index to the list? Of course, if the lowest list is ordered, otherwise the index is meaningless.
Let the HEAD pointer point to the highest index, and I pull out a layer of index so that even if you look up node 2222 three times for comparison.
The first time: Compared with the 2019 node, the value is greater than 2019. Continue later
The second time: compared with the 2100 node, the value is still greater than the value. Continue in the future
Third time: this layer index end, point to the next node of the lower level index, continue to compare, find the node
The efficiency of a linked list without an index may not seem obvious, but as the number of linked list nodes increases and the number of index levels increases, the efficiency gap becomes obvious. Figure will not draw their own, from the geek time wang Zheng teacher a picture.
You can see the efficiency of skip lists in just four comparisons over five levels of indexing that would have taken 62 comparisons.
In order to know how different the specific skip list is from the linked list, we will analyze and compare the time complexity of each operation.
1. Insert a node
The original insertion operation of a double-ended linked list (hereinafter referred to as a linked list) is O(1) time complexity, but what we are talking about here is an ordered linked list, so the insertion operation can only be performed after at least finding its insertion position when inserting a node, so the insertion efficiency of the linked list is O(n).
Skip table (hereafter referred to as skip table) also needs two steps to complete the insert operation, first find the insert position, and then insert operation. We set up a linked list of N nodes with a k-level index and assume that the index is split up one level every two node intervals.
Two nodes in k layer, four nodes in K-1 layer, eight nodes in K-2 layer… The first layer has n nodes,
1: n 2:1/2 * n 3:1/2 ^2 * n..... . K is 1/2 to the k minus 1 times nCopy the code1/2^(k-1) * n represents the number of nodes at the KTH layer, 1/2^(k-1) * n=2 can be obtained, k is equal to logn, that is to say, n nodes to build a skip table will need logn layer index, including its own layer of chain surface.
When we want to search for a node, we need to start with the highest level index. The way we build it, a node must be between two index nodes, so each level can access up to three nodes. That you may need to understand to understand, because each layer of index search is based on a layer of indexes from a layer of index is down or is greater than (less than) the index of the current node, but not more than (less than) its nodes, the center of the two back, that is, the current index node of a layer of a index node after it most visited three nodes.
Given this, the time to insert an element into the hop table is O(logn). The time complexity is equal to the time complexity of binary lookup, so sometimes we call a skip list a linked list that implements binary lookup.
Obviously, insert operations, skip lists beat linked lists.
2, modify delete query
In fact, there is no comparison between these three node operations. The operation of modification and deletion is equivalent to a linked list. And the query, as we said above, is at least order n, and the hop is order logn.
In addition, we all know that red and black tree after each insert node will spin to the balance of the tree, then jump table is also there will be such a problem, is inserted, will lead to the underlying list node crazy growth, and still so many index layer, extreme all nodes are added to the final stage index node right, and then make the jump table degenerate into a linked list.
To put it simply, after a large number of nodes are inserted, without updating the index, the hop table will not be as efficient as before. The solution is to update the index node every time a node is inserted. Let’s look at the update strategy.
This random function will generate a random number based on the current structure of the table after a new node is added to the table. This number must be less than the maximum value of the index level. Assuming this value is equal to m, the table will generate the index level from 1 to M. So the choice or implementation of this random function is very important, and we’re not going to talk about it here, but you can see how this random function is implemented in various hop table implementations, typically the SkipList structure implemented inside ConcurrentSkipListMap in Java, And, of course, the implementation in Redis, which we’ll cover soon.
The above is the basic theoretical content of the data structure of the hop table. Next, let’s look at the implementation of redis.
Skip lists in Redis
Is said in the previous, redis himself has realized the jump table, but the purpose is an ordered set of high-level abstract data structure for it to provide services, so when we analyze the source code which will inevitably involve some seemingly useless code structure and logic, but is also very important, we will also mention ordered set related content, but does not break up, The key is to see the implementation of the skip table.
The data structure of the hop table is defined as follows:
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
Copy the codeEach node in a hop table is represented by a zskiplistNode data structure, with head and tail pointing to the head and tail nodes of the lowest linked list, respectively. Length indicates the number of nodes in the lowest linked list of the current hop table. Level indicates the number of the highest index layer of the current hop table.
ZskiplistNode has the following structure:
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;
Copy the codeThe redis source code I extracted here is version 4.0. In the previous version, ele attribute was a RedisObject type, now it is a string type, which means that the jump representation is only used to store string data.
Score records a score value of the current node. The lowest linked list is orderly connected according to the score value. In addition, when we query a node, the score value of the node will also be passed in, because the numerical type is convenient after all.
A backward pointer points to the previous node, why backward, we’ll talk about that later.
Each element is a zskiplistLevel structure. The zskiplistLevel type contains a forward pointer and a span value. Let’s talk little by little.
In theory, a jumper is a double-ended linked list at the bottom level, and then based on this to establish a multi-layer index node to achieve, but in the actual code implementation, this structure is not easy to express, so you have to break the existing inertia thinking, and then to understand the implementation of Redis. In fact, just like the zskiplistNode structure introduced above, each node not only stores the data of the node itself, but also stores the node reference of the node in all index layers of the whole hop table through the level array. The specific structure is like this:
And the whole hop table basically looks like this:
The backward pointer of each node points to the node in front of it, and the level array in each node records which index layers the current node appears in the hop table, and the nodes of this index layer are connected in sequence through its forward pointer, 0 represents the first layer, 1 represents the second layer, and so on. Span is the span between the current node and the next node, and we’ll talk about that in the code later, but if you don’t understand it for the moment.
Basically, the table is such a structure, the above figure is still very important, including we will introduce the source code implementation, but also to your understanding of a lot of help. (After all, I spent a lot of time drawing.)
In addition, there is also an ordered collection structure, which is defined with the hopept-related structure. Many people would say that the ordered collection in Redis is implemented by the hopept-related structure. This is a good statement, but it is not biased.
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
Copy the codeTo be exact, the ordered set in Redis is realized by the dictionary we introduced before and the hop table. The mapping relationship between the data saved in the dictionary and score will be queried from the dictionary every time the data is inserted. If it already exists, it will not be inserted again.
Let’s take a look at the redis hoptable related code implementation.
1. Initialize the hop table
Redis initializes a hop table as follows:
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
zskiplistNode *zn =
zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
zn->score = score;
zn->ele = ele;
returnzn; } /* Create a new skiplist. */ zskiplist *zslCreate(void) { int j; zskiplist *zsl; ZSL = zmalloc(sizeof(* ZSL)); ZSL ->level = 1; ZSL ->length = 0; // create a node. ZSKIPLIST_MAXLEVEL=32 memory size //3, i.e. ZSL ->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL); // Initialize the level of the sentinel nodefor (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;
}
Copy the codeZslCreate is used to initialize a hop table. It is relatively simple, and I have given basic comments, which will not be repeated here. It is important to note that the hop table implemented in Redis allows up to 32 index levels. 32 is a good value.
2. Insert a node
The code to insert a node is quite many and a little complicated. I hope you have the patience to analyze it with me.
zskiplistNode *zslInsert(zskiplist *zsl, double score, ZskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x; Unsigned int rank[ZSKIPLIST_MAXLEVEL]; int i, level; serverAssert(! isnan(score)); X = ZSL ->header; // This section traverses each index level to find the last node less than the current score value // traverses from the upper index to the lower indexfor(i = zsl->level-1; i >= 0; [I] = I == (ZSL ->level-1) {if (ZSL ->level-1) {if (ZSL ->level-1) {if (ZSL ->level-1) {if (ZSL ->level-1) {if (ZSL ->level-1) {if (ZSL ->level-1) {if (ZSL ->level-1) {if (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; // if x = x->level[I]. } update[i] = x; // The new node only needs to be inserted after the last node of each level whose value is less than the given score. // The random algorithm obtains the level value of the balanced hop table, indicating which index our new node will appear in. // The specific algorithm does not need to analyze. Level = zslRandomLevel(); // If the value generated is greater than the highest index of the current hop tableif(level > ZSL ->level) {// Assign an initial value to the higher index level, update[I] to the sentinel nodefor(i = zsl->level; i < level; i++) { rank[i] = 0; update[i] = zsl->header; update[i]->level[i].span = zsl->length; } zsl->level = level; } // create node x = zslCreateNode(level,score,ele); // New nodes are inserted at each index levelfor(i = 0; i < level; X ->level[I]. Forward = update[I]->level[I]. Forward; update[i]->level[i].forward = x; //update[I]->level[I].span Update [I]->level[I]. Span = update[I]->level[I]. Span - (rank[0] -rank [I]); Update [I]->level[I]. Span = (rank[0] -rank [I]) + 1; } // If the balance level generated above is greater than the highest used index of the hop table, we will initialize it for the higher part of the hop tablefor(i = level; i < zsl->level; i++) { update[i]->level[i].span++; } // Modify backward Pointers with tail Pointers 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 codeI have given notes on the whole method, and I will not go into details. You are welcome to communicate and discuss with me. The overall logic is divided into three steps.
- Start at the highest index level, find its precursor node by score, and save it in the UPDATE array
- Each layer must insert nodes and calculate the update span value
- Modify the backward and tail Pointers
Node deletion is similar. First, the target node should be found according to the score value, and then the connection between the front and back nodes should be disconnected to complete node deletion.
3. Special query operations
Since the span field is added in redis’ hop table implementation, it records the span between the current node and the next node, so there are some query methods as follows.
A, zslGetRank
Returns the rank of the node in the skip list with the given member and score.
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--) {
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 */
if (x->ele && sdscmp(x->ele,ele) == 0) {
returnrank; }}return 0;
}
Copy the codeAs you can see, the core code of this method is actually the part of our insert node method that accumulates the span to get a ranking value for the target node.
B, zslGetElementByRank
Query elements by given ranking. This one is even easier.
C, zslIsInRange
Given a range of points, such as 0 to 10, return 1 if the given range is included in the skip list, 0 otherwise.
D, zslFirstInRange
Given a range of points, returns the first node in the skip list that matches this range.
E, zslDeleteRangeByScore
Given a range of points, delete all nodes in the skip list that fall within this range.
F, zslDeleteRangeByRank
Given a ranking range, remove all nodes in the skip list that fall within this range.
In fact, the methods listed below that remove nodes based on rankings, or even a range query, rely on the SPAN field, which is one reason why the INSERT method requires so much computational logic to calculate the SPAN field.
To sum up, skip tables serve for ordered collections. Through multi-level indexes, search efficiency of linked lists is improved to O(logn) level, but modification and deletion is still O(1), which is a relatively excellent data structure. However, the implementation in Redis realizes each node into a structure similar to buildings, that is, our index layer, which is very clever.
We are here for the time being. If you have any questions, you are very welcome to discuss with me.
Focus on the public not getting lost, a programmer who loves to share.
Public number reply “1024” add the author wechat together to discuss learning!
All the case code materials used in each article are uploaded to my personal Github
Github.com/SingleYam/o…
Welcome to step on it!
