第三章：存储与检索
[TOC]
一个数据库在最基础的层次上需要完成两件事情：当你把数据交给数据库时，它应当把数据存储起来；而后当你向数据库要数据时，它应当把数据返回给你。
在 第二章 中，我们讨论了数据模型和查询语言，即程序员将数据录入数据库的格式，以及再次要回数据的机制。在本章中我们会从数据库的视角来讨论同样的问题：数据库如何存储我们提供的数据，以及如何在我们需要时重新找到数据。
作为程序员，为什么要关心数据库内部存储与检索的机理？你可能不会去从头开始实现自己的存储引擎，但是你 确实 需要从许多可用的存储引擎中选择一个合适的。而且为了让存储引擎能在你的工作负载类型上运行良好，你也需要大致了解存储引擎在底层究竟做了什么。
特别需要注意，针对 事务性 负载优化的和针对 分析性 负载优化的存储引擎之间存在巨大差异。稍后我们将在 “事务处理还是分析？” 一节中探讨这一区别，并在 “列式存储” 中讨论一系列针对分析性负载而优化的存储引擎。
但首先，我们将从你可能已经很熟悉的两大类数据库（传统的关系型数据库和很多所谓的 “NoSQL” 数据库）中使用的 存储引擎 来开始本章的内容。我们将研究两大类存储引擎：日志结构（log-structured） 的存储引擎，以及 面向页面（page-oriented） 的存储引擎（例如 B 树）。
驱动数据库的数据结构
世界上最简单的数据库可以用两个 Bash 函数实现：
#!/bin/bash
db_set () {
echo "$1,$2" >> database
}
db_get () {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}这两个函数实现了键值存储的功能。执行 db_set key value 会将 键（key） 和 值（value） 存储在数据库中。键和值（几乎）可以是你喜欢的任何东西，例如，值可以是 JSON 文档。然后调用 db_get key 会查找与该键关联的最新值并将其返回。
麻雀虽小，五脏俱全：
$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}'
$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}底层的存储格式非常简单：一个文本文件，每行包含一条逗号分隔的键值对（忽略转义问题的话，大致与 CSV 文件类似）。每次对 db_set 的调用都会向文件末尾追加记录，所以更新键的时候旧版本的值不会被覆盖 —— 因而查找最新值的时候，需要找到文件中键最后一次出现的位置（因此 db_get 中使用了 tail -n 1 )。
$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Exploratorium"]}
$ cat database
123456,{"name":"London","attractions":["Big Ben","London Eye"]}
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}db_set 函数对于极其简单的场景其实有非常好的性能，因为在文件尾部追加写入通常是非常高效的。与 db_set 做的事情类似，许多数据库在内部使用了 日志（log），也就是一个 仅追加（append-only） 的数据文件。真正的数据库有更多的问题需要处理（如并发控制，回收硬盘空间以避免日志无限增长，处理错误与部分写入的记录），但基本原理是一样的。日志极其有用，我们还将在本书的其它部分重复见到它好几次。
日志（log） 这个词通常指应用日志：即应用程序输出的描述正在发生的事情的文本。本书在更普遍的意义下使用 日志 这一词：一个仅追加的记录序列。它可能压根就不是给人类看的，它可以使用二进制格式，并仅能由其他程序读取。
另一方面，如果这个数据库中有着大量记录，则这个 db_get 函数的性能会非常糟糕。每次你想查找一个键时，db_get 必须从头到尾扫描整个数据库文件来查找键的出现。用算法的语言来说，查找的开销是 O(n) ：如果数据库记录数量 n 翻了一倍，查找时间也要翻一倍。这就不好了。
为了高效查找数据库中特定键的值，我们需要一个数据结构：索引（index）。本章将介绍一系列的索引结构，并在它们之间进行比较。索引背后的大致思想是通过保存一些额外的元数据作为路标来帮助你找到想要的数据。如果你想以几种不同的方式搜索同一份数据，那么你也许需要在数据的不同部分上建立多个索引。
索引是从主数据衍生的 额外的（additional） 结构。许多数据库允许添加与删除索引，这不会影响数据的内容，而只会影响查询的性能。维护额外的结构会产生开销，特别是在写入时。写入性能很难超过简单地追加写入文件，因为追加写入是最简单的写入操作。任何类型的索引通常都会减慢写入速度，因为每次写入数据时都需要更新索引。
这是存储系统中一个重要的权衡：精心选择的索引加快了读查询的速度，但是每个索引都会拖慢写入速度。因为这个原因，数据库默认并不会索引所有的内容，而需要你，也就是程序员或数据库管理员（DBA），基于对应用的典型查询模式的了解来手动选择索引。你可以选择那些能为应用带来最大收益而且又不会引入超出必要开销的索引。
散列索引
让我们从 键值数据（key-value Data） 的索引开始。这不是你可以索引的唯一数据类型，但键值数据是很常见的。在引入更复杂的索引之前，它是重要的第一步。
键值存储与在大多数编程语言中可以找到的 字典（dictionary） 类型非常相似，通常字典都是用 散列映射（hash map） 或 散列表（hash table） 实现的。散列映射在许多算法教科书中都有描述【1,2】，所以这里我们不会讨论它的工作细节。既然我们已经可以用散列映射来表示 内存中 的数据结构，为什么不使用它来索引 硬盘上 的数据呢？
假设我们的数据存储只是一个追加写入的文件，就像前面的例子一样，那么最简单的索引策略就是：保留一个内存中的散列映射，其中每个键都映射到数据文件中的一个字节偏移量，指明了可以找到对应值的位置，如 [图 3-1] 所示。当你将新的键值对追加写入文件中时，还要更新散列映射，以反映刚刚写入的数据的偏移量（这同时适用于插入新键与更新现有键）。当你想查找一个值时，使用散列映射来查找数据文件中的偏移量，寻找（seek） 该位置并读取该值即可。
![以类 CSV 格式存储键值对的日志，并使用内存散列映射进行索引。]
图 3-1 以类 CSV 格式存储键值对的日志，并使用内存散列映射进行索引。
听上去简单，但这是一个可行的方法。现实中，Bitcask 实际上就是这么做的（Riak 中默认的存储引擎）【3】。Bitcask 提供高性能的读取和写入操作，但要求所有的键必须能放入可用内存中，因为散列映射完全保留在内存中。而数据值可以使用比可用内存更多的空间，因为可以在硬盘上通过一次硬盘查找操作来加载所需部分，如果数据文件的那部分已经在文件系统缓存中，则读取根本不需要任何硬盘 I/O。
像 Bitcask 这样的存储引擎非常适合每个键的值经常更新的情况。例如，键可能是某个猫咪视频的网址（URL），而值可能是该视频被播放的次数（每次有人点击播放按钮时递增）。在这种类型的工作负载中，有很多写操作，但是没有太多不同的键 —— 每个键有很多的写操作，但是将所有键保存在内存中是可行的。
到目前为止，我们只是在追加写入一个文件 —— 所以如何避免最终用完硬盘空间？一种好的解决方案是，将日志分为特定大小的 段（segment），当日志增长到特定尺寸时关闭当前段文件，并开始写入一个新的段文件。然后，我们就可以对这些段进行 压缩（compaction），如 [图 3-2] 所示。这里的压缩意味着在日志中丢弃重复的键，只保留每个键的最近更新。
![键值更新日志（统计猫咪视频的播放次数）的压缩，只保留每个键的最近值]
图 3-2 键值更新日志（统计猫咪视频的播放次数）的压缩，只保留每个键的最近值
而且，由于压缩经常会使得段变得很小（假设在一个段内键被平均重写了好几次），我们也可以在执行压缩的同时将多个段合并在一起，如 [图 3-3] 所示。段被写入后永远不会被修改，所以合并的段被写入一个新的文件。冻结段的合并和压缩可以在后台线程中完成，这个过程进行的同时，我们仍然可以继续使用旧的段文件来正常提供读写请求。合并过程完成后，我们将读取请求转换为使用新合并的段而不是旧的段 —— 然后旧的段文件就可以简单地删除掉了。
![同时执行压缩和分段合并]
图 3-3 同时执行压缩和分段合并
每个段现在都有自己的内存散列表，将键映射到文件偏移量。为了找到一个键的值，我们首先检查最近的段的散列映射；如果键不存在，我们就检查第二个最近的段，依此类推。合并过程将保持段的数量足够小，所以查找过程不需要检查太多的散列映射。
要让这个简单的想法在实际中能工作会涉及到大量的细节。简单来说，下面几点都是实现过程中需要认真考虑的问题：
文件格式
CSV 不是日志的最佳格式。使用二进制格式更快，更简单：首先以字节为单位对字符串的长度进行编码，然后是原始的字符串（不需要转义）。
删除记录
如果要删除一个键及其关联的值，则必须在数据文件中追加一个特殊的删除记录（逻辑删除，有时被称为墓碑，即 tombstone）。当日志段被合并时，合并过程会通过这个墓碑知道要将被删除键的所有历史值都丢弃掉。
崩溃恢复
如果数据库重新启动，则内存散列映射将丢失。原则上，你可以通过从头到尾读取整个段文件并记录下来每个键的最近值来恢复每个段的散列映射。但是，如果段文件很大，可能需要很长时间，这会使服务的重启比较痛苦。Bitcask 通过将每个段的散列映射的快照存储在硬盘上来加速恢复，可以使散列映射更快地加载到内存中。
部分写入记录
数据库随时可能崩溃，包括在将记录追加到日志的过程中。Bitcask 文件包含校验和，允许检测和忽略日志中的这些损坏部分。
并发控制
由于写操作是以严格的顺序追加到日志中的，所以常见的实现是只有一个写入线程。也因为数据文件段是仅追加的或者说是不可变的，所以它们可以被多个线程同时读取。
乍一看，仅追加日志似乎很浪费：为什么不直接在文件里更新，用新值覆盖旧值？仅追加的设计之所以是个好的设计，有如下几个原因：
- 追加和分段合并都是顺序写入操作，通常比随机写入快得多，尤其是在磁性机械硬盘上。在某种程度上，顺序写入在基于闪存的 固态硬盘（SSD） 上也是好的选择【4】。我们将在“比较 B 树和 LSM 树”中进一步讨论这个问题。
- 如果段文件是仅追加的或不可变的，并发和崩溃恢复就简单多了。例如，当一个数据值被更新的时候发生崩溃，你不用担心文件里将会同时包含旧值和新值各自的一部分。
- 合并旧段的处理也可以避免数据文件随着时间的推移而碎片化的问题。
但是，散列表索引也有其局限性：
- 散列表必须能放进内存。如果你有非常多的键，那真是倒霉。原则上可以在硬盘上维护一个散列映射，不幸的是硬盘散列映射很难表现优秀。它需要大量的随机访问 I/O，而后者耗尽时想要再扩充是很昂贵的，并且需要很烦琐的逻辑去解决散列冲突【5】。
- 范围查询效率不高。例如，你无法轻松扫描 kitty00000 和 kitty99999 之间的所有键 —— 你必须在散列映射中单独查找每个键。
在下一节中，我们将看到一个没有这些限制的索引结构。
SSTables和LSM树
在 [图 3-3]中，每个日志结构存储段都是一系列键值对。这些键值对按照它们写入的顺序排列，日志中稍后的值优先于日志中较早的相同键的值。除此之外，文件中键值对的顺序并不重要。
现在我们可以对段文件的格式做一个简单的改变：要求键值对的序列按键排序。乍一看，这个要求似乎打破了我们使用顺序写入的能力，我们将稍后再回到这个问题。
我们把这个格式称为 排序字符串表（Sorted String Table），简称 SSTable。我们还要求每个键只在每个合并的段文件中出现一次（压缩过程已经保证）。与使用散列索引的日志段相比，SSTable 有几个大的优势：
即使文件大于可用内存，合并段的操作仍然是简单而高效的。这种方法就像归并排序算法中使用的方法一样，如 [图 3-4] 所示：你开始并排读取多个输入文件，查看每个文件中的第一个键，复制最低的键（根据排序顺序）到输出文件，不断重复此步骤，将产生一个新的合并段文件，而且它也是也按键排序的。
![合并几个 SSTable 段，只保留每个键的最新值]
图 3-4 合并几个 SSTable 段，只保留每个键的最新值
如果在几个输入段中出现相同的键，该怎么办？请记住，每个段都包含在一段时间内写入数据库的所有值。这意味着一个输入段中的所有值一定比另一个段中的所有值都更近（假设我们总是合并相邻的段）。当多个段包含相同的键时，我们可以保留最近段的值，并丢弃旧段中的值。
为了在文件中找到一个特定的键，你不再需要在内存中保存所有键的索引。以 [图 3-5] 为例：假设你正在内存中寻找键
handiwork，但是你不知道这个键在段文件中的确切偏移量。然而，你知道handbag和handsome的偏移，而且由于排序特性，你知道handiwork必须出现在这两者之间。这意味着你可以跳到handbag的偏移位置并从那里扫描，直到你找到handiwork（或没找到，如果该文件中没有该键）。![具有内存索引的 SSTable]
图 3-5 具有内存索引的 SSTable
你仍然需要一个内存中的索引来告诉你一些键的偏移量，但它可以是稀疏的：每几千字节的段文件有一个键就足够了，因为几千字节可以很快地被扫描完 ^i。
- 由于读取请求无论如何都需要扫描所请求范围内的多个键值对，因此可以将这些记录分组为块（block），并在将其写入硬盘之前对其进行压缩（如 [图 3-5]中的阴影区域所示）[^ 译注 i] 。稀疏内存索引中的每个条目都指向压缩块的开始处。除了节省硬盘空间之外，压缩还可以减少对 I/O 带宽的使用。
[^译注i]: 这里的压缩是 compression，不是前文的 compaction，请注意区分。
构建和维护SSTables
到目前为止还不错，但是如何让你的数据能够预先排好序呢？毕竟我们接收到的写入请求可能以任何顺序发生。
虽然在硬盘上维护有序结构也是可能的（请参阅 “B 树”），但在内存保存则要容易得多。有许多可以使用的众所周知的树形数据结构，例如红黑树或 AVL 树【2】。使用这些数据结构，你可以按任何顺序插入键，并按排序顺序读取它们。
现在我们可以让我们的存储引擎以如下方式工作：
- 有新写入时，将其添加到内存中的平衡树数据结构（例如红黑树）。这个内存树有时被称为 内存表（memtable）。
- 当 内存表 大于某个阈值（通常为几兆字节）时，将其作为 SSTable 文件写入硬盘。这可以高效地完成，因为树已经维护了按键排序的键值对。新的 SSTable 文件将成为数据库中最新的段。当该 SSTable 被写入硬盘时，新的写入可以在一个新的内存表实例上继续进行。
- 收到读取请求时，首先尝试在内存表中找到对应的键，如果没有就在最近的硬盘段中寻找，如果还没有就在下一个较旧的段中继续寻找，以此类推。
- 时不时地，在后台运行一个合并和压缩过程，以合并段文件并将已覆盖或已删除的值丢弃掉。
这个方案效果很好。它只会遇到一个问题：如果数据库崩溃，则最近的写入（在内存表中，但尚未写入硬盘）将丢失。为了避免这个问题，我们可以在硬盘上保存一个单独的日志，每个写入都会立即被追加到这个日志上，就像在前面的章节中所描述的那样。这个日志没有按排序顺序，但这并不重要，因为它的唯一目的是在崩溃后恢复内存表。每当内存表写出到 SSTable 时，相应的日志都可以被丢弃。
用SSTables制作LSM树
这里描述的算法本质上是 LevelDB【6】和 RocksDB【7】这些键值存储引擎库所使用的技术，这些存储引擎被设计嵌入到其他应用程序中。除此之外，LevelDB 可以在 Riak 中用作 Bitcask 的替代品。在 Cassandra 和 HBase 中也使用了类似的存储引擎【8】，而且他们都受到了 Google 的 Bigtable 论文【9】（引入了术语 SSTable 和 memtable ）的启发。
这种索引结构最早由 Patrick O'Neil 等人发明，且被命名为日志结构合并树（或 LSM 树）【10】，它是基于更早之前的日志结构文件系统【11】来构建的。基于这种合并和压缩排序文件原理的存储引擎通常被称为 LSM 存储引擎。
Lucene，是一种全文搜索的索引引擎，在 Elasticsearch 和 Solr 被使用，它使用类似的方法来存储它的关键词词典【12,13】。全文索引比键值索引复杂得多，但是基于类似的想法：在搜索查询中，由一个给定的单词，找到提及单词的所有文档（网页、产品描述等）。这也是通过键值结构实现的：其中键是 单词（term），值是所有包含该单词的文档的 ID 列表（postings list）。在 Lucene 中，从词语到记录列表的这种映射保存在类似于 SSTable 的有序文件中，并根据需要在后台执行合并【14】。
性能优化
与往常一样，要让存储引擎在实践中表现良好涉及到大量设计细节。例如，当查找数据库中不存在的键时，LSM 树算法可能会很慢：你必须先检查内存表，然后查看从最近的到最旧的所有的段（可能还必须从硬盘读取每一个段文件），然后才能确定这个键不存在。为了优化这种访问，存储引擎通常使用额外的布隆过滤器（Bloom filters）【15】。（布隆过滤器是一种节省内存的数据结构，用于近似表达集合的内容，它可以告诉你数据库中是否存在某个键，从而为不存在的键节省掉许多不必要的硬盘读取操作。）
还有一些不同的策略来确定 SSTables 被压缩和合并的顺序和时间。最常见的选择是 size-tiered 和 leveled compaction。LevelDB 和 RocksDB 使用 leveled compaction（LevelDB 因此得名），HBase 使用 size-tiered，Cassandra 同时支持这两种【16】。对于 sized-tiered，较新和较小的 SSTables 相继被合并到较旧的和较大的 SSTable 中。对于 leveled compaction，key （按照分布范围）被拆分到较小的 SSTables，而较旧的数据被移动到单独的层级（level），这使得压缩（compaction）能够更加增量地进行，并且使用较少的硬盘空间。
即使有许多微妙的东西，LSM 树的基本思想 —— 保存一系列在后台合并的 SSTables —— 简单而有效。即使数据集比可用内存大得多，它仍能继续正常工作。由于数据按排序顺序存储，你可以高效地执行范围查询（扫描所有从某个最小值到某个最大值之间的所有键），并且因为硬盘写入是连续的，所以 LSM 树可以支持非常高的写入吞吐量。
B树
前面讨论的日志结构索引看起来已经相当可用了，但它们却不是最常见的索引类型。使用最广泛的索引结构和日志结构索引相当不同，它就是我们接下来要讨论的 B 树。
从 1970 年被引入【17】，仅不到 10 年后就变得 “无处不在”【18】，B 树很好地经受了时间的考验。在几乎所有的关系数据库中，它们仍然是标准的索引实现，许多非关系数据库也会使用到 B 树。
像 SSTables 一样，B 树保持按键排序的键值对，这允许高效的键值查找和范围查询。但这也就是仅有的相似之处了：B 树有着非常不同的设计理念。
我们前面看到的日志结构索引将数据库分解为可变大小的段，通常是几兆字节或更大的大小，并且总是按顺序写入段。相比之下，B 树将数据库分解成固定大小的 块（block） 或 分页（page），传统上大小为 4KB（有时会更大），并且一次只能读取或写入一个页面。这种设计更接近于底层硬件，因为硬盘空间也是按固定大小的块来组织的。
每个页面都可以使用地址或位置来标识，这允许一个页面引用另一个页面 —— 类似于指针，但在硬盘而不是在内存中。我们可以使用这些页面引用来构建一个页面树， 所示。
![使用 B 树索引查找一个键] 图 3-6 使用 B 树索引查找一个键
一个页面会被指定为 B 树的根；在索引中查找一个键时，就从这里开始。该页面包含几个键和对子页面的引用。每个子页面负责一段连续范围的键，根页面上每两个引用之间的键，表示相邻子页面管理的键的范围（边界）。
在 [图 3-6] 的例子中，我们正在寻找键 251 ，所以我们知道我们需要跟踪边界 200 和 300 之间的页面引用。这将我们带到一个类似的页面，进一步将 200 到 300 的范围拆分到子范围。
最终，我们将到达某个包含单个键的页面（叶子页面，leaf page），该页面或者直接包含每个键的值，或者包含了对可以找到值的页面的引用。
在 B 树的一个页面中对子页面的引用的数量称为 分支因子（branching factor）。例如，在 [图 3-6] 中，分支因子是 6。在实践中，分支因子的大小取决于存储页面引用和范围边界所需的空间，但这个值通常是几百。
如果要更新 B 树中现有键的值，需要搜索包含该键的叶子页面，更改该页面中的值，并将该页面写回到硬盘（对该页面的任何引用都将保持有效）。如果你想添加一个新的键，你需要找到其范围能包含新键的页面，并将其添加到该页面。如果页面中没有足够的可用空间容纳新键，则将其分成两个半满页面，并更新父页面以反映新的键范围分区，如 所示 [^ii]。
![通过分割页面来生长 B 树] 图 3-7 通过分割页面来生长 B 树
[^ii]: 向 B 树中插入一个新的键是相当符合直觉的，但删除一个键（同时保持树平衡）就会牵扯很多其他东西了【2】。
这个算法可以确保树保持平衡：具有 n 个键的 B 树总是具有 $O (log n)$ 的深度。大多数数据库可以放入一个三到四层的 B 树，所以你不需要追踪多个页面引用来找到你正在查找的页面（分支因子为 500 的 4KB 页面的四层树可以存储多达 256TB 的数据）。
让B树更可靠
B 树的基本底层写操作是用新数据覆写硬盘上的页面，并假定覆写不改变页面的位置：即，当页面被覆写时，对该页面的所有引用保持完整。这与日志结构索引（如 LSM 树）形成鲜明对比，后者只追加到文件（并最终删除过时的文件），但从不修改文件中已有的内容。
你可以把覆写硬盘上的页面对应为实际的硬件操作。在磁性硬盘驱动器上，这意味着将磁头移动到正确的位置，等待旋转盘上的正确位置出现，然后用新的数据覆写适当的扇区。在固态硬盘上，由于 SSD 必须一次擦除和重写相当大的存储芯片块，所以会发生更复杂的事情【19】。
而且，一些操作需要覆写几个不同的页面。例如，如果因为插入导致页面过满而拆分页面，则需要写入新拆分的两个页面，并覆写其父页面以更新对两个子页面的引用。这是一个危险的操作，因为如果数据库在系列操作进行到一半时崩溃，那么最终将导致一个损坏的索引（例如，可能有一个孤儿页面没有被任何页面引用） 。
为了使数据库能处理异常崩溃的场景，B 树实现通常会带有一个额外的硬盘数据结构：预写式日志（WAL，即 write-ahead log，也称为 重做日志，即 redo log）。这是一个仅追加的文件，每个 B 树的修改在其能被应用到树本身的页面之前都必须先写入到该文件。当数据库在崩溃后恢复时，这个日志将被用来使 B 树恢复到一致的状态【5,20】。
另外还有一个更新页面的复杂情况是，如果多个线程要同时访问 B 树，则需要仔细的并发控制 —— 否则线程可能会看到树处于不一致的状态。这通常是通过使用 锁存器（latches，轻量级锁）保护树的数据结构来完成。日志结构化的方法在这方面更简单，因为它们在后台进行所有的合并，而不会干扰新接收到的查询，并且能够时不时地将段文件切换为新的（该切换是原子操作）。
B树的优化
由于 B 树已经存在了很久，所以并不奇怪这么多年下来有很多优化的设计被开发出来，仅举几例：
- 不同于覆写页面并维护 WAL 以支持崩溃恢复，一些数据库（如 LMDB）使用写时复制方案【21】。经过修改的页面被写入到不同的位置，并且还在树中创建了父页面的新版本，以指向新的位置。这种方法对于并发控制也很有用，我们将在 “快照隔离和可重复读” 中看到。
- 我们可以通过不存储整个键，而是缩短其大小，来节省页面空间。特别是在树内部的页面上，键只需要提供足够的信息来充当键范围之间的边界。在页面中包含更多的键允许树具有更高的分支因子，因此也就允许更少的层级 [^iii]。
- 通常，页面可以放置在硬盘上的任何位置；没有什么要求相邻键范围的页面也放在硬盘上相邻的区域。如果某个查询需要按照排序顺序扫描大部分的键范围，那么这种按页面存储的布局可能会效率低下，因为每个页面的读取都需要执行一次硬盘查找。因此，许多 B 树的实现在布局树时会尽量使叶子页面按顺序出现在硬盘上。但是，随着树的增长，要维持这个顺序是很困难的。相比之下，由于 LSM 树在合并过程中一次性重写一大段存储，所以它们更容易使顺序键在硬盘上连续存储。
- 额外的指针被添加到树中。例如，每个叶子页面可以引用其左边和右边的兄弟页面，使得不用跳回父页面就能按顺序对键进行扫描。
- B 树的变体如 分形树（fractal trees）【22】借用了一些日志结构的思想来减少硬盘查找（而且它们与分形无关）。
[^iii]: 这个变种有时被称为 B+ 树，但因为这个优化已被广泛使用，所以经常无法区分于其它的 B 树变种。
比较B树和LSM树
尽管 B 树实现通常比 LSM 树实现更成熟，LSM 树由于其性能特征的关系，仍然引起了不少关注。根据经验，通常 LSM 树的写入速度更快，而 B 树的读取速度更快【23】。LSM 树上的读取通常比较慢，因为它们必须检查几种不同的数据结构和不同压缩（Compaction）层级的 SSTables。
然而，基准测试的结果通常和工作负载的细节相关。你需要用你特有的工作负载来测试系统，以便进行有效的比较。在本节中，我们将简要讨论一些在衡量存储引擎性能时值得考虑的事情。
LSM树的优点
B 树索引中的每块数据都必须至少写入两次：一次写入预先写入日志（WAL），一次写入树页面本身（如果有分页还需要再写入一次）。即使在该页面中只有几个字节发生了变化，也需要接受写入整个页面的开销。有些存储引擎甚至会覆写同一个页面两次，以免在电源故障的情况下页面未完整更新【24,25】。
由于反复压缩和合并 SSTables，日志结构索引也会多次重写数据。这种影响 —— 在数据库的生命周期中每笔数据导致对硬盘的多次写入 —— 被称为 写入放大（write amplification）。使用固态硬盘的机器需要额外关注这点，固态硬盘的闪存寿命在覆写有限次数后就会耗尽。
在写入繁重的应用程序中，性能瓶颈可能是数据库可以写入硬盘的速度。在这种情况下，写放大会导致直接的性能代价：存储引擎写入硬盘的次数越多，可用硬盘带宽内它能处理的每秒写入次数就越少。
进而，LSM 树通常能够比 B 树支持更高的写入吞吐量，部分原因是它们有时具有较低的写放大（尽管这取决于存储引擎的配置和工作负载），部分是因为它们顺序地写入紧凑的 SSTable 文件而不是必须覆写树中的几个页面【26】。这种差异在机械硬盘上尤其重要，其顺序写入比随机写入要快得多。
LSM 树可以被压缩得更好，因此通常能比 B 树在硬盘上产生更小的文件。B 树存储引擎会由于碎片化（fragmentation）而留下一些未使用的硬盘空间：当页面被拆分或某行不能放入现有页面时，页面中的某些空间仍未被使用。由于 LSM 树不是面向页面的，并且会通过定期重写 SSTables 以去除碎片，所以它们具有较低的存储开销，特别是当使用分层压缩（leveled compaction）时【27】。
在许多固态硬盘上，固件内部使用了日志结构化算法，以将随机写入转变为顺序写入底层存储芯片，因此存储引擎写入模式的影响不太明显【19】。但是，较低的写入放大率和减少的碎片仍然对固态硬盘更有利：更紧凑地表示数据允许在可用的 I/O 带宽内处理更多的读取和写入请求。
LSM树的缺点
日志结构存储的缺点是压缩过程有时会干扰正在进行的读写操作。尽管存储引擎尝试增量地执行压缩以尽量不影响并发访问，