使用 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/

你可能感兴趣的文章