SkipList (Skip List)

When reading "Redis Design and Implementation", I came across some applications related to SkipList and wanted to learn more about it. I recorded my findings below.

SkipList is actually a data structure that maintains multiple linked lists simultaneously. In other words, it sacrifices more space to store data in order to speed up query speed, which can be considered as trading space for time.

The structure looks like this:

Structure#

In a regular linked list, there would be pointers like next or forward/backward to point to other nodes. SkipList is more powerful.

It has a row (level, the number of levels of SkipList nodes in Redis is 1 to 32) of pointers, and these pointers generally point to nodes at different positions (with different spans).

Node Definition#

The attributes of a basic node are as follows: Key and Value, as well as the number of forward pointers and the array that stores them.

public class Node<T> {
    private Long key;
    private T data;
    private int level;
    private Node<T>[] forwards;
}

Data Structure#

The structure of SkipList includes head and tail nodes, as well as the maximum level height. When adding a node, the height of the node is provided by the getRandomLevel() method.

public class SkipList<T> {
    private int MAX_LEVEL;
    private Node<T> head;
    private Node<T> tail;

    /**
     * Constructor
     *
     * @param level
     */
    public SkipList(int level) {
        
    }

    /**
     * Get the level of the new node,
     * not greater than the maximum node
     *
     * @return
     */
    public int getRandomLevel() {
        int count = 0;
        Random random = new Random(System.currentTimeMillis());
        while (Math.abs(random.nextLong()) % 2 == 1) {
            if (count < MAX_LEVEL - 1) {
                count += 1;
            } else {
                break;
            }
        }
        if (count > MAX_LEVEL - 1) {
            count = MAX_LEVEL - 1;
        }
        return count;
    }
}

Adding Data#

The key to adding data is to find the preceding nodes of the insertion position, and to maintain the preceding nodes of so many levels at the same time.

Node<T>[] update = new Node[MAX_LEVEL];
Node<T> tempHead = head;

An array used to store preceding nodes, and a temporary variable for traversal.

for (int i = MAX_LEVEL - 1; i >= 0; i--) {
   if (tempHead.getForwards()[i] == tail || tempHead.getForwards()[i].getKey() > key) {
     update[i] = tempHead;
   } else {
     while (tempHead.getForwards()[i] != tail && tempHead.getForwards()[i].getKey() < key) {
       tempHead = tempHead.getForwards()[i];
     }
     if (tempHead.getForwards()[i] != tail && tempHead.getForwards()[i].getKey() == key) {
       tempHead.getForwards()[i].setData(data);
       return;
     }
     update[i] = tempHead;
    }
}

Start traversing from the highest level, where the span is faster. When the next node of the current node is the tail or the key is greater than the key to be inserted, save the current node as the result for this level.

After saving, move on to the next level.

If the above conditions are not met, continue to traverse horizontally in that level tempHead = tempHead.getForwards()[i]; until the tail or the key is greater than the target key. If the key is equal, overwrite it and return early.

Then save the result update[i] = tempHead;.

Finally, update the linked list.

When creating a linked list node, it needs to have a forward level (level). The level size should not exceed the size of the Head, and the level value is obtained based on probability. Here it is:

1: 1/2
2: 1/4
3: 1/8
..

The probability of increasing the level by one is 1/2.

Redis uses level: 1/4 and MAX: 32

Node<T> node = new Node<>();
node.setKey(key);
node.setData(data);
node.setForwards(new Node[level + 1]);
int level = getRandomLevel();
node.setLevel(level);
/**
* Link the new node
*/
for (int i = 0; i <= level; i++) {
    if (update[i] != null) {
        node.getForwards()[i] = update[i].getForwards()[i];
        update[i].getForwards()[i] = node;
    }
}

Searching#

Searching is similar to inserting.

Traverse horizontally and vertically, and return when found.

public T getData(Long key) {
    Node<T> tempHead = head;
    for (int i = MAX_LEVEL - 1; i >= 0; i--) {
        if (tempHead.getForwards()[i] == tail || tempHead.getForwards()[i].getKey() > key) {
            continue;
        } else {
            while (tempHead.getForwards()[i] != tail && tempHead.getForwards()[i].getKey() < key) {
                tempHead = tempHead.getForwards()[i];
            }
            if (tempHead.getForwards()[i] != null) {
                if (tempHead.getForwards()[i].getKey() != null) {
                    if (tempHead.getForwards()[i].getKey().equals(key)) {
                        return tempHead.getForwards()[i].getData();
                    }
                }
            }
        }
    }
    return null;
}

Complexity#

Since the forward height of each node is random, it is difficult to calculate precisely.

Time Complexity#

Worst case is O(n)
Probability of O(logn) for searching

Space Complexity#

S < 2n

Beaten#

Compared with Java's HashMap (inflation), it was beaten.