列表与跳表实现

// 1. 游戏排行榜：按分数排序的玩家列表
// ZADD leaderboard 9500 "player1"
// ZRANGE leaderboard 0 99 WITHSCORES  // 查询前100名

// 2. 延迟队列：按时间戳排序的任务队列
// ZADD delay_queue 1699999999 "task1"
// ZRANGEBYSCORE delay_queue 0 <current_time>  // 获取到期任务

// 3. 实时推荐：按相关度排序的内容
// ZADD recommend 0.95 "article1"
// ZREVRANGE recommend 0 9  // 获取最相关的10条

type SortedArray struct {
    data []int  // 有序数组
}

// 查找：二分查找
func (sa *SortedArray) Search(value int) int {
    left, right := 0, len(sa.data)-1
    for left <= right {
        mid := left + (right-left)/2
        if sa.data[mid] == value {
            return mid
        } else if sa.data[mid] < value {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

// 插入：需要移动元素
func (sa *SortedArray) Insert(value int) {
    pos := sa.findInsertPosition(value)
    // 将 pos 后面的所有元素后移一位
    sa.data = append(sa.data[:pos], append([]int{value}, sa.data[pos:]...)...)
}

type ListNode struct {
    value int
    next  *ListNode
}

type SortedLinkedList struct {
    head *ListNode
}

// 查找：顺序遍历
func (sll *SortedLinkedList) Search(value int) *ListNode {
    current := sll.head
    for current != nil {
        if current.value == value {
            return current
        }
        if current.value > value {
            return nil  // 已超过，不存在
        }
        current = current.next
    }
    return nil
}

// 插入：找到位置后 O(1) 插入
func (sll *SortedLinkedList) Insert(value int) {
    newNode := &ListNode{value: value}

    if sll.head == nil || sll.head.value >= value {
        newNode.next = sll.head
        sll.head = newNode
        return
    }

    current := sll.head
    for current.next != nil && current.next.value < value {
        current = current.next
    }

    newNode.next = current.next
    current.next = newNode
}

type TreeNode struct {
    value  int
    left   *TreeNode
    right  *TreeNode
    height int  // AVL树需要维护高度
}

type AVLTree struct {
    root *TreeNode
}

// 查找：二分查找思想
func (avl *AVLTree) Search(value int) *TreeNode {
    current := avl.root
    for current != nil {
        if current.value == value {
            return current
        } else if value < current.value {
            current = current.left
        } else {
            current = current.right
        }
    }
    return nil
}

// 插入：需要维护平衡 (旋转操作)
func (avl *AVLTree) Insert(value int) {
    avl.root = avl.insertNode(avl.root, value)
}

func (avl *AVLTree) insertNode(node *TreeNode, value int) *TreeNode {
    if node == nil {
        return &TreeNode{value: value, height: 1}
    }

    if value < node.value {
        node.left = avl.insertNode(node.left, value)
    } else if value > node.value {
        node.right = avl.insertNode(node.right, value)
    } else {
        return node  // 已存在
    }

    // 更新高度
    node.height = 1 + max(avl.getHeight(node.left), avl.getHeight(node.right))

    // 计算平衡因子
    balance := avl.getBalance(node)

    // 左左情况：右旋
    if balance > 1 && value < node.left.value {
        return avl.rightRotate(node)
    }

    // 右右情况：左旋
    if balance < -1 && value > node.right.value {
        return avl.leftRotate(node)
    }

    // 左右情况：先左旋后右旋
    if balance > 1 && value > node.left.value {
        node.left = avl.leftRotate(node.left)
        return avl.rightRotate(node)
    }

    // 右左情况：先右旋后左旋
    if balance < -1 && value < node.right.value {
        node.right = avl.rightRotate(node.right)
        return avl.leftRotate(node)
    }

    return node
}

// 旋转操作 (复杂!)
func (avl *AVLTree) rightRotate(y *TreeNode) *TreeNode {
    x := y.left
    T2 := x.right

    x.right = y
    y.left = T2

    y.height = max(avl.getHeight(y.left), avl.getHeight(y.right)) + 1
    x.height = max(avl.getHeight(x.left), avl.getHeight(x.right)) + 1

    return x
}

func (avl *AVLTree) leftRotate(x *TreeNode) *TreeNode {
    y := x.right
    T2 := y.left

    y.left = x
    x.right = T2

    x.height = max(avl.getHeight(x.left), avl.getHeight(x.right)) + 1
    y.height = max(avl.getHeight(y.left), avl.getHeight(y.right)) + 1

    return y
}

// 随机层数生成算法
func randomLevel() int {
    level := 1
    // 每次有50%概率增加一层
    for rand.Float64() < 0.5 && level < MAX_LEVEL {
        level++
    }
    return level
}

// 示例：
// 50% 概率: level = 1 (只在原始层)
// 25% 概率: level = 2 (在原始层 + 一级索引)
// 12.5% 概率: level = 3 (在原始层 + 两级索引)
// ...

type SkipListNode struct {
    key     string        // 键
    value   interface{}   // 值
    score   float64       // 分数 (用于排序)
    level   int           // 节点层数
    forward []*SkipListNode  // 前向指针数组 (每层一个指针)
}

// 示例：一个3层节点的结构
node := &SkipListNode{
    key:   "user:1000",
    value: "张三",
    score: 95.5,
    level: 2,  // 0, 1, 2 三层
    forward: [
        node_level0,  // Level 0 的下一个节点
        node_level1,  // Level 1 的下一个节点
        node_level2,  // Level 2 的下一个节点
    ],
}

func (sl *SkipList) Search(score float64, key string) *SkipListNode {
    current := sl.header  // 从头节点开始

    // 从最高层开始向下搜索
    for level := sl.level; level >= 0; level-- {
        // 在当前层向右走,直到下一个节点大于目标
        for current.forward[level] != nil {
            next := current.forward[level]

            // 比较 (先比分数,再比键)
            if next.score < score || (next.score == score && next.key < key) {
                current = next  // 继续向右
            } else {
                break  // 下一个节点太大了,停止在当前层
            }
        }
        // 当前层走不动了,下降到下一层
    }

    // 此时 current 是小于目标的最后一个节点
    // 目标节点应该是 current.forward[0]
    current = current.forward[0]

    if current != nil && current.score == score && current.key == key {
        return current  // 找到!
    }

    return nil  // 未找到
}

func (sl *SkipList) Insert(score float64, key string, value interface{}) {
    // Step 1: 找到每一层的插入位置
    update := make([]*SkipListNode, MAX_LEVEL+1)
    current := sl.header

    for level := sl.level; level >= 0; level-- {
        for current.forward[level] != nil {
            next := current.forward[level]
            if next.score < score || (next.score == score && next.key < key) {
                current = next
            } else {
                break
            }
        }
        update[level] = current  // 记录每层的前驱节点
    }

    // Step 2: 随机生成层数
    newLevel := randomLevel()

    // Step 3: 如果新层数超过当前最大层数,更新 header 的前向指针
    if newLevel > sl.level {
        for i := sl.level + 1; i <= newLevel; i++ {
            update[i] = sl.header
        }
        sl.level = newLevel
    }

    // Step 4: 创建新节点
    newNode := &SkipListNode{
        key:     key,
        value:   value,
        score:   score,
        level:   newLevel,
        forward: make([]*SkipListNode, newLevel+1),
    }

    // Step 5: 在每一层插入新节点
    for i := 0; i <= newLevel; i++ {
        newNode.forward[i] = update[i].forward[i]
        update[i].forward[i] = newNode
    }

    sl.length++
}

func (sl *SkipList) Delete(score float64, key string) bool {
    // Step 1: 找到每一层的前驱节点
    update := make([]*SkipListNode, MAX_LEVEL+1)
    current := sl.header

    for level := sl.level; level >= 0; level-- {
        for current.forward[level] != nil {
            next := current.forward[level]
            if next.score < score || (next.score == score && next.key < key) {
                current = next
            } else {
                break
            }
        }
        update[level] = current
    }

    // Step 2: 检查目标节点是否存在
    target := current.forward[0]
    if target == nil || target.score != score || target.key != key {
        return false  // 未找到
    }

    // Step 3: 在每一层删除节点
    for i := 0; i <= sl.level; i++ {
        if update[i].forward[i] == target {
            update[i].forward[i] = target.forward[i]
        }
    }

    // Step 4: 调整最大层数 (如果最高层变空了)
    for sl.level > 0 && sl.header.forward[sl.level] == nil {
        sl.level--
    }

    sl.length--
    return true
}

type SimpleSkipList struct {
    level0 *Node  // 原始层
    level1 *Node  // 索引层 (每隔2个元素建一个索引)
}

// 优点：简单易懂
// 缺点：性能不够,索引密度固定

type FixedLevelSkipList struct {
    levels [4]*Node  // 固定4层
    // Level 0: 所有元素
    // Level 1: 每2个元素1个索引
    // Level 2: 每4个元素1个索引
    // Level 3: 每8个元素1个索引
}

// 优点：性能提升
// 缺点：层数固定,不够灵活

type SkipList struct {
    header   *SkipListNode    // 头节点
    tail     *SkipListNode    // 尾节点 (优化)
    length   int              // 元素数量
    level    int              // 当前最大层数
    maxLevel int              // 最大允许层数 (通常16-32)
}

// 优点：
// 1. 动态适应：层数随数据量自动调整
// 2. 概率平衡：无需复杂的平衡维护
// 3. 性能稳定：期望 O(log n)
// 4. 易于并发：无全局锁

// 缺点：
// 1. 空间开销：约2倍空间 (每个节点平均2个指针)

// skiplist/skiplist.go
package skiplist

import (
    "fmt"
    "math/rand"
    "sync"
    "time"
)

const (
    MAX_LEVEL       = 16     // 最大层数
    PROBABILITY     = 0.5    // 晋升概率
)

// 跳表节点
type SkipListNode struct {
    key     string           // 键
    value   interface{}      // 值
    score   float64          // 分数 (用于排序)
    level   int              // 节点层数
    forward []*SkipListNode  // 前向指针数组
}

// 跳跃表
type SkipList struct {
    header   *SkipListNode   // 头节点
    tail     *SkipListNode   // 尾节点
    length   int             // 元素数量
    level    int             // 当前最大层数
    maxLevel int             // 最大允许层数
    mu       sync.RWMutex    // 读写锁
}

// 创建新节点
func newNode(key string, value interface{}, score float64, level int) *SkipListNode {
    return &SkipListNode{
        key:     key,
        value:   value,
        score:   score,
        level:   level,
        forward: make([]*SkipListNode, level+1),
    }
}

// 创建跳跃表
func NewSkipList(maxLevel int) *SkipList {
    if maxLevel <= 0 || maxLevel > MAX_LEVEL {
        maxLevel = MAX_LEVEL
    }

    // 创建头节点 (哨兵节点)
    header := newNode("", nil, 0, maxLevel)

    return &SkipList{
        header:   header,
        tail:     nil,
        length:   0,
        level:    0,
        maxLevel: maxLevel,
    }
}

// 随机生成层数 (核心算法!)
func (sl *SkipList) randomLevel() int {
    level := 0
    for rand.Float64() < PROBABILITY && level < sl.maxLevel {
        level++
    }
    return level
}

// skiplist/search.go
package skiplist

// 查找节点
func (sl *SkipList) Search(score float64, key string) (interface{}, bool) {
    sl.mu.RLock()
    defer sl.mu.RUnlock()

    node := sl.searchNode(score, key)
    if node != nil {
        return node.value, true
    }

    return nil, false
}

// 查找节点（内部方法）
func (sl *SkipList) searchNode(score float64, key string) *SkipListNode {
    current := sl.header

    // 从最高层开始搜索
    for level := sl.level; level >= 0; level-- {
        // 在当前层向前搜索
        for current.forward[level] != nil {
            next := current.forward[level]

            // 比较：先比分数,再比键
            if next.score < score || (next.score == score && next.key < key) {
                current = next  // 继续向右
            } else {
                break  // 太大了,停止
            }
        }
    }

    // 移动到下一个节点
    current = current.forward[0]

    // 检查是否找到
    if current != nil && current.score == score && current.key == key {
        return current
    }

    return nil
}

// 范围查询 (按分数)
func (sl *SkipList) SearchRangeByScore(minScore, maxScore float64) []interface{} {
    sl.mu.RLock()
    defer sl.mu.RUnlock()

    var result []interface{}

    // 找到第一个 >= minScore 的节点
    current := sl.findFirstGE(minScore)

    // 收集范围内的所有节点
    for current != nil && current.score <= maxScore {
        result = append(result, current.value)
        current = current.forward[0]
    }

    return result
}

// 查找第一个 >= 指定分数的节点
func (sl *SkipList) findFirstGE(score float64) *SkipListNode {
    current := sl.header

    for level := sl.level; level >= 0; level-- {
        for current.forward[level] != nil && current.forward[level].score < score {
            current = current.forward[level]
        }
    }

    return current.forward[0]
}

// skiplist/insert.go
package skiplist

// 插入节点
func (sl *SkipList) Insert(score float64, key string, value interface{}) error {
    sl.mu.Lock()
    defer sl.mu.Unlock()

    // Step 1: 查找插入位置,记录每层的前驱节点
    update := make([]*SkipListNode, sl.maxLevel+1)
    current := sl.header

    for level := sl.level; level >= 0; level-- {
        for current.forward[level] != nil {
            next := current.forward[level]
            if next.score < score || (next.score == score && next.key < key) {
                current = next
            } else {
                break
            }
        }
        update[level] = current
    }

    // Step 2: 检查键是否已存在
    current = current.forward[0]
    if current != nil && current.score == score && current.key == key {
        // 键已存在,更新值
        current.value = value
        return nil
    }

    // Step 3: 随机生成层数
    newLevel := sl.randomLevel()

    // Step 4: 如果新层数超过当前最大层数,更新 header 的前向指针
    if newLevel > sl.level {
        for i := sl.level + 1; i <= newLevel; i++ {
            update[i] = sl.header
        }
        sl.level = newLevel
    }

    // Step 5: 创建新节点
    newNode := newNode(key, value, score, newLevel)

    // Step 6: 在每一层插入新节点
    for i := 0; i <= newLevel; i++ {
        newNode.forward[i] = update[i].forward[i]
        update[i].forward[i] = newNode
    }

    // Step 7: 更新尾节点
    if newNode.forward[0] == nil {
        sl.tail = newNode
    }

    sl.length++
    return nil
}

// skiplist/delete.go
package skiplist

// 删除节点
func (sl *SkipList) Delete(score float64, key string) bool {
    sl.mu.Lock()
    defer sl.mu.Unlock()

    // Step 1: 查找删除位置,记录每层的前驱节点
    update := make([]*SkipListNode, sl.maxLevel+1)
    current := sl.header

    for level := sl.level; level >= 0; level-- {
        for current.forward[level] != nil {
            next := current.forward[level]
            if next.score < score || (next.score == score && next.key < key) {
                current = next
            } else {
                break
            }
        }
        update[level] = current
    }

    // Step 2: 检查目标节点是否存在
    current = current.forward[0]
    if current == nil || current.score != score || current.key != key {
        return false  // 未找到
    }

    // Step 3: 在每一层删除节点
    for i := 0; i <= sl.level; i++ {
        if update[i].forward[i] == current {
            update[i].forward[i] = current.forward[i]
        }
    }

    // Step 4: 更新尾节点
    if current == sl.tail {
        sl.tail = update[0]
        if sl.tail != sl.header {
            sl.tail = update[0]
        } else {
            sl.tail = nil
        }
    }

    // Step 5: 调整最大层数
    for sl.level > 0 && sl.header.forward[sl.level] == nil {
        sl.level--
    }

    sl.length--
    return true
}

// 删除范围
func (sl *SkipList) DeleteRangeByScore(minScore, maxScore float64) int {
    sl.mu.Lock()
    defer sl.mu.Unlock()

    count := 0

    // 找到第一个 >= minScore 的节点
    update := make([]*SkipListNode, sl.maxLevel+1)
    current := sl.header

    for level := sl.level; level >= 0; level-- {
        for current.forward[level] != nil && current.forward[level].score < minScore {
            current = current.forward[level]
        }
        update[level] = current
    }

    current = current.forward[0]

    // 删除范围内的所有节点
    for current != nil && current.score <= maxScore {
        next := current.forward[0]

        // 在每一层删除节点
        for i := 0; i <= sl.level; i++ {
            if update[i].forward[i] == current {
                update[i].forward[i] = current.forward[i]
            }
        }

        count++
        current = next
    }

    // 调整最大层数
    for sl.level > 0 && sl.header.forward[sl.level] == nil {
        sl.level--
    }

    sl.length -= count
    return count
}

// skiplist/utils.go
package skiplist

// 获取长度
func (sl *SkipList) Length() int {
    sl.mu.RLock()
    defer sl.mu.RUnlock()
    return sl.length
}

// 获取排名 (从0开始)
func (sl *SkipList) GetRank(score float64, key string) int {
    sl.mu.RLock()
    defer sl.mu.RUnlock()

    rank := 0
    current := sl.header

    for level := sl.level; level >= 0; level-- {
        for current.forward[level] != nil {
            next := current.forward[level]
            if next.score < score || (next.score == score && next.key < key) {
                rank++
                current = next
            } else {
                break
            }
        }
    }

    current = current.forward[0]
    if current != nil && current.score == score && current.key == key {
        return rank
    }

    return -1  // 未找到
}

// 根据排名获取节点 (从0开始)
func (sl *SkipList) GetByRank(rank int) (interface{}, bool) {
    sl.mu.RLock()
    defer sl.mu.RUnlock()

    if rank < 0 || rank >= sl.length {
        return nil, false
    }

    current := sl.header.forward[0]
    for i := 0; i < rank && current != nil; i++ {
        current = current.forward[0]
    }

    if current != nil {
        return current.value, true
    }

    return nil, false
}

// 获取范围排名
func (sl *SkipList) GetRangeByRank(start, stop int) []interface{} {
    sl.mu.RLock()
    defer sl.mu.RUnlock()

    if start < 0 || stop >= sl.length || start > stop {
        return nil
    }

    var result []interface{}
    current := sl.header.forward[0]

    // 移动到起始位置
    for i := 0; i < start && current != nil; i++ {
        current = current.forward[0]
    }

    // 收集范围内的节点
    for i := start; i <= stop && current != nil; i++ {
        result = append(result, current.value)
        current = current.forward[0]
    }

    return result
}

// 打印跳表结构 (调试用)
func (sl *SkipList) Print() {
    sl.mu.RLock()
    defer sl.mu.RUnlock()

    fmt.Printf("SkipList (length=%d, level=%d):\n", sl.length, sl.level)

    for level := sl.level; level >= 0; level-- {
        fmt.Printf("Level %d: ", level)
        current := sl.header.forward[level]
        for current != nil {
            fmt.Printf("[%.1f:%s] -> ", current.score, current.key)
            current = current.forward[level]
        }
        fmt.Println("nil")
    }
}

// skiplist/skiplist_bench_test.go
package skiplist

import (
    "fmt"
    "math/rand"
    "testing"
)

// 测试插入性能
func BenchmarkSkipListInsert(b *testing.B) {
    sl := NewSkipList(16)

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        score := float64(i)
        key := fmt.Sprintf("key%d", i)
        sl.Insert(score, key, i)
    }
}

// 测试查找性能
func BenchmarkSkipListSearch(b *testing.B) {
    sl := NewSkipList(16)

    // 预填充数据
    for i := 0; i < 1000000; i++ {
        score := float64(i)
        key := fmt.Sprintf("key%d", i)
        sl.Insert(score, key, i)
    }

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        score := float64(rand.Intn(1000000))
        key := fmt.Sprintf("key%d", int(score))
        sl.Search(score, key)
    }
}

// 测试范围查询性能
func BenchmarkSkipListRangeQuery(b *testing.B) {
    sl := NewSkipList(16)

    // 预填充数据
    for i := 0; i < 1000000; i++ {
        score := float64(i)
        key := fmt.Sprintf("key%d", i)
        sl.Insert(score, key, i)
    }

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        start := float64(rand.Intn(900000))
        sl.SearchRangeByScore(start, start+100)
    }
}

