SkipList (Skip List)

When reading "Redis Design and Implementation", I came across some applications involving 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 trades more space for faster 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 in a SkipList node in Redis ranges from 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 the 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 a new node,
     * not exceeding the maximum level
     *
     * @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 simultaneously.

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

An array used to store the 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;
    }
}

Traverse 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 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 should have a forward level (level), which should not exceed the size of the Head, and the value of the level is probabilistic. 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 insertion.

Traverse horizontally and vertically, and return if 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: O(n)
Probability of O(logn) for searching

Space Complexity#

S < 2n

Beaten#

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