LevelDB 是一个开源的可持久化的key-value数据库，是nosql数据库，在这边文章，我们来系统的了解一下levelDB。

1. 使用场景

LevelDB 是一个高性能的键值存储库，拥有快速读写、简单接口和可靠性等特点，因此在很多需要高效存储和读取的场景中得到了广泛应用，例如日志场景、消息队列等等。

在使用上，我们会发现LevelDB与Redis、memchched很类似，都是k-v类型的操作。但是其定位还是有很大不同的，对于Redis和memchched，其数据操作都是基于内存的，而LevelDB不同，其数据操作并不是完全的内存操作，其本质还是需要持久化的数据库。因此，LevelDB虽然可以作为缓存使用，但是其本身还是更适合用于非关系性数据的存储之用。

2. 数据结构

2.1. LSM树

LevelDB 采用 LSM 树 (Log-Structured Merge-Tree) 作为其内部数据结构。要理解LSM 树，我们需要明确两个计算机的基本共识：

• 内存操作远快于磁盘操作。
• 磁盘的顺序操作远快于随机操作。

1. 写操作

前面我们提到过，LevelDB本质还是数据库，因此需要保证数据库事务的持久性，MySQL是通过binlog日志来做到的，LevelDB的想法也类似，数据增删改操作优先写入WAL日志，用于在系统崩溃时恢复数据，这个过程是顺序写入的。之后，数据会写入内存中的MemTable，之后，再由其他线程异步将数据写入磁盘的SSTable，此外，LevelDB会定期将多个 SSTable 合并、压缩成新的 SSTable，减少数据重复和消除过期数据。

1. 读操作

LevelDB会先读内存中的MemTable，找不到时再去读磁盘中的SSTable，提升数据读取的效率。

2.2. 跳表

LevelDB在内存中的数据结构是跳表，跳表（Skip List）是一种基于链表的数据结构，旨在平衡链表的动态插入与删除操作的同时，提供接近于树结构的数据访问性能。跳表通过多级链表来加速节点的搜索、插入和删除操作，更直观、更易于实现，且在理论上可以提供类似于平衡树的性能。

跳表的核心思想是通过构建多层索引，使得每次搜索都能“跳过”一部分元素，从而在链表基础上提高搜索效率。跳表的每一层都是一个有序链表，最底层包含所有数据，而上面的每一层是对其下层链表的抽样，以此类推。

跳表的主要操作包括搜索、插入和删除，所有这些操作的时间复杂度在平均情况下都是 O(log n)，其中 n 是元素的数量。

LevelDB 的内存中维护了 2 个跳表，rtable用于只读，wtable同时用于修改与读取。 当LevelDB 有修改操作时，并不是直接修改跳表中的值，而是像日志一样，在wtable中追加一个操作指令，当指令追加到一定程度后，wtable的节点就会同步到rtable，rtable的数据会通过异步线程更新到磁盘的SSTable中。

查询数据时，也是通过wtable->rtable->SSTable的顺序。

2.3. SSTable

通过上面的学习，我们可以知道，LevelDB中的一个key会生成很多个SSTable，SSTable在磁盘中是分层级存储的，rtable的数据只会直接写入L0层次，而当数据从L0下沉时，重复的key会merge，之后会进行有序排列，提升搜索效率。

3. LevelDB的优化设计

3.1. 布隆过滤器

LevelDB 为了进一步减少磁盘读的次数，在每个磁盘文件上又加了一层布隆过滤器，内存中找不到数据时，会先走布隆过滤器，可以直接将磁盘读次数大幅减少。

3.2. 缓存

LevelDB 的内存中存储了一笔最近读写的热数据，如果请求的数据在热数据中查不到就需要去磁盘文件中去查找，效率就会大幅降低。LevelDB 为了降低磁盘文件的搜寻次数，增加了块缓存，缓存了近期频繁使用的数据块解压缩之后的内容。