// 对比：Go map 的性能
func BenchmarkGoMap(b *testing.B) {
    m := make(map[string]int)

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        key := fmt.Sprintf("key%d", i)
        m[key] = i
    }
}

// skiplist/skiplist_test.go
package skiplist

import (
    "testing"
)

func TestSkipListBasicOperations(t *testing.T) {
    sl := NewSkipList(16)

    // 测试插入
    sl.Insert(10.0, "key1", "value1")
    sl.Insert(20.0, "key2", "value2")
    sl.Insert(15.0, "key3", "value3")

    if sl.Length() != 3 {
        t.Errorf("Expected length 3, got %d", sl.Length())
    }

    // 测试查找
    val, exists := sl.Search(10.0, "key1")
    if !exists || val != "value1" {
        t.Errorf("Expected 'value1', got %v", val)
    }

    // 测试不存在的键
    _, exists = sl.Search(99.0, "key99")
    if exists {
        t.Error("Key should not exist")
    }

    // 测试删除
    if !sl.Delete(10.0, "key1") {
        t.Error("Failed to delete key1")
    }

    _, exists = sl.Search(10.0, "key1")
    if exists {
        t.Error("Key1 should not exist after deletion")
    }

    if sl.Length() != 2 {
        t.Errorf("Expected length 2, got %d", sl.Length())
    }
}

