LevelDB 源码阅读:如何正确测试跳表的并行读写?

在上篇 LevelDB 源码阅读:跳表的原理、实现以及可视化中,从当前二叉搜索树和平衡树的一些缺点出发,引出了跳表这种数据结构。然后结合论文,解释了跳表的实现原理。接着详细分析了 LevelDB 的代码实现,包括迭代器实现,以及并行读的极致性能优化。最后还提供了一个可视化页面,可以直观看到跳表的构建过程。

但是还有两个问题:

  1. 怎么测试 LevelDB 跳表的代码,保证功能的正确性?特别是怎么保证读写并行情况下跳表实现的正确性
  2. 怎么定量分析跳表的时间复杂度?

接下来通过分析 LevelDB 的测试代码,先来回答第一个问题。跳表的性能定量分析,放到另外单独一篇文章。

阅读全文

实际例子上手体验 OpenAI o1-preview,比预期差一点?

OpenAI 半夜悄咪咪推出了新的模型,introducing-openai-o1-preview。放出了系列视频,展示新模型的强大,网上也是普天盖地的文章来讲新模型测评有多厉害。不过见惯了 AI 界的放卫星,怀着怀疑的态度,第一时间上手体验一把。

汉语新解

刚好最近李继刚有个提示词很火,可以生成很好玩的汉语新解。用 Claude3.5 试了效果特别好,下面是一些 Claude 生成的 SVG 图:

Claude3.5 汉语新解的示例

阅读全文

LevelDB 源码阅读:跳表的原理、实现以及可视化

在 LevelDB 中,内存 MemTable 中的数据存储在 SkipList(跳表) 中,用来支持快速插入。跳表是 William Pugh 在论文 Skip Lists: A Probabilistic Alternative to Balanced Trees 中提出的一种概率性数据结构。有点类似有序链表,但是可以有多层,通过空间换时间,允许快速的查询、插入和删除操作,平均时间复杂度为 $ O(\log n) $。和一些平衡树比起来,代码实现也比较简单,性能稳定,因此应用比较广泛。

跳表实现的启发思路

那么跳表的原理是什么?LevelDB 中跳表又是怎么实现的呢?LevelDB 的跳表实现有哪些亮点以及优化呢?如何支持单线程写,并发读跳表呢?本文将从跳表的原理、实现等方面来深入探讨。最后还提供了一个可视化页面,可以直观看到跳表的构建以及整体结构

阅读全文