本文内容摘自leveldb官方手册，版权归其所有
leveldb是一个写性能十分优秀的存储引擎，是典型的LSM树(Log Structured-Merge Tree)实现。
LSM树的核心思想就是放弃部分读的性能，换取最大的写入能力。
LSM树写性能极高的原理，简单地来说就是尽量减少随机写的次数。
对于每次写入操作，并不是直接将最新的数据驻留在磁盘中，而是将其拆分成
（1）一次日志文件的顺序写
（2）一次内存中的数据插入
leveldb正是实践了这种思想，将数据首先更新在内存中，当内存中的数据达到一定的阈值，将这部分数据真正刷新到磁盘文件中，因而获得了极高的写性能（顺序写60MB/s, 随机写45MB/s）。
leveldb中主要由以下几个重要的部件构成：
memtable就是一个在内存中进行数据组织与维护的结构。
memtable中，所有的数据按用户定义的排序方法排序之后按序存储，等到其存储内容的容量达到阈值时（默认为4MB），
便将其转换成一个不可修改的memtable，与此同时创建一个新的memtable，供用户继续进行读写操作。
memtable底层使用了一种跳表数据结构，这种数据结构效率可以比拟二叉查找树，绝大多数操作的时间复杂度为O(log n)。
memtable的容量到达阈值时，便会转换成一个不可修改的memtable，也称为immutable memtable。
这两者的结构定义完全一样，区别只是immutable memtable是只读的。
当一个immutable memtable被创建时，leveldb的后台压缩进程便会将利用其中的内容，创建一个sstable，持久化到磁盘文件中。
leveldb在写内存之前会首先将所有的写操作写到日志文件中，也就是log文件。
当以下异常情况发生时，均可以通过日志文件进行恢复：
当第一类情况发生时，数据库重启读取log时，发现异常日志数据，抛弃该条日志数据，即视作这次用户写入失败，保障数据库的一致性；
当第二类，第三类，第四类情况发生了，均可以通过redo日志文件中记录的写入操作完成数据库的恢复。
每次日志的写操作都是一次顺序写，因此写效率高，整体写入性能较好。
此外，leveldb的用户写操作的原子性同样通过日志来实现。
除了某些元数据文件，leveldb的数据主要都是通过sstable来进行存储
虽然在内存中，所有的数据都是按序排列的，但是当多个memetable数据持久化到磁盘后，对应的不同的sstable之间是存在交集的，在读操作时，需要对所有的sstable文件进行遍历，严重影响了读取效率。
因此leveldb后台会 定期整合 这些sstable文件，该过程也称为compaction。
随着compaction的进行，sstable文件在逻辑上被分成若干层，由内存数据直接dump出来的文件称为level 0层文件，后期整合而成的文件为level i层文件，这也是leveldb这个名字的由来
leveldb中有个版本的概念，一个版本中主要记录了每一层中所有文件的元数据
元数据包括
（1）文件大小
（2）最大key值
（3）最小key值
该版本信息十分关键，除了在查找数据时，利用维护的每个文件的最大／小key值来加快查找，还在其中维护了一些进行compaction的统计值，来控制compaction的进行
以goleveldb为例，一个文件的元数据主要包括了最大最小key，文件大小等信息；
// tFile holds basic information about a table.
type tFile struct
{
fd storage.FileDesc
seekLeft int32
size int64
imin, imax internalKey
}
一个版本信息主要维护了每一层所有文件的元数据
type version struct
{
s *session // session - version
levels []tFiles // file meta
// Level that should be compacted next and its compaction score.
// Score < 1 means compaction is not strictly needed. These fields
// are initialized by computeCompaction()
cLevel int // next level
cScore float64 // current score
cSeek unsafe.Pointer
closing bool
ref int
released bool
}
当每次compaction完成（或者换一种更容易理解的说法，当每次sstable文件有新增或者减少），leveldb都会创建一个新的version，
创建的规则是:
versionNew = versionOld + versionEdit
versionEdit指代的是基于旧版本的基础上，变化的内容（例如新增或删除了某些sstable文件）
manifest文件就是用来记录这些versionEdit信息的。
一个versionEdit数据，会被编码成一条记录，写入manifest文件中。
例如下图便是一个manifest文件的示意图，其中包含了3条versionEdit记录，
每条记录包括
（1）新增哪些sst文件
（2）删除哪些sst文件
（3）当前compaction的下标
（4）日志文件编号
（5）操作seqNumber等信息
通过这些信息，leveldb便可以在启动时，基于一个空的version，不断apply这些记录，最终得到一个上次运行结束时的版本信息
这个文件的内容只有一个信息，就是记载当前的manifest文件名。
因为每次leveldb启动时，都会创建一个新的Manifest文件。因此数据目录可能会存在多个Manifest文件。
Current则用来指出哪个Manifest文件才是我们关心的那个Manifest文件
leveldb的一次写入分为两部分：
leveldb对外提供的写入接口有：
（1）Put
（2）Delete两种
这两种本质对应同一种操作，Delete操作同样会被转换成一个value为空的Put操作
除此以外，leveldb还提供了一个批量处理的工具Batch，用户可以依据Batch来完成批量的数据库更新操作，且这些操作是原子性的
batch的组织结构
在batch中，每一条数据项都按照上图格式进行编码。每条数据项编码后的第一位是这条数据项的类型（更新还是删除），之后是数据项key的长度，数据项key的内容；
若该数据项不是删除操作，则再加上value的
长度，value的内容
batch中会维护一个size值，用于表示其中包含的数据量的大小。
该size值为所有数据项key与value长度的累加，以及每条数据项额外的8个字节。
这8个字节用于存储一条数据项额外的一些信息
当数据项从batch中写入到内存数据库中是，需要将一个key值的转换，
即在leveldb内部，所有数据项的key是经过特殊编码的，这种格式称为internalKey
internalkey在用户key的基础上，尾部追加了8个字节，用于存储
（1）该操作对应的 sequence number
（2）该操作的类型
其中，每一个操作都会被赋予一个sequence number。该计时器是在leveldb内部维护，每进行一次操作就做一个累加。由于在leveldb中，一次更新或者一次删除，采用的是append的方式，并非直接更新原数据。因此对应同样一个key，会有多个版本的数据记录，而最大的*sequence number**对应的数据记录就是最新的
此外，leveldb的快照（snapshot）也是基于这个sequence number实现的，即每一个sequence number代表着数据库的一个版本
在面对并发写入时，在同一个时刻，只允许一个写入操作将内容写入到日志文件以及内存数据库中。
为了在写入进程较多的情况下，减少日志文件的小写入，增加整体的写入性能，leveldb 将一些“小写入”合并成一个“大写入”
流程如下：
leveldb的任意一个写操作（无论包含了多少次写），其原子性都是由日志文件实现的。一个写操作中所有的内容会以一个日志中的一条记录，作为最小单位写入
考虑以下两种异常情况：
前者中可能存储一个写操作的部分写已经被记载到日志文件中，仍然有部分写未被记录，这种情况下，当数据库重新启动恢复时，读到这条日志记录时，发现数据异常，直接丢弃或退出，实现了写入的原子性保障
后者，写日志已经完成，已经数据未真正持久化，数据库启动恢复时通过redo日志实现数据写入，仍然保障原子性
下章节介绍
leveldb提供给用户两种进行读取数据的接口：
两者的本质是一样的，只不过第一种调用方式默认地以当前数据库的状态创建了一个snapshot，并基于此snapshot进行读取
snapshot（快照）就是数据库在某一个时刻的状态。
基于一个快照进行数据的读取，读到的内容不会因为后续数据的更改而改变。
由于两种方式本质都是基于快照进行读取的
快照代表着数据库某一个时刻的状态，在leveldb中，作者巧妙地用一个整型数来代表一个数据库状态。
在leveldb中，用户对同一个key的若干次修改（包括删除）是以维护多条数据项的方式进行存储的（直至进行compaction时才会合并成同一条记录），每条数据项都会被赋予一个序列号，代表这条数据项的新旧状态。一条数据项的序列号越大，表示其中代表的内容越新
因此，每一个序列号，其实就代表着leveldb的一个状态。换句话说，每一个序列号都可以作为一个状态快照
利用快照能够保证数据库进行并发的读写操作
在 获 取 到 一 个 快 照 之 后 ，leveldb会 为 本 次 查 询 的key构 建 一 个internalKey（ 格 式 如 上 文 所 述 ） ， 其中internalKey的seq字段使用的便是快照对应的seq。
通过这种方式可以过滤掉所有seq大于快照号的数据项
leveldb 读取分为三步：
为了防止写入内存的数据库因为进程异常、系统掉电等情况发生丢失，leveldb在写内存之前会将本次写操作的内容写入日志文件中
在leveldb中，有两个memory db，以及对应的两份日志文件。其中一个memory db是可读写的，当这个db的数据量超过预定的上限时，便会转换成一个不可读的memory db，与此同时，与之对应的日志文件也变成一份frozen log
而新生成的immutable memory db则会由后台的minor compaction进程将其转换成一个sstable文件进行持久化，持久化完成，与之对应的frozen log被删除
为了增加读取效率，日志文件中按照block进行划分，每个block的大小为32KiB
每个block中包含了若干个完整的chunk
一条日志记录包含一个或多个chunk。
每个chunk包含了一个7字节大小的header，前4字节是该chunk的校验码，紧接的2字节是该chunk数据的长度，以及最后一个字节是该chunk的类型。其中checksum校验的范围包括chunk的类型以及随后的data数据
chunk共有四种类型：
full，first，middle，last
一条日志记录若只包含一个chunk，则该chunk的类型为full
若一条日志记录包含多个chunk，则这些chunk的第一个类型为first, 最后一个类型为last，中间包含大于等于0个middle类型的chunk
由于一个block的大小为32KiB，因此当一条日志文件过大时，会将第一部分数据写在第一个block中，且类型为first，若剩余的数据仍然超过一个block的大小，则第二部分数据写在第二个block中，类型为middle，最后剩余的数据写在最后一个block中，类型为last
日志的内容为写入的batch编码后的信息
一条日志记录的内容包含：
其中header中有
（1）当前db的sequence number
（2）本次日志记录中所包含的put/del操作的个数。紧接着写入所有batch编码后的内容
在leveldb内 部 ， 实 现 了 一 个journal的writer
首 先 调 用Next函 数 获 取 一个singleWriter，这个singleWriter的作用就是写入一条journal记录
singleWriter开始写入时，标志着第一个chunk开始写入。在写入的过程中，不断判断writer中buffer的大小，若超过32KiB，将chunk开始到现在做为一个完整的chunk，为其计算header之后将整个block写入文件。与此同时reset buffer，开始新的chunk的写入
若一条journal记录较大，则可能会分成几个chunk存储在若干个block中
为了避免频繁的IO读取，每次从文件中读取数据时，按block（32KiB）进行块读取
每次读取一条日志记录，reader调用Next函数返回一个singleReader
singleReader每次调用Read函数就返回一个chunk的数据。每次读取一个chunk，都会检查这批数据的校验码、数据类型、数据长度等信息是否正确，若不正确，且用户要求严格的正确性，则返回错误，否则丢弃整个chunk的数据
循环调用singleReader的read函数，直至读取到一个类型为Last的chunk，表示整条日志记录都读取完毕，返回
本章节关于跳表内容源自 wangzheng0822/algo，版权归wangzheng0822所有。
【强烈推荐作者课程 数据结构与算法之美！】
支持快速地：
某些情况下，跳表甚至可以替代红黑树（Red-Black tree）。Redis 当中的有序集合（Sorted Set）是用跳表实现的。
跳表是对链表的改进。对于单链表来说，即使内容是有序的，查找具体某个元素的时间复杂度也要达到
O
(
n
)
O(n)
O(n)。对于二分查找来说，由于链表不支持随机访问，根据 first 和 last 确定 cut 时，必须沿着链表依次迭代 std::distance(first, last) / 2 步；特别地，计算 std::(first, last) 本身，就必须沿着链表迭代才行。此时，二分查找的效率甚至退化到了
O
(
n
log
n
)
O(n \log n)
O(nlogn)，甚至还不如顺序遍历。
跳表的核心思想是用空间换时间，构建足够多级数的索引，来缩短查找具体值的时间开销。
例如对于一个具有 64 个有序元素的五级跳表，查找起来的过程大约如下图所示。
对于一个每一级索引的跨度是下一级索引
k
k
k 倍的跳表，每一次 down 操作，相当于将搜索范围缩小到「剩余的可能性的
1
/
k
1 / k
1/k」。因此，查找具体某个元素的时间复杂度大约需要
⌊
log
k
n
⌋
+
1
\lfloor \log_k n\rfloor + 1
⌊logkn⌋+1 次操作；也就是说时间复杂度是
O
(
log
n
)
O(\log n)
O(logn)。
前面说了，跳表是一种用空间换时间的数据结构。因此它的空间复杂度一定不小。我们考虑原链表有 n n n 个元素，那么第一级索引就有 n / k n / k n/k 个元素，剩余的索引依次有 n / k 2 n / k^2 n/k2, n / k 3 n / k^3 n/k3, …, 1 1 1 个元素。总共的元素个数是一个等比数列求和问题，它的值是 n − 1 k − 1 \frac{n - 1}{k - 1} k−1n−1。可见，不论 k k k 是多少，跳表的空间复杂度都是 O ( n ) O(n) O(n)；但随着 k k k 的增加，实际需要的额外节点数会下降。
对于链表来说，插入或删除一个给定结点的时间复杂度是 O ( 1 ) O(1) O(1)。因此，对于跳表来说，插入或删除某个结点，其时间复杂度完全依赖于查找这类结点的耗时。而我们知道，在跳表中查找某个元素的时间复杂度是 O ( log n ) O(\log n) O(logn)。因此，在跳表中插入或删除某个结点的时间复杂度是 O ( log n ) O(\log n) O(logn)。
为了维护跳表的结构，在不断插入数据的过程中，有必要动态维护跳表的索引结构。一般来说，可以采用随机层级法。具体来说是引入一个输出整数的随机函数。当随机函数输出 K K K，则更新从第 1 1 1 级至第 K K K 级的索引。为了保证索引结构和数据规模大小的匹配，一般采用二项分布的随机函数。
内存数据库中，key称为internalKey，其由三部分组成：
用户定义的key：这个key值也就是原生的key值；
序列号：leveldb中，每一次写操作都有一个sequence number，标志着写入操作的先后顺序。由于在leveldb中，可能会有多条相同key的数据项同时存储在数据库中，因此需要有一个序列号来标识这些数据项的新旧情况。序列号最大的数据项为最新值；
类型：标志本条数据项的类型，为更新还是删除
比较规则：
ukey），若用户定义key值大，整个internalKey就大；以goleveldb为示例，内存数据库的定义如下
type DB struct
{
cmp comparer.BasicComparer
rnd *rand.Rand
mu sync.RWMutex
kvData []byte
// Node data:
// [0] : KV offset
// [1] : Key length
// [2] : Value length
// [3] : Height
// [3..height] : Next nodes
nodeData []int
prevNode [tMaxHeight]int
maxHeight int
n int
kvSize int
}
其中kvData用来存储每一条数据项的key-value数据，nodeData用来存储每个跳表节点的链接信息。
nodeData中，每个跳表节点占用一段连续的存储空间，每一个字节分别用来存储特定的跳表节点信息。
• 第一个字节用来存储本节点key-value数据在kvData中对应的偏移量；
• 第二个字节用来存储本节点key值长度；
• 第三个字节用来存储本节点value值长度；
• 第四个字节用来存储本节点的层高；
• 第五个字节开始，用来存储每一层对应的下一个节点的索引值；
Put、Get、Delete、Iterator等操作均依赖于底层的跳表的基本操作实现