这是关于 LevelDB 跳表的系列文章的最后一篇，详细分析了跳表的时间复杂度。通过分解搜索问题、反转整个搜索过程以及找到合适的 L 层，最终推导出跳表的时间复杂度。基于对时间复杂度的理解，进一步推导了如何选择概率 p 以及 Redis 和 LevelDB 跳表中选择最大高度的原因。最后通过简单的基准测试测试了跳表的性能并与 unordered_map 进行了比较。

主要内容包括：

• 跳表性能分析拆解：极端情况下跳表性能差于平衡树，平均性能与平衡树类似，引入随机高度可保证平均性能。需分析跳表操作中影响时间消耗的部分、搜索操作平均复杂度、找到最有效搜索起始层及计算总时间复杂度等问题。
• 跳表操作瓶颈：跳表操作时间复杂度由搜索操作复杂度决定，搜索操作是在跳表中向右向下搜索直到找到目标元素，直接分析搜索操作平均复杂度较难。
• 跳过 k 层的期望步数：从任意层 k 开始向下搜索找到目标位置的平均步数为$k/p$，此公式很重要，但仍不能直接分析跳表平均性能。
• 从哪层开始搜索：理想是从“合适”层开始搜索，论文定义合适层为期望有$1/p$个节点的层，通常选择 p 为 1/2、1/4 等，从该层开始搜索可避免不必要工作且不失跳表优势，需知道该层平均高度并结合$k/p$计算整体搜索复杂度。
• 层级高度计算：假设跳表有 n 个节点，在第 L 层有$1/p$个节点，通过推导可得$L = log_{1/p} n$，结合前面结论可得跳表搜索过程的时间复杂度为$O(log n)$。
• p 值选择：论文分析了 p 值选择对性能和空间占用的影响，推荐 p = 1/4，LevelDB 和 Redis 的 zset 实现都选择了 p = 1/4，Redis 选择 32 级是因为要支持 2^64 个元素，LevelDB 选择 12 级是因为存储的键数量不会很大。
• 性能测试基准：使用 Google 的基准测试库测试跳表的插入和搜索性能，并与 unordered_map 比较，测试结果表明跳表长度增加时插入时间增加不明显，搜索性能与 unordered_map 差别不大。

总的来说，通过对跳表的深入分析和测试，更好地理解了跳表的性能和特点。