1
// Redis 跳表层数计算（简化版）
2
int zslRandomLevel(void) {
3
    int level = 1;
4
    // 以 25% 概率继续增加层数
5
    while ((random() & 0xFFFF) < (0.25 * 0xFFFF)) {
6
        level++;
7
    }
8
    return level;
9
}

1
# 添加成员（带分数）
2
ZADD leaderboard 100 "player1"
3
ZADD leaderboard 200 "player2"
4
ZADD leaderboard 150 "player3"
5

6
# 范围查询：获取排名前 10
7
ZRANGE leaderboard 0 9 WITHSCORES
8

9
# 分数范围查询
10
ZRANGEBYSCORE leaderboard 100 200
11

12
# 获取成员排名
13
ZRANK leaderboard "player1"

1
// 跳表插入核心代码（简化版）
2
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
3
    // 1. 找到插入位置
4
    // 2. 随机决定层数
5
    // 3. 创建节点
6
    // 4. 更新各层指针
7
    // 完成！无需复杂的旋转和着色
8
}

1
// Redis 跳表节点定义
2
typedef struct zskiplistNode {
3
    sds ele;                        // 成员对象
4
    double score;                   // 分值
5
    struct zskiplistNode *backward; // 后退指针
6
    struct zskiplistLevel {
7
        struct zskiplistNode *forward;  // 前进指针
8
        unsigned long span;             // 跨度
9
    } level[];  // 柔性数组，层数动态
10
} zskiplistNode;

1
跳表节点大小 ≈
2
    8 (ele指针) +
3
    8 (score) +
4
    8 (backward) +
5
    1.33 * (8 + 8) (level数组)
6
    = 42.64 字节/节点

1
// 红黑树节点定义
2
typedef struct RBNode {
3
    void *key;          // 8 字节
4
    void *value;        // 8 字节
5
    struct RBNode *left;   // 8 字节
6
    struct RBNode *right;  // 8 字节
7
    struct RBNode *parent; // 8 字节
8
    int color;             // 4 字节 + 4 字节对齐
9
} RBNode;

1
红黑树节点大小 ≈ 48 字节/节点

1
// 跳表的无锁插入（简化版）
2
void concurrent_insert(skiplist *list, int key, int value) {
3
    // 1. 找到插入位置（不需要锁）
4
    node *prev = find_position(list, key);
5

6
    // 2. 创建新节点
7
    node *new_node = create_node(key, value);
8

9
    // 3. CAS 设置 next 指针
10
    do {
11
        new_node->next = prev->next;
12
    } while (!CAS(&prev->next, new_node->next, new_node));
13

14
    // 4. 更新上层索引（同样可用 CAS）
15
}

1
// LevelDB 跳表注释
2
// Thread safety
3
// -------------
4
//
5
// Writes require external synchronization.
6
// Reads require a guarantee that the SkipList will not be deleted
7
// while the read is in progress.
8
//
9
// In addition, reads require an iterator to be created.
10
// The iterator is not thread-safe.

1
// HBase MemStore 使用 ConcurrentSkipListMap
2
private final ConcurrentSkipListMap<Cell, Cell> cellSet;

1
# 极端情况：所有节点只有 1 层
2
# 概率：(0.75)^n，当 n=100 时约为 10^-12
3
# 实际中几乎不可能发生

1
ZSET 编码选择：
2
- ziplist/listpack：小规模，紧凑存储
3
- skiplist + dict：大规模，高效查询
4

5
编码切换阈值：
6
- zset-max-ziplist-entries: 128
7
- zset-max-ziplist-value: 64