面试题：Redis跳跃表的插入与删除机制

Question

详细说明在Redis跳跃表中插入和删除一个节点的具体过程，包括如何调整各层指针以及维持跳跃表的平衡特性？

Answer 1

插入节点过程

1. 确定插入位置：
   • 从跳跃表的顶层（通常是最高层）开始，沿着当前层的指针向右查找，直到找到一个节点，其值大于要插入的值，或者到达链表末尾。
   • 然后下降到下一层，重复上述查找过程，直到最底层。这样就确定了新节点在每一层的插入位置。
2. 生成新节点的层数：
   • 随机生成一个层数，一般采用抛硬币的方式，正面则层数加1，直到达到最大层数限制或硬币为反面。Redis中跳跃表默认最大层数为32层。
3. 创建新节点：
   • 根据生成的层数创建新节点，节点包含要插入的值以及对应层数的指针数组。
4. 调整指针：
   • 从顶层开始，在每一层找到要插入位置的前驱节点，将前驱节点的指针指向新节点，新节点的指针指向原来前驱节点的后继节点。这样在每一层都完成新节点的插入，调整了各层指针。

删除节点过程

1. 查找节点：
   • 与插入节点类似，从顶层开始，沿着当前层指针向右查找，直到找到值等于要删除值的节点，同时记录下每一层该节点的前驱节点。
2. 调整指针：
   • 从顶层开始，若该层存在要删除的节点，将前驱节点的指针绕过要删除的节点，直接指向其后继节点，依次处理每一层，从而删除节点在各层的连接。
3. 释放节点内存：
   • 完成各层指针调整后，释放被删除节点占用的内存空间。

跳跃表平衡特性维持

1. 随机层数生成：
   • 通过随机生成节点的层数，使得跳跃表在插入和删除节点时，整体结构不会出现过于偏向某一侧的情况。例如，新插入节点的层数有一定概率与已有的高层节点匹配，从而维持高层节点的稀疏性和底层节点的密集性，保证查找效率。
2. 动态调整：
   • 跳跃表不依赖严格的平衡算法（如AVL树的高度平衡），而是依靠插入和删除过程中的随机层数生成，在大量操作后，自然地使节点分布相对均匀，维持跳跃表在查找效率上的平衡特性。例如，多次插入和删除操作后，高层节点和底层节点的比例依然能保持在一个合理范围，不会因为某几个极端操作导致结构严重失衡。