func TestSkipListRangeQuery(t *testing.T) {
    sl := NewSkipList(16)

    // 插入测试数据
    for i := 0; i < 100; i++ {
        score := float64(i)
        key := fmt.Sprintf("key%d", i)
        sl.Insert(score, key, i)
    }

    // 测试范围查询
    result := sl.SearchRangeByScore(10.0, 20.0)
    if len(result) != 11 {  // 10, 11, ..., 20
        t.Errorf("Expected 11 results, got %d", len(result))
    }

    // 验证结果顺序
    for i, val := range result {
        expected := 10 + i
        if val != expected {
            t.Errorf("Expected %d at position %d, got %v", expected, i, val)
        }
    }
}

func TestSkipListRank(t *testing.T) {
    sl := NewSkipList(16)

    // 插入测试数据
    for i := 0; i < 100; i++ {
        score := float64(i)
        key := fmt.Sprintf("key%d", i)
        sl.Insert(score, key, i)
    }

    // 测试获取排名
    rank := sl.GetRank(50.0, "key50")
    if rank != 50 {
        t.Errorf("Expected rank 50, got %d", rank)
    }

    // 测试根据排名获取
    val, exists := sl.GetByRank(25)
    if !exists || val != 25 {
        t.Errorf("Expected 25, got %v", val)
    }
}

