Redis source code analysis skip list

Jump table features
1、 according to score Sort by , If score equal , Then according to ele Sort by .

2、 Average query time complexity O(logn).

Jump table implementation
The jump table is made of server.h/zskiplistNode and server.h/zskiplist Two structures are defined, of which

zskiplistNode Structure is used to subscribe to the nodes of the jump table , and zskiplist Structure is used to save information related to the jump table , For example, the number of nodes , And the pointer of the header node and footer node

Jump table implementation server.h/zskiplistNode Structure definition ：

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    // data 
    sds ele;
    // The score is 
    double score;
    // Back pointer 
    struct zskiplistNode *backward;
    // layer 
    struct zskiplistLevel {
        // Forward pointer 
        struct zskiplistNode *forward;
        // span 
        unsigned long span;
    } level[];
} zskiplistNode;
​
 Copy code 

zskiplist The structure is defined as follows ：

typedef struct zskiplist {
    // Head node and tail node 
    struct zskiplistNode *header, *tail;
    // Number of nodes in the table 
    unsigned long length;
    // The number of nodes with the largest number of layers in the table 
    int level;
} zskiplist;
 Copy code 

With zskiplist The data structure based on is as follows ：

Use scenarios
A jump table is an ordered set （zset） One of the underlying implementations of
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
Copy code
Design jump table
Focus on the topic （1206）:
Do not use any library functions , To design a Jump watch .

Jump watch Is in O(log(n)) Add... In time 、 Delete 、 The data structure of the search operation . Compared with tree pile and red black tree , Its function and performance are equivalent , And the code length of the jump table is shorter , Its design idea is similar to the linked list .

for example , A jump table contains [30, 40, 50, 60, 70, 90] , Then increase 80、45 To jump table , Operate as shown in the following figure ：

Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons

There are many layers in the jump table , Each layer is a short linked list . Under the action of the first layer , increase 、 The time complexity of deletion and search operations does not exceed O(n). The average time complexity of each operation of the jump table is O(log(n)), The space complexity is O(n).

Learn more about : https://en.wikipedia.org/wiki/Skip_list

In the subject , Your design should include these functions ：

bool search(int target) : return target Whether it exists in the jump table .
void add(int num): Insert an element into the jump table .
bool erase(int num): Delete a value in the jump table , If num non-existent , Go straight back to false. If there are multiple num , Any one of them can be deleted .
Be careful , There may be multiple identical values in the jump table , Your code needs to handle this situation .

Example 1:

Input

["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]

Output

[null, null, null, null, false, null, true, false, true, false]

explain

Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0);   //  return  false
skiplist.add(4);
skiplist.search(1);   //  return  true
skiplist.erase(0);    //  return  false,0  Not in the jump table 
skiplist.erase(1);    //  return  true
skiplist.search(1);   //  return  false,1  Has been erased 
 Copy code 

Tips :

0 <= num, target <= 2 * 104

call search,add, erase The number of operations shall not be greater than 5 * 104
Solution code
Here's the reference redis Of skiplist The implementation of the . The code is as follows ：

public class Skiplist {
    private static final float SKIPLIST_P = 0.5f;
    private static final int MAX_LEVEL = 16;
    
    //  Head node 
    Node head;

    //  Node object 
    class Node {
        int val;
        Node bw;   //  Back pointer 
        Node[] fw; //  Forward pointer 
​
        //  Constructors 
        public Node(int val) {
            this.val = val;
            fw = new Node[randomLevel()];
        }
​
        public Node(int val, int size) {
            this.val = val;
            fw = new Node[size + 1];
        }

        //  Generate random  level
        public int randomLevel() {
            int level = 1;
            while (Math.random() < SKIPLIST_P && level < MAX_LEVEL) {
                level++;
            }
            return level;
        }
    }
​
    //  Generate default header node 
    public Skiplist() {
        head = new Node(-1, MAX_LEVEL);
    }

    //  Inquire about 
    public boolean search(int target) {
        Node p = searchNode(target);
        boolean b = p.val == target;
        //System.out.println(b);
        return b;
    }
    
    //  add to 
    public void add(int num) {
        Node p = searchNode(num);
        Node n = new Node(num);
        n.bw = p;
        for (int i = 0; i < n.fw.length; i++) {
            Node f = p;
            while (f.bw != null && f.fw.length < i + 1) {
                f = f.bw;
            }
            if (i == 0 && f.fw[i] != null) {
                f.fw[i].bw = n;
            }
            n.fw[i] = f.fw[i];
            f.fw[i] = n;
        }
    }
    
    //  remove 
    public boolean erase(int num) {
        if (isEmpty()) {
            //System.out.println(false);
            return false;
        }
        Node p = searchNode(num);
        if (p.val != num) {
            //System.out.println(false);
            return false;
        }
        for (int i = 0; i < p.fw.length; i++) {
            Node f = p.bw;
            while (f.bw != null && f.fw.length < i + 1) {
                f = f.bw;
            }
            if (i == 0 && f.fw[i].fw[i] != null) {
                f.fw[i].fw[i].bw = f;
            }
            f.fw[i] = f.fw[i].fw[i];
        }
        //System.out.println(true);
        return true;
    }
    
    //  Query nodes 
    private Node searchNode(int target) {
        if (isEmpty()) {
            return head;
        }
        Node p = head;
        for (int i = MAX_LEVEL; i >= 0; i--) {
            while (p.fw[i] != null && p.fw[i].val <= target) {
                p = p.fw[i];
            }
        }
        return p;
    }
    
    //  Is it empty 
    private boolean isEmpty() {
        return head.fw[0] == null;
    }
}
 Copy code 

Execute the sample （ Execution results ）：

Last
If you think this article is of little help to you , Point a praise . Or you can join my development communication group ：1025263163 Learn from each other , We will have professional technical questions and answers

If you think this article is useful to you , Please give our open source project a little bit star:http://github.crmeb.net/u/defu Thank you for ！

PHP Learning manual ：https://doc.crmeb.com
Technical exchange forum ：https://q.crmeb.com