在现代多核服务器环境中，选择合适的索引数据结构直接影响系统的并发吞吐量与响应延迟。Skip 列表作为一种概率平衡的层次化链表，自 1990 年由 William Pugh 提出以来，因其简洁的实现与天然的并发友好性，在高并发内存索引场景中持续受到关注。本文从工程实践角度，分析 Skip 列表在并发索引中的优势与局限，并对比 B + 树与红黑树的性能权衡。
Skip 列表的并发友好性原理
Skip 列表的核心结构由多层有序链表叠加而成：底层包含完整的有序元素序列，上层作为快速通道逐层跳跃。搜索操作从最高层开始，沿当前层向右遍历直至超过目标值，然后下降一层继续搜索。这种层次结构天然支持无锁或细粒度锁的实现方式 —— 每个节点的指针更新仅影响局部路径，其他线程可以并发遍历不受影响。
与 B + 树或红黑树需要全局平衡操作不同，Skip 列表的插入仅涉及局部节点的前向指针修改，无需触发大规模的树结构调整。研究表明，设计良好的无锁 Skip 列表在多核环境下能够实现接近线性的扩展性，这是因为不同线程操作不同层级时天然形成物理隔离。
然而，这种并发优势并非没有代价。由于采用指针跳跃的访问模式，Skip 列表在遍历过程中会产生较多的缓存未命中 —— 每跨入下一个节点都可能导致一次内存随机访问。相比经过精心布局的 B + 树节点，Skip 列表的缓存局部性明显较差，这是工程实现中必须正视的性能瓶颈。
B + 树：缓存友好的传统选择
B + 树一直是数据库索引的默认选项，其根本原因在于对缓存友好的节点结构与出色的范围查询性能。B + 树的所有数据指针集中在叶子层且通过双向链表串联，顺序扫描时能够充分利用预取机制，缓存命中率远高于 Skip 列表。
在并发写入场景下，传统 B + 树的节点分裂与合并操作需要持有较粗粒度的锁，可能造成访问热点。但现代优化后的 B + 树实现采用细粒度锁或乐观并发控制，在多数工作负载下仍能保持较高吞吐量。实测数据显示，经过缓存优化的 B + 树在混合读写工作负载中通常比 Skip 列表高出 2 到 8 倍的吞吐量。
对于注重范围查询性能、追求可预测延迟的工程场景，B + 树仍是更稳妥的选择。其确定性更强的树高也意味着更稳定的访问延迟 —— 这在延迟敏感的在线服务中尤为关键。
红黑树：平衡性与实现复杂度
红黑树作为自平衡二叉搜索树，提供最坏情况 O (log n) 的时间复杂度保证，天然比 Skip 列表具有更强的确定性。然而在并发环境下，维持严格的平衡需要复杂的旋转操作，锁粒度往往难以精细化。
实践中，红黑树在并发写入时容易成为瓶颈 —— 每次插入或删除都可能触发从叶子到根路径上的平衡调整，导致较长的事务持有时间。相比之下，Skip 列表的层次结构允许更细粒度的并发控制。
红黑树的优势在于内存占用紧凑 —— 每个节点仅需两个指针与一个颜色位，比 Skip 列表的多个前向指针更节省空间。在内存受限或节点数量巨大的场景中，这一特性可能成为选择的关键因素。
工程实践的关键决策点
选择 Skip 列表、B + 树还是红黑树，需要基于具体工作负载特征做出判断。读多写少且重视并发实现的简洁性时，Skip 列表的无锁实现能够大幅降低工程复杂度。写密集或范围查询占比高的场景，B + 树的缓存友好性优势显著。需要严格最坏情况保障且内存敏感时，红黑树的确定性表现更佳。
现代系统也出现混合使用两种结构的趋势 —— 例如 LevelDB 在内存索引中采用 Skip 列表而在磁盘层使用 B + 树，或在 Skip 列表基础上引入 B 树的节点组织方式形成 B-Skiplist 变体，在特定场景下可实现 2 到 9 倍的吞吐量提升。
结论
Skip 列表在并发索引场景中提供了实现简洁性与并发友好性的平衡，但其缓存未命中问题限制了绝对性能上限。B + 树凭借出色的缓存局部性仍是大多数数据库场景的首选，而红黑树在需要确定性性能保证时保留其价值。工程决策应基于工作负载的读，写，比例、范围查询频率与延迟敏感度综合评估，而非机械套用某一种数据结构。
参考资料
- Parallelizing Skip Lists for In-memory Multi-core Database Systems
- Bridging Cache-Friendliness and Concurrency: A Locality-Optimized In-Memory B-Skiplist
内容声明：本文无广告投放、无付费植入。
如有事实性问题，欢迎发送勘误至 i@hotdrydog.com。