func TestSkipListConcurrent(t *testing.T) {
    sl := NewSkipList(16)
    done := make(chan bool, 2)

    // 并发写入
    go func() {
        for i := 0; i < 1000; i++ {
            score := float64(i)
            key := fmt.Sprintf("key%d", i)
            sl.Insert(score, key, i)
        }
        done <- true
    }()

    // 并发读取
    go func() {
        for i := 0; i < 1000; i++ {
            score := float64(i % 100)
            key := fmt.Sprintf("key%d", i%100)
            sl.Search(score, key)
        }
        done <- true
    }()

    // 等待完成
    <-done
    <-done

    if sl.Length() != 1000 {
        t.Errorf("Expected length 1000, got %d", sl.Length())
    }
}

type ZSet struct {
    dict     map[string]float64  // 哈希表：key -> score (O(1)查找分数)
    skiplist *SkipList            // 跳表：按 score 排序 (O(log n)范围查询)
}

// 为什么需要两个数据结构？
// 1. 哈希表：快速查找元素的分数 (ZSCORE命令)
// 2. 跳表：支持按分数范围查询 (ZRANGE命令)

// ZADD: 添加成员
func (zs *ZSet) Add(member string, score float64) {
    // 1. 检查是否已存在
    if oldScore, exists := zs.dict[member]; exists {
        // 删除旧的跳表节点
        zs.skiplist.Delete(oldScore, member)
    }

    // 2. 更新哈希表
    zs.dict[member] = score

    // 3. 插入跳表
    zs.skiplist.Insert(score, member, nil)
}

