存储引擎
概括来讲，存储引擎分为两大类：针对事务处理（OLTP）优化的结构，以及针对分析型（OLAP）的优化结构。它们典型的访问模式存在很大的差异：
OLTP系统通常面向用户，这意味着它们可能收到大量的请求。为了处理负载，应用程序通常在每个用户查询中只涉及小量的记录。应用程序基于某种键来请求记录，而存储引擎使用索引来查找所请求的数据。磁盘寻道时间往往是瓶颈。
由于不直接面对最终用户，数据仓库和类似的分析系统相对并不太广为人知，它们主要由业务分析师使用。处理的查询请求数目远低于OLTP系统，但每个查询通常要求非常苛刻，需要在短时间内扫描百万条记录。磁盘带宽（不是寻道时间）通常是瓶颈，而面向列的存储对于这种工作负载成为日益流行的解决方案。 在OLTP方面，有两个主要流派的存储引擎：
日志结构流派：它只允许追加方式更新文件和删除过时的文件，但不会修改已写入的文件。BitCask、SSTable、LST-Tree、LevelDB、Cassandra、HBase、Lucence等属于此类；
原地更新流派：将磁盘视为可以覆盖的一组固定大小的页。B-Tree是这个哲学的最典型代表，它已用于所有主要的关系数据库，以及大量的非关系数据库。
日志结构的存储引擎是一个相对较新的方案。其关键思想是系统地将磁盘上随机访问写入转为顺序写入，由于硬盘驱动器和SSD的性能特性，可以实现更高的写入吞吐量。下面将针对这两种存储引擎进行分析。
1. LSM-Tree
LSM-Tree(Log-Structured Merge
Tree)广泛用于key-value存储引擎库中，如LevelDB和RocksDB，类似的存储引擎还用于Cassandra和HBase中，它的主要特征包括：1）数据顺序写入，不支持更新（更新及删除通过压缩合并数据段来实现）；2）数据写入操作内存表，数据异步写入磁盘；3）数据以SSTable段的形式写入磁盘，按照key进行排序，定期对数据段进行压缩合并；4）在内存中建立索引，由于数据段已经排序，只需要记录段首的记录即可。其结构如下所示：
LSM-Tree存储引擎数据存储于SSTables中，一个SSTables表示一个数据段，存储的是key-value值，且按照key进行排序，这种格式也称为排序字符串表。SSTables有两种形式，在内存中，采用的数据结构主要是树状数据结构，如红黑树或AVL树，进行内存排序；内存中的SSTables大于某个阈值时，顺序写入到磁盘中的日志文件中。
LSM-Tree存储引擎的工作流程如下：
- 当写入时，将其添加到内存中的平衡树数据结构中（例如红黑树）。这个内存中的树有时也被称为内存表；
- 当内存表大于某个阈值（通常为几兆字节）时，将其作为SSTable文件写入到磁盘。由于树已经维护了按照key排序的key-value对，写磁盘可以比较高效。新的SSTable文件成为数据库的最新部分。当SSTable写磁盘的同时，写入可以继续添加到一个新的内存表实例；
- 为了处理读请求，首先尝试在内存表中查找key,然后是最新的磁盘段文件，接下来是次新的磁盘段文件，以此类推，直到找到目标；
- 后台进程周期性执行段合并及压缩过程，以合并多个段文件，并丢弃那些已经被覆盖或删除的值；
- 每个写入操作都会立即追加到一个WAL日志文件中，它记录了操作的内容，它的目的是在数据库崩溃之后恢复内存表，每当将内存表写入SSTable时，相应的日志可以被丢弃。
数据库运行一段时间之后，磁盘上会生成多个SSTable文件，一个key可以包含在多个SSTable文件中，即一个key可以有多个版本。后台进程使用合并排序算法周期性地合并数据段，如下图所示。并发读取多个输入段文件，比较每个文件的第一个key，把最小的key（根据排序文件）拷贝到输出文件，并重复这个过程，最后会产生一个新的按key排序的合并段文件。当多个段包含相同的key时，可以保留最新段的值，并丢弃旧段中的值。
在文件中查找特定的key时，不需要在内存中保存所有key的索引，因为段是排序的，只需要一个内存索引来记录段首的key，可以减少内存的占用，同时可以进行区间查询。由于读请求往往需要扫描请求范围内的多个key-value对，可以考虑将这些记录保存到一个磁盘块中并在写磁盘前将其压缩。然后内存索引的每个条目指向压缩块的开关。除了节省磁盘空间，压缩还减少了I/O带宽的占用。
查找数据库中某个不存在的key时，LSM-Tree算法可能很慢：在确定key不存在之前，必须先检查内存表，然后将段一直回溯访问到最旧的段文件（可能必须从磁盘多次读取），为了优化这种访问，存储引擎通常使用额外的布隆过滤器。
2. B-Tree
B-Tree是关系数据库中被广泛使用的索引结构，像SSTable一样，B-Tree留按照key排序的key-value对，这样可以实现高效的key-value查找和区间查询。从本质上来说，B-Tree具有非常不同的设计理念。
在LSM-Tree中，日志结构索引将数据库分解为可变大小的段，通常大小为几兆字节或更大，并且始终按顺序写入段。相比之下，B-Tree将数据库分解为固定大小的块或页，传统上大小为4
KB（有时更大），页是内部读/写的最小单元。这种设计更接近底层硬件，因为磁盘也是以固定大小的块排列。
每个页面都可以使用地址或位置进行标识，这样可以让一个页面引用另一个页面，类似指针，不过是指向磁盘地址，而不是内存，可以使用这些页面引用来构造一个树状页面，如下所示。
某一页被指定为B-Tree的根，每当查找索引中的一个key时，总是从这里开始。该页面包含若干个key和对子页的引用。每个孩子都负责一个连续范围内的key,相邻引用之间的key可以指示这些范围之间的边界。
假定正在查找key
251,需要沿着200300间的页引用，到达类似的页，它进一步将200300范围分解成子范围。最终到达一个包含单个key的页(叶子页)，该页包含每个内联key的值或包含找到值的页的引用。
B-Tree中每一个页所包含的子页引用数量称为分支因子，例如在上图中，分支因子为6，在实际中，分支因子取决于存储页面引用和范围过界所需的空间总量，通常为几百个。
在正常情况下，数据库表一般只包含一个主键索引，如上图中以user_id为主键的索引。在主键索引中根据叶子结点中存储记录的内容还是引用，可以分为聚集索引和非聚集索引，而二级索引引用主键，如下图所示，在user_name上建立一个二级索引，它引用的值是主键。
如果更新B-Tree中原有的值，首先搜索包含该key的叶子页，更改该页的值，并将页定回到磁盘（对该页的任何引用仍然有效）。如果要添加新key，则需要找到其范围包含新key的页，并将其添加到该页，如果页中没有足够的可用空间来容纳新key，则将其分裂为两个半满的页，并且父页也需要更新以包含分裂之后的新key范围，如下图所示：
该算法确保树保持平衡：具有n个key的B-Tree总是具有O(log
n)的深度，大多数数据库可以适合3~4层的B-Tree，因此不需要遍历非常深的页面层次即可找到所需的页（分支因子为500的4
KB页的四级树可以存储高达256 TB）。
为了使数据库能从崩溃中恢复，常见的B-Tree的实现需要支持磁盘上的额外的数据结构：预写日志（Write-ahead log,WAL），也称为重做日志。这是一个仅支持追加修改的文件，每一个B-Tree的修改必须先更新WAL然后再修改树本身的页。当数据库在崩溃后需要恢复时，该日志用于将B-Tree恢复到最近一致的状态。
3. 对比B-Tree和LSM-Tree
根据经验，LSM-Tree通常对于写入更快，而B-Tree被认为对于读取更快。读取通常在LSM-Tree上较慢，主要是因为它们必须在不同的压缩阶段检查多个不同的数据结构和SSTable。
3.1 磁盘写入
B-Tree索引必须至少写两次数据：一个写入预写日志，一次写入树的页本身（还可能发生页分裂）。即使该页中只有几个字节更改，也必须承受整个页的开销。另外，B-Tree存储引擎使用与磁盘类似的分页结构，存在磁盘的碎片化。 LSM-Tree数据通常是写入内存表，内存表达到一定阈值的时候再统一写入磁盘，对于磁盘上的SStable段文件由后台线程进行合并压缩，效率更高，同时也会减少磁盘碎片。相对B-Tree来说，具有更高的写入吞吐量。
3.2 事务支持
B-Tree的优点则是每个键都恰好唯一对应于索引中的某个位置，而日志结构的存储引擎可能在不同的段中具有相同键的多个副本。如果数据库希望提供强大的事务语义，B-Tree显得更具吸引力：在许多关系数据库，事务隔离是通过键范围上的锁来实现的，并且在B-Tree索引中，这些锁可以直接定义到树中。
参考：