LevelDB 源码阅读:如何正确测试跳表的并行读写?
在上篇 LevelDB 源码阅读:跳表的原理、实现以及可视化中,从当前二叉搜索树和平衡树的一些缺点出发,引出了跳表这种数据结构。然后结合论文,解释了跳表的实现原理。接着详细分析了 LevelDB 的代码实现,包括迭代器实现,以及并行读的极致性能优化。最后还提供了一个可视化页面,可以直观看到跳表的构建过程。
但是还有两个问题:
- 怎么测试 LevelDB 跳表的代码,保证功能的正确性?特别是怎么保证读写并行情况下跳表实现的正确性。
- 怎么定量分析跳表的时间复杂度?
接下来通过分析 LevelDB 的测试代码,先来回答第一个问题。跳表的性能定量分析,放到另外单独一篇文章。