鸿篇巨制 —— LevelDB 的整体架构

本节信息量很大，我们要从整体上把握 LevelDB 这座大厦的结构。当我们熟悉了整体的结构，接下来就可以各个击破来细致了解它的各种微妙的细节了。

一个比喻

LevelDB 有点类似于建筑，分为地基和地面两部分，也就是磁盘和内存，而地基又好比地壳结构分了很多层级，不同层级的数据还会定期从上往下移动 —— 沉积作用。如果磁盘底层的冷数据被修改了，它又会再次进入内存，一段时间后又会被持久化刷回到磁盘文件的浅层，然后再慢慢往下移动到底层，周而复始就好比地球水循环。

内存结构

LevelDB 的内存中维护了 2 个跳跃列表，一个是只读的 rtable，一个是可修改的 wtable。跳跃列表在我的另一本书《Redis 深度历险》中有详细讲解，这里就不再细致重复说明。简单理解，跳跃列表就是一个 Key 有序的 Set 集合，排序规则由全局的「比较器」决定，默认是字典序。跳跃列表的查找和更新操作时间复杂度都是 Log(n)。

跳跃列表是由多个层次的链表构成，其中底层的链表存储了所有的 Key，它们是有序的。普通链表并不支持快速二分查找，但是跳跃链表的特殊结构可以让底层的链表以近似二分查找算法的效率定位到指定节点。简单理解就是跳跃列表同时具备了有序数组的快速定位能力和链表的高效增删能力。但是它会付出一定的代价，在实现上有一定的复杂度。

如果跳跃列表只存 Key，那 Value 存哪里呢？答案是 Value 也存在跳跃列表的 Key 中。跳跃列表中存储的 Key 比较特殊，它是一个复合结构字符串，它同时包含了键值对的 Key 和 Value。

其中 sequence 为全局自增序列号，LevelDB 遇到一个修改操作，全局序列号自动加一。LevelDB 中的 Key 存储了多个版本的 Value。LevelDB 使用序列号来标记键值对的版本，序列号越大，对应的键值对越新。

type 为数据类型，标记是 Put 还是 Delete 操作，只有两个取值，0 表示 Delete，1 表示 Put。

internal_key = key + sequence + type
Key = internal_key_size + internal_key + value_size + value