博客
关于我
Golang 实现 Redis(5): 使用跳表实现 SortedSet
阅读量:403 次
发布时间:2019-03-05

本文共 3816 字,大约阅读时间需要 12 分钟。

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

你可能感兴趣的文章
Objective-C实现带头双向循环链表(附完整源码)
查看>>
Objective-C实现广度优先搜寻树遍历算法(附完整源码)
查看>>
Objective-C实现应用程序添加防火墙白名单 (附完整源码)
查看>>
Objective-C实现度到弧度算法(附完整源码)
查看>>
Objective-C实现建造者模式(附完整源码)
查看>>
Objective-C实现开方数(附完整源码)
查看>>
Objective-C实现异或加密(附完整源码)
查看>>
Objective-C实现异或加密(附完整源码)
查看>>
Objective-C实现异或密码算法(附完整源码)
查看>>
Objective-C实现异步编程(附完整源码)
查看>>
Objective-C实现弧度到度算法 (附完整源码)
查看>>
Objective-C实现循环移位(附完整源码)
查看>>
Objective-C实现循环链表(附完整源码)
查看>>
Objective-C实现循环队列算法(附完整源码)
查看>>
Objective-C实现循环队列链表算法(附完整源码)
查看>>
Objective-C实现快速傅立叶变换FFT算法(附完整源码)
查看>>
Objective-C实现快速傅里叶变换FFT(附完整源码)
查看>>
Objective-C实现快速傅里叶变换FFT(附完整源码)
查看>>
Objective-C实现快速排序(附完整源码)
查看>>
Objective-C实现快速排序(附完整源码)
查看>>