为什么跳表的同一塔结构中必须存储重复元素？

你的观察非常准确：标准跳表中同一塔的多层节点确实存储了重复的键，存在空间冗余，而你提出的优化思路是可行的——通过让上层节点直接指向底层的唯一节点，确实能消除键的重复存储，同时保留跳表的概率层级特性。但这种设计需要权衡空间节省与操作复杂度的提升，下面具体分析：

一、标准跳表为什么要保留冗余节点 #

标准跳表的冗余是为了实现极简且高效的操作逻辑：

• 标准跳表的每一层都是独立的有序链表，每个节点只维护「同层后继指针」和「下层同塔指针」。查找、插入、删除操作的逻辑高度统一：每一层只做横向的单步比较（和当前节点的后继键比较），如果目标键更大就继续横向走，否则向下跳。
• 这种单指针链的结构不需要维护多子节点列表，代码实现异常简洁，而且横向遍历的缓存友好性更好（同层节点内存分布更连续），实际运行效率很高。

二、你的优化思路的可行性与特性 #

你提出的结构本质是带概率层级的多叉搜索树，核心特性如下：

• 空间冗余消除：每个键只在底层存储一次，上层节点仅作为索引指向底层节点，彻底消除了键的重复存储。
• 概率特性保留：插入时通过抛硬币生成层级的逻辑完全可以复用——新节点的层级依然服从几何分布，理论上的查找/插入时间复杂度仍为O(log n)，和标准跳表一致。
• 操作逻辑调整：查找时需要遍历当前节点的子节点列表，找到第一个键大于目标的位置，选择前一个子节点跳转；插入时需要在对应层级的父节点子列表中找到合适位置插入新节点。

三、这种优化的代价 #

空间节省的同时，会带来几个明显的 trade-off：

• 操作复杂度上升：标准跳表的每个节点仅需维护2-3个指针，而你的结构中每个节点需要维护有序的子节点列表。插入/删除时，需要遍历子节点列表找到位置，时间开销比标准跳表的单步横向比较更高。
• 缓存友好性下降：多叉树的子节点在内存中分散分布，而标准跳表的同层链表节点内存更连续，缓存命中率会更低，实际运行效率可能不如标准跳表。
• 边界处理更复杂：比如处理最小/最大键、空节点等情况时，需要维护子节点列表的有序性，逻辑比标准跳表的单链表遍历更繁琐。

四、更平衡的空间优化方案 #

如果想兼顾空间节省和操作简洁，实际工程中常用的优化是：

• 仅底层存储完整键值对：上层节点只存储键（不存值），这样既保留了标准跳表的单指针链结构，又消除了值的冗余存储，是空间与效率的平衡选择。
• 压缩跳表变种：合并连续的同塔节点，减少上层节点数量，但同样需要调整遍历逻辑，适合对空间要求极高的场景。

内容的提问来源于stack exchange，提问作者Lily-Heather Crawford