面试题：Redis跳跃表在有序集合中的插入操作原理

Question

请阐述在Redis的有序集合中，当使用跳跃表结构插入一个新元素时，其具体的操作步骤和实现逻辑是什么？

Answer 1

1. 确定插入位置
   • 从跳跃表的顶层开始，通过比较新元素的分值与当前节点的分值来决定移动方向。
   • 如果新元素分值小于当前节点分值，或者分值相等但字典序小于当前节点，向左移动；否则向下移动。
   • 重复上述步骤，直到到达最底层找到合适的插入位置。
2. 更新指针
   • 记录从顶层到最底层路径上每个层遇到的最后一个节点，这些节点的右指针需要更新以包含新插入的节点。
   • 创建新节点，新节点的分值为要插入元素的分值，指针数组大小根据随机函数生成的层数确定。
   • 对于每个记录的节点，将其右指针指向新节点，新节点的左指针指向该记录节点。
   • 同时更新新节点右指针指向的原节点的左指针，使其指向新节点。
3. 随机确定新节点层数
   • Redis跳跃表采用抛硬币的方式来随机决定新节点的层数。
   • 每次抛硬币，如果结果为正面（通常概率设为0.5），则层数加1，继续抛硬币，直到结果为反面为止。
   • 最终确定新节点的层数，保证跳跃表结构大致平衡，提高查找、插入和删除操作的效率。