go skip list跳表实现之Redis为啥这么快之一的原因_golang skipset

Redis为何使用跳表实现快速索引结构？

Redis中的跳表(skiplist)是一种允许快速查找、插入和删除的数据结构。它是有序集合实现的核心数据结构之一，用于存储有序序列。

跳表的优点在于它可以同时保持数据的有序性和高效的插入、删除和查找操作。在理论上，对于插入、删除和查找操作，它们的时间复杂度分别为O(logN)，这里的N是列表长度。

Redis的跳表实现具有以下特性：

1. 多层索引结构，每层都是双向链表。
2. 每个节点都有一个随机层数，决定了它在跳表中的位置。
3. 包含了向上和向下的指针，使得跳表既可以从上往下搜索，也可以从下往上搜索。

使用跳表的好处是，它可以在对数平均时间复杂度内完成插入、删除和查找操作，这使得Redis可以快速处理大量的数据。

以下是一个简单的Go语言实现示例，展示了如何使用跳表结构：

package main
 
import (
    "fmt"
    "math/rand"
)
 
type SkipListNode struct {
    value    int
    backward *SkipListNode
    forward  *SkipListNode
    down     *SkipListNode
}
 
type SkipList struct {
    header *SkipListNode
    level  int
}
 
func NewSkipList() *SkipList {
    return &SkipList{
        header: &SkipListNode{forward: nil, down: nil, backward: nil},
        level:  0,
    }
}
 
func (sl *SkipList) randomLevel() int {
    level := 1
    for rand.Intn(2) == 1 {
        level++
    }
    return level
}
 
func (sl *SkipList) insert(value int) {
    update := make([]*SkipListNode, sl.level+1)
    rank := make([]*SkipListNode, sl.level+1)
    x := sl.header
    for i := sl.level; i >= 0; i-- {
        for rank[i] != nil && rank[i].value < value {
            x = rank[i]
            rank[i] = rank[i].forward[i]
        }
        update[i] = x
    }
 
    level := sl.randomLevel()
    if level > sl.level {
        for i := sl.level + 1; i <= level; i++ {
            rank[i] = sl.header
            update[i] = sl.header
        }
        sl.level = level
    }
 
    x = &SkipListNode{value: value, forward: make([]*SkipListNode, level+1), backward: nil, down: nil}
    for i := 0; i <= level; i++ {
        x.forward[i] = update[i].forward[i]
        update[i].forward[i] = x
        x.backward = update[i]
        if update[i].forward[i] != nil {
            update[i].forward[i].backward = x
        }
    }
}
 
func main() {
    sl := NewSkipList()
    sl.insert(10)
    sl.insert(20)
    sl.insert(30)
    // Output: 10, 20, 30
    for x := sl.header.forward[0]; x != nil; x = x.forward[0] {
        fmt.Printf("%d, ", x.value)
    }
}

在这个简单的实现中，我