LevelDB 源码阅读：如何分析跳表的时间复杂度？
在上篇 LevelDB 源码阅读：跳表的原理、实现以及可视化中，详细分析了 LevelDB 中跳表的实现。然后在 LevelDB 源码阅读：如何正确测试跳表的并行读写？ 中，分析了 LevelDB 跳表的测试代码，最后还剩下一个问题，怎么分析跳表的时间复杂度呢？
在分析完跳表的时间复杂度之后，就能明白 LevelDB 中概率值和最大高度的选择，以及 Redis 为什么选择不同的最大高度。最后本文也会提供一个简单的压测代码，来看看跳表的性能如何。
本文不会有很高深的数学知识，只涉及简单的概率论，可以放心往下看。跳表的性能分析有不少思路很值得借鉴，希望本文能抛砖引玉，给大家带来一些启发。
跳表性能分析拆解
在知道 LevelDB 的原理和实现后，我们可以推测出来，在极端情况下，每个节点的高度都是 1，那么跳表的查找、插入、删除操作的时间复杂度都会退化到 O(n)。在这种情况下，性能比平衡树差了不少。当然，因为有随机性在里面，所以没有输入序列能始终导致性能最差。
那么跳表的平均性能如何呢？前面给出过结论，和平衡树的平均性能差不多。引入一个简单的随机高度，就能保证跳表的平均性能和平衡树差不多。这背后有没有什么分析方法，能够分析跳表的性能呢？