// ZSCORE: 获取分数
func (zs *ZSet) Score(member string) (float64, bool) {
    score, exists := zs.dict[member]
    return score, exists
}

// ZRANGE: 按排名范围查询
func (zs *ZSet) Range(start, stop int) []string {
    values := zs.skiplist.GetRangeByRank(start, stop)

    var members []string
    for _, val := range values {
        if node, ok := val.(*SkipListNode); ok {
            members = append(members, node.key)
        }
    }

    return members
}

// ZRANGEBYSCORE: 按分数范围查询
func (zs *ZSet) RangeByScore(minScore, maxScore float64) []string {
    values := zs.skiplist.SearchRangeByScore(minScore, maxScore)

    var members []string
    for _, val := range values {
        if node, ok := val.(*SkipListNode); ok {
            members = append(members, node.key)
        }
    }

    return members
}

// ZREM: 删除成员
func (zs *ZSet) Remove(member string) bool {
    score, exists := zs.dict[member]
    if !exists {
        return false
    }

    // 1. 删除哈希表
    delete(zs.dict, member)

    // 2. 删除跳表
    zs.skiplist.Delete(score, member)

    return true
}

// 默认 p = 0.5
// 减小 p: 空间开销更小,但查找变慢
// 增大 p: 查找更快,但空间开销更大

