面试题：Redis跳跃表构建过程中的关键步骤是什么

Question

请阐述在Redis中构建跳跃表时，从底层链表开始到构建多层索引链表的关键步骤，包括节点的创建、层数的随机化确定等方面。

Answer 1

1. 底层链表构建：
   • 节点创建：为每个要插入跳跃表的数据项创建一个跳跃表节点。每个节点包含数据域（存放实际数据）、多个指针域（用于不同层的索引链表），以及用于指向下一节点的指针（在底层链表中）。例如，在C语言实现中，节点结构可能类似如下定义：

typedef struct zskiplistNode {
    sds ele; // 数据域，sds是Redis自定义的字符串结构
    double score; // 用于排序的分数
    struct zskiplistNode *backward; // 指向前驱节点，仅在底层链表和最高层索引链表中使用
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 指向下一节点
        unsigned int span; // 跨度，记录当前节点到forward节点之间经过的节点数（包括forward节点）
    } level[]; // 柔性数组，根据节点层数动态分配内存
} zskiplistNode;

• 链表插入：按照数据的排序规则（通常是根据某个分数值），将新节点插入到底层链表的合适位置。在插入过程中，需要调整前后节点的指针，确保链表的顺序性。

2. 层数随机化确定：
   • 随机函数：Redis使用一个随机函数来确定新节点的层数。这个随机函数通常基于一定的概率分布。在Redis中，使用了一种简单的基于抛硬币的思想。具体来说，每次以一定概率（通常设置为1/2）决定是否增加一层。例如，在C语言实现中可能类似如下代码：

int zslRandomLevel(void) {
    int level = 1;
    while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level < ZSKIPLIST_MAXLEVEL)? level : ZSKIPLIST_MAXLEVEL;
}

• 最大层数限制：为了防止层数过高导致内存消耗过大和查询效率降低，会设置一个最大层数限制（在Redis中通常设置为32层，即ZSKIPLIST_MAXLEVEL）。如果随机生成的层数超过这个限制，则使用最大层数。

3. 多层索引链表构建：
   • 索引节点创建：根据随机确定的层数，为新节点分配相应数量的指针域（即level数组的大小）。每个指针域用于指向不同层索引链表中的下一个节点。
   • 索引链表插入：从最高层到最低层（通常是从随机生成的层数到第1层），将新节点插入到相应层的索引链表中。在插入过程中，需要找到合适的插入位置。通过从跳跃表的头节点开始，沿着每层的forward指针，根据节点的分数值比较，找到需要插入的位置。在插入时，不仅要调整新节点在该层的forward指针，还要调整前一节点的forward指针指向新节点，并更新跨度值span。例如，如果在第i层，新节点newNode要插入到prevNode和nextNode之间，代码实现大致如下：

newNode->level[i].forward = nextNode;
prevNode->level[i].forward = newNode;
newNode->level[i].span = nextNode->level[i].span - (rank[0] - rank[i]);
prevNode->level[i].span = rank[0] - rank[i] + 1;

• 底层链表与索引链表关联：底层链表中的节点通过不同层的指针与相应的索引链表节点关联，从而形成完整的跳跃表结构。这样在查询时，可以通过多层索引快速定位到目标节点所在的范围，然后在底层链表中精确查找。