跳表Redis中的随机高度特性（redis的跳表高度随机）

跳表：Redis中的随机高度特性

跳表（Skip List）是一种基于有序链表的数据结构，它可以快速地进行查找、插入和删除操作，而且实现相对简单。跳表的数据结构类似于一组有序的链表，每一层链表存在数据的概率比下一层链表小。跳表的本质是一种平衡的竖向拆分，其高度随机，跳表中每个元素的升高概率是1/2，也就是说在跳表中找到任意一个元素的开销等于它在单链表中的平均开销。

在Redis中，跳表被作为有序集合的底层结构，实现了对有序集合的快速插入、查找和删除。Redis的跳表实现中，有一个非常重要的特性，就是高度的随机性特性。通过在每次插入操作时对节点的高度进行随机，让节点的高度分布的可能性更加平均，从而提高跳表的效率。

下面是Redis中跳表中节点高度的生成方法：

/*
 * redis.h/sdskiplistRandomLevel() 
 * Redis 中跳表节点高度产生算法 
 */
unsigned int sdskiplistRandomLevel(void) {
    unsigned int level = 1;
    while ((random() & 0xFFFF) 
        level += 1;
    return (level 
}

其中`REDIS_SKIPLIST_P`是一个宏定义，决定了每插入一个新节点，新节点的高度升高的概率为1/`REDIS_SKIPLIST_P`。在上面的代码中，使用了一个随机数生成器`random()`，用于生成一个范围在0到`0xFFFF`(即65535)之间的随机数，如果这个数小于`REDIS_SKIPLIST_P * 0xFFFF`，则节点的高度加1。这个判断的意义在于，让新节点的高度分布更加均匀，从而提高整个跳表的效率。

跳表的高度成倍增长，即第i层的节点数比（i+1）层少一半，而第1层的节点数最多，所以跳表的高度，一般不会超过logN+1（其中N为节点数）。

跳表在Redis中的应用主要体现在有序集合这个数据结构中。当有序集合需要查找一个元素的时候，Redis就会通过跳表来进行查找。在无序集合中，这个操作的时间复杂度为O(N)，而有了跳表的帮助，这个时间复杂度就能够降低到O(logN)，大大提高了Redis的效率。

此外，跳表还有其他的应用场景，例如在搜索引擎中，可以用跳表来优化搜索关键字的索引；在游戏开发中，可以用跳表来优化游戏世界中的场景判断等等。

跳表是一种高效的数据结构，可以对某些场景下的查找操作进行优化，它在Redis中被加入了随机高度特性，提高了在有序集合中的效率。