const PROBABILITY = 0.25  // 4倍空间减少,查找变慢
const PROBABILITY = 0.5   // 平衡点 (推荐)
const PROBABILITY = 0.75  // 查找更快,但空间开销大

type SkipList struct {
    header *SkipListNode
    tail   *SkipListNode  // 优化：快速访问最后一个元素
}

// ZRANGE -1 -1 (获取最后一个元素) 从 O(n) 降到 O(1)

type SkipListLevel struct {
    forward *SkipListNode
    span    int  // 跨度：到下一个节点的距离
}

// 优化：GetByRank 从 O(n) 降到 O(log n)

// 批量插入：减少锁开销
func (sl *SkipList) BatchInsert(items []Item) {
    sl.mu.Lock()
    defer sl.mu.Unlock()

    for _, item := range items {
        sl.insertInternal(item)  // 无锁版本
    }
}

type SkipList struct {
    // ...
    mu sync.RWMutex
}

func (sl *SkipList) Insert(/*...*/) {
    sl.mu.Lock()
    defer sl.mu.Unlock()
    // ...
}

// 使用 CAS (Compare-And-Swap) 操作
import "sync/atomic"

func (sl *SkipList) Insert(/*...*/) {
    for {
        // 1. 找到插入位置
        // 2. 尝试 CAS 插入
        if atomic.CompareAndSwapPointer(
            (*unsafe.Pointer)(unsafe.Pointer(&update[0].forward[0])),
            unsafe.Pointer(current),
            unsafe.Pointer(newNode),
        ) {
            break  // 成功
        }
        // 失败：重试
    }
}

type SkipList struct {
    segments []*Segment  // 多个分段
}

type Segment struct {
    mu   sync.RWMutex
    list *SkipListNode
}

// 根据 key 的 hash 定位到不同的 segment
// 减少锁竞争

// 提示：添加 backward 指针,支持反向遍历
type SkipListNode struct {
    forward  []*SkipListNode
    backward *SkipListNode  // 反向指针
}

func (sl *SkipList) Count(minScore, maxScore float64) int {
    // TODO: 实现统计逻辑
    // 提示：添加 span 字段加速统计
}

func (sl *SkipList) Serialize() ([]byte, error) {
    // TODO: 实现序列化逻辑
}

func (sl *SkipList) Deserialize(data []byte) error {
    // TODO: 实现反序列化逻辑
}