使用 Golang 实现 Redis 系列之五：跳表的有序集合实现

Redis 中的 SortedSet 数据结构通过跳表（skip list）来实现，其优秀的范围查找能力为 ZRange 和 ZRangeByScore 等命令提供了有力支持。本文将从结构定义、查找逻辑、插入逻辑以及删除逻辑等方面详细探讨跳表的实现细节。

结构定义

跳表是一种高效的有序数据结构，其核心思想是通过多层链表来减少查找的时间复杂度。传统的链表实现 ZRange 命令的时间复杂度为 O(n)，而通过引入上层链表，查找时间复杂度可以降低到 O(n / 2)，进一步优化到 O(log n) 时需要 log2(n) 层的链表。

为实现跳表，我们首先定义了以下相关数据结构：

Element：表示跳表中元素的抽象类型，包含成员键（Member）和分数（Score）。

Node：表示跳表节点，包含一个 Element 以及后向指针和多个层级的前向指针。

Level：表示跳表的一个层级，包含当前层的前向指针和跨越当前层的节点数量（span）。

Skiplist：表示跳表的整体结构，包含头节点、尾节点、节点总数以及层级数。

查找节点

跳表的查找逻辑以 RangeByRank 为例，核心思想是从最高层开始，逐层向下查找目标节点。具体实现如下：

func (skiplist *Skiplist) getByRank(rank int64) *Node {    var i int64 = 0    n := skiplist.header // 从顶层开始查找    for level := skiplist.level - 1; level >= 0; level-- {        if n.level[level].forward != nil && (i + n.level[level].span) <= rank {            i += n.level[level].span            n = n.level[level].forward        }    }    if i == rank {        return n    }    return nil}

这个逻辑通过遍历各层节点，快速定位目标节点，确保在 O(log n) 时间内完成查找。

插入节点

插入节点的逻辑相对复杂，需要从最高层开始，逐层查找插入位置，并更新相关的指针。具体实现如下：

func (skiplist *Skiplist) insert(member string, score float64) *Node {    update := make([]*Node, maxLevel)    rank := make([]int64, maxLevel) // 记录每层的起始位置    node := skiplist.header    for i := skiplist.level - 1; i >= 0; i-- {        if i == skiplist.level-1 {            rank[i] = 0        } else {            rank[i] = rank[i+1]        }        if node.level[i] != nil && node.level[i].forward != nil {            for node.level[i].forward != nil &&                (node.level[i].forward.Score < score ||                    (node.level[i].forward.Score == score && node.level[i].forward.Member < member)) {                rank[i] += node.level[i].span                node = node.level[i].forward            }        }        update[i] = node    }    level := randomLevel()    if level > skiplist.level {        for i := skiplist.level; i < level; i++ {            rank[i] = 0            update[i] = skiplist.header            update[i].level[i].span = skiplist.length        }        skiplist.level = level    }    node = createNode(level, score, member)    for i := 0; i < level; i++ {        node.level[i].forward = update[i].level[i].forward        update[i].level[i].forward = node        node.level[i].span = update[i].level[i].span - (rank[0] - rank[i])        update[i].level[i].span = (rank[0] - rank[i]) + 1    }    for i := level; i < skiplist.level; i++ {        update[i].level[i].span++    }    if update[0] == skiplist.header {        node.backward = nil    } else {        node.backward = update[0].level[0].forward    }    if node.level[0].forward != nil {        node.level[0].forward.backward = node    } else {        skiplist.tail = node    }    skiplist.length++    return node}

插入逻辑首先确定新节点所在的层级，然后从顶层开始查找插入位置，最后更新各层的指针，确保跳表的结构正确。

删除节点

删除节点的逻辑与插入逻辑相似，但方向相反。具体实现如下：

func (skiplist *Skiplist) RemoveRangeByRank(start int64, stop int64) ([]*Element) {    i := 0    update := make([]*Node, maxLevel)    removed := make([]*Element, 0)    node := skiplist.header    for level := skiplist.level - 1; level >= 0; level-- {        for node.level[level].forward != nil && (i + node.level[level].span) < start {            i += node.level[level].span            node = node.level[level].forward        }        update[level] = node    }    i++    node = node.level[0].forward    for node != nil && i < stop {        next := node.level[0].forward        removedElement := node.Element        removed = append(removed, removedElement)        skiplist.removeNode(node, update)        node = next        i++    }    return removed}

删除操作需要从最高层开始，逐层查找目标节点，并更新相关的指针，确保跳表的结构正确。

总结

通过以上实现，可以清晰地看出跳表在实现 SortedSet 的关键作用。通过多层链表优化查找时间复杂度，并通过合理的插入和删除逻辑维护跳表的结构，跳表能够高效地支持 Redis 中的有序集合操作。

转载地址：http://dxqzz.baihongyu.com/

你可能感兴趣的文章