Understanding Skip Lists: Principles, Implementation in Go, and Redis Integration

This article provides a comprehensive exploration of Skip Lists, a data structure that offers efficiency comparable to balanced trees while being easier to implement. The author addresses questions raised while reading "Redis Design and Implementation" and provides practical insights through Go implementation.

Part I: Skip List Principles

A Skip List is essentially an enhancement of an ordered linked list, adding multi-layer indexes using a space-for-time strategy. The core concept involves creating hierarchical indexes: extracting "middle nodes" to form higher-level linked lists, enabling binary search-like efficiency in a linked structure. The author explains how this works through detailed diagrams and examples, showing how to build first-level, second-level, and higher indexes.

Index Update and Degradation Prevention

Similar to balanced trees, Skip Lists must maintain index balance to prevent degradation. The article discusses how nodes are promoted to higher levels with a probability factor (p), typically 1/2. This probabilistic approach ensures that when node count is sufficiently large, the indexes remain well-distributed, approximating the effect of strict "every other node promotion."

Complexity Analysis

Time complexity: O(log n) - proven through mathematical derivation showing expected index height and search steps. Space complexity: O(n) - derived from geometric series calculation with ratio p.

Part II: Go Implementation

The article presents a complete Go implementation of a basic Skip List with the following core components:

const MaxLevel = 32

const p = 0.5

type Node struct {

value  uint32

levels []*Level // index nodes, index=0 is base linked list

}

type Level struct {

next *Node

}

type SkipList struct {

header *Node  // header node

length uint32 // original linked list length, header not counted

height uint32 // highest node level

}

The implementation includes key operations: randomLevel() for determining new node levels based on promotion probability, Add() for insertion with update array tracking, Delete() for removal with height recalculation, and Find() for search operations.

Part III: Redis Skip List Implementation

Redis's implementation differs from classic Skip Lists in several ways: it supports duplicate scores, sorts by both score and member object, uses a doubly-linked base list, and combines with a hash map for O(1) member-to-score lookups. The zset structure uses either ziplist (for small member counts) or map+skiplist (for larger datasets).

Part IV: Questions Answered

The article resolves three key questions: (1) Why header node isn't counted in length - it's an empty initialization node serving only as entry point; (2) How new node levels are determined - by score and member object jointly, with lexicographic comparison for same scores; (3) Why zset allows duplicate scores but not duplicate members - to maintain deterministic insertion order.