一个最简单的数据库可以实现为 Key-Value 追加写入到文件，每次读取时从头到尾扫描文件。当文件很大时，读取的效率就很低了，为了高效地查找数据库中特定键的值，需要新的数据结构：==索引==。这里涉及存储系统中重要的权衡设计：==适当的索引可以加速读取查询，但每个索引都会减慢写速度。==
假设数据存储全部采用==追加式文件==组成，如之前的例子所示。那么最简单的索引策略就是：保存内存中的 hash map，把每个 Key 一一映射到数据文件中特定的字节偏移量，这样就可以找到每个值的位置。每当在文件中追加新的 Key-Value 对时，还要更新 hash map 来反映刚刚写入数据的偏移量（包括插入新的 Key 和更新已有的 Key）。当查找某个值时，使用 hash map 来找到文件中的偏移量，即存储位置，然后读取其内容。
如上所述，只追加到一个文件，那么如何避免最终用尽磁盘空间？一个好的解决方案是将日志分解成一定大小的段，当文件达到一定大小时就关闭它，并将后续写入到新的段文件中。然后可以在这些段上执行压缩，如图 3-2 所示。==压缩意味着在日志中丢弃重复的 Key，并且只保留每个 Key 最近的更新==。
此外，由于压缩往往使得段更小（假设 Key 在段内被覆盖多次），==也可以在执行压缩的同时将多个段合并在一起==。
简而言之，在真正地实现中有以下重要问题：
- 文件格式：二进制
- 删除记录：==如果要删除 Key 和它关联的 Value，则必须在数据文件中追加一个特殊的删除记录（有时候称为墓碑，tombstone）。当合并日志段时，一旦发现墓碑标记，则会丢弃这个已删除 Key 的所有值==。
- 崩溃恢复：如果数据库重新启动，则内存中的 hash map 将丢失。原则上，可以通过从头到尾读取整个段文件，然后记录每个 Key 的最新值的偏移量，来恢复每个段的 hash map。但是，如果分段文件很大，可能扫描需要很长时间，这将使服务器重启变得缓慢。Bitcask 通过将每个段的 hash map 的快照存储在磁盘上，可以更快地加载到内存中，以此加快恢复速度。
- 部分写入的记录：数据库随时可能崩溃，包括将记录追加到日志的过程中。Bitcask 文件包括校验值，这样可以发现损坏部分并丢弃。
- 并发控制：由于写入以严格的先后顺序追加到日志中，通常的实现选择是==只有一个写线程==。数据文件段是追加的，并且是不可变的，所以他们可以被==多个线程同时读取==。
为什么不原地更新文件，用新值覆盖旧值？
- 追加和分段合并主要是==顺序写==，它通常比随机写入快得多。
- 如果段文件是追加的或不可变的，则并发和==崩溃恢复要简单==得多。 例如，不必担心在重写值时发生崩溃的清况，留下一个包含部分旧值和部分新值混杂在一起的文件。
- 合并旧段可以避免随着时间的推移数据文件出现==碎片化==的问题。
但是，哈希表索引也有其局限性：
- 哈希表==必须全部放入内存==，所以如果有大量的 Key，就没那么幸运了。原则上，可以在磁盘上维护 hash map，但不幸的是，很难使磁盘上的 hash map 表现良好。它需要大量的随机访问 I/0，当哈希变满时，继续增长代价昂贵，并且哈希冲突时需要复杂的处理逻辑 。
- ==区间查询效率不高==。 例如，不能简单地支持扫描 kittyooooo 和 kitty99999 区间内的所有 Key，只能采用逐个查找的方式查询每一个 Key。
现在简单地改变段文件的格式：要求 Key-Value 对的顺序按键排序。这种格式称为排序字符串表，或简称为 SSTable。它要求每个键在每个合并的段文件中只能出现一次（压缩过程已经确保了）。SSTable 相比哈希索引的日志段，具有以下优点：
-
==合并段更加简单高效，即使文件大于可用内存，可以使用归并排序的方法==。如果相同的 Key 出现在多个输入段怎么办？请记住，每个段包含在某段时间内写入数据库的所有值。这意味着一个输入段中的所有值肯定比其他段中的所有值更新（假设总是合并相邻的段）。==当多个段包含相同的键时，可以保留最新段的值，并丢弃旧段中的值==。
-
在文件中查找特定的 Key 时，不再需要在内存中保存所有 Key 的索引。仍然需要一个内存索引来记录某些 Key 的偏移，但它==可以是稀疏的==，由于可以很快扫描几千字节，对于段文件中每几千字节，只需要一个 Key 就足够了。
-
由于读请求往往需要扫描请求范围内的多个 Key-Value 对，可以考虑将这些记录保存到一个块中并在写磁盘之前将其压缩（如图 3-5 中阴影区域所示）。然后稀疏内存索引的每个条目指向压缩块的开头。除了节省磁盘空间，压缩还减少了 I/O 带宽的占用。
考虑到写入可能以任意顺序出现，首先该如何让数据按键排序呢？在磁盘上维护排序结构是可行的，不过，将其保存在内存中更容易。内存排序有很多广为人知的树状数据结构，例如红黑树或 AVL 树。使用这些数据结构，可以按任意顺序插入键并以排序后的顺序读取它们。
存储引擎的基本工作流程如下：
- 当写入时，将其添加到内存中的平衡树数据结构中（例如红黑树），这个内存中的树有时被称为内存表。
- 当内存表大于某个阈值（通常为几兆字节）时，将其作为 SSTable 文件写入磁盘。由于树已经维护了按键排序的 Key-Value 对，写磁盘可以比较高效。新的 SSTable 文件成为数据库的最新部分。当 SSTable 写磁盘的同时，写入可以继续添加到一个新的内存表实例。
- 为了处理读请求，首先尝试在内存表中查找键，然后是最新的磁盘段文件，接下来是次新的磁盘段文件，以此类推，直到找到目标（或为空）。
- 后台进程周期性地执行段合并与压缩过程，以合并多个段文件，并丢弃那些已被覆盖或删除的值。
上述方案可以很好地工作，但它还存在一个问题：如果数据库崩溃，最近的写入（在内存表中但尚未写入磁盘）将会丢失。为了避免该问题，可以在磁盘上保留单独的日志，每个写入都会立即追加到该日志，就像上一节所述。==那个日志文件不需要按键排序，这并不重要，因为它的唯一目的是在崩溃后恢复内存表。每当将内存表写入 SSTable 时，相应的日志可以被丢弃。==
以上描述的算法本质上正是 LevelDB 和 RocksDB 所使用的，主要用于嵌入到其他应用程序的 Key-Value 存储引擎库。最初这个索引结构由 Patrick O'Neil 等人以日志结构的合并树（Log-Structured Merge Tree，或 LSM-Tree）命名，它建立在更早期的日志结构文件系统之上 。 因此，基于合并和压缩排序文件原理的存储引擎通常都被称为 LSM 存储引擎。
当查找数据库中某个不存在的键时，LSM-Tree 算法可能很慢：在确定键不存在之前，必须先检查内存表，然后将段一直回溯访问到最旧的段文件（可能必须从磁盘多次读取)。为了优化这种访问，存储引擎通常使用额外的==布隆过滤器==（Bloom filters）。
还有不同的策略会影响甚至决定 SSTables 压缩和合并时的具体顺序和时机。最常见的方式是==大小分级==（ size-tiered）和==分层==（leveled）压缩。
-
在大小分级的压缩中，较新的和较小的 SSTables 被连续合并到较旧和较大的 SSTables。
-
在分层压缩中，键的范围分裂成多个更小的 SSTables，旧数据被移动到单独的“层级”，这样压缩可以逐步进行并节省磁盘空间。
B-tree 将数据库分解成固定大小的块或页，传统上大小为 4 KB（有时更大），页是内部读/写的最小单元。这种设计更接近底层硬件，因为磁盘也是以固定大小的块排列。每个页面都可以使用地址或位置进行标识，这样可以让一个页面引用另一个页面，类似指针，不过是指向磁盘地址，而不是内存。可以使用这些页面引用来构造一个树状页面，如图 3-6 所示。
B-tree 底层的基本写操作是使用新数据覆盖磁盘上的旧页。它假设覆盖不会改变页的磁盘存储位置，也就是说，当页被覆盖时，对该页的所有引用保持不变。这与日志结构索引（如 LSM-tree）形成鲜明对比，LSM-Tree 仅追加更新文件（并最终删除过时的文件)，但不会修改文件。
某些操作需要覆盖多个不同的页。例如，如果插入导致页溢出，因而需分裂页，那么需要写两个分裂的页，并且覆盖其父页以更新对两个子页的引用。这是个比较危险的操作，因为如果数据库在完成部分页写入之后发生崩溃，最终会导致索引破坏（例如，可能有一个孤儿页，没有被任何其他页所指向）。
为了使数据库能从崩溃中恢复，常见 B-tree 的实现需要支持磁盘上的额外的数据结构：==预写日志==（write-ahead log, ==WAL==） ，也称为==重做日志==。这是一个仅支持追加修改的文件，每个 B-tree 的修改必须先更新 WAL 然后再修改树本身的页。当数据库在崩溃后需要恢复时，该日志用于将 B-tree 恢复到最近一致的状态。
原地更新页的另一个复杂因素是，如果多个线程要同时访问 B-tree，则需要注意并发控制，否则线程可能会看到树处于不一致的状态。通常使用锁存器（轻量级的锁）保护树的数据结构来完成。在这方面，日志结构化的方法显得更简单，因为它们在后台执行所有合并，而不会干扰前端的查询，并且会不时地用新段原子地替换旧段。
-
一些数据库（如 LMDB）不使用覆盖页和维护 WAL 来进行崩溃恢复，而是使用==写时复制==（copy-on-write）方案。
-
保存键的缩略信息，而不是完整的键，这样可以节省页空间。
-
一般来说，页可以放在磁盘上的任何位置；没有要求相邻的页需要放在磁盘的相邻位置。如果查询需要按照顺序扫描大段的键范围，考虑到每个读取的页都可能需要磁盘 I/0，所以逐页的布局可能是低效的。因此，许多 B-tree 的实现尝试对树进行布局，以便相邻叶子页可以按顺序保存在磁盘上。然而，随着树的增长，维持这个顺序会变得越来越困难。相比之下，由于 LSM-tree 在合并过程中一次重写大批存储段，因此它们更容易让连续的键在磁盘上相互靠近。
-
添加额外的指针到树中。例如，每个叶子页面可能会向左和向右引用其同级的兄弟页，这样可以顺序扫描键，而不用跳回到父页。
-
B-tree 的变体如分形树，借鉴了一些日志结构的想法来减少磁盘寻道。
B-tree 索引必须至少写两次数据：一次写入预写日志，一次写入树的页本身（还可能发生页分裂)。即使该页中只有几个字节更改，也必须承受写整个页的开销。一些存储引擎甚至覆盖相同的页两次，以避免在电源故障的情况下最终出现部分更新的页。（注：==InnoDB 写 page 时候使用 Double Write，即先写一个临时文件，再去修改原来的页，防止修改页的过程中发生异常，把原来的页写坏。由于 redo log 的恢复能力基于原 page 的数据，一旦原 page 数据出现错误，就无法使用 redo log 恢复了==。）
LSM-tree 通常能够承受比 B-tree ==更高的写入吞吐量==，部分是因为它们有时==具有较低的写放大==（尽管这取决于存储引擎的配置和工作负载），部分原因是它们以==顺序方式写入紧凑的 SSTable 文件==，而不必重写树中的多个页。
LSM-tree 可以支持==更好地压缩==，因此通常磁盘上的文件比 B-tree 小很多。由于碎片，B-tree 存储引擎使某些磁盘空间无法使用：当页被分裂或当一行的内容不能适合现有页时，页中的某些空间无法使用。由于 LSM- tree 不是面向页的，并且定期重写 SSTables 以消除碎片化，所以它们具有较低的存储开销，特别是在使用分层压缩时。
日志结构存储的缺点是==压缩过程有时会干扰正在进行的读写操作==。由于磁盘的并发资源有限，所以当磁盘执行昂贵的压缩操作时，很容易发生读写请求等待的情况。这对吞吐量和平均响应时间的影响通常很小，但是如果观察较高的百分位数，日志结构化存储引擎的查询响应时间有时会相当高，而 B-tree 的响应延迟则更具确定性。
==如果写入吞吐量很高并且压缩没有仔细配置，那么就会发生压缩无法匹配新数据写入速率的情况==。在这种情况下，磁盘上未合并段的数量不断增加，直到磁盘空间不足，由于它们需要检查更多的段文件，因此读取速度也会降低 。通常，即使压缩不能跟上，基于 SSTable 的存储引擎也不会限制到来的写入速率，因此需要额外的监控措施来及时发现这种情况。
B-tree 的优点则是每个 Key 都恰好唯一对应于索引中的某个位置，而日志结构的存储引擎可能在不同的段中具有相同 Key 的多个副本。==如果数据库希望提供强大的事务语义，这方面 B-tree 显得更具有吸引力==：在许多关系数据库中，事务隔离是通过 Key 范围上的锁来实现的，==并且在 B-tree 索引中，这些锁可以直接定义到树中==（注：InnoDB 中的 Next-Key Lock 就是基于 B-tree 的）。
索引中的键是查询搜索的对象，而值则可以是以下两类之一：它可能是上述的实际行（文档，顶点），也可以是对其他地方存储的行的引用。在后一种情况下，存储行的具体位置被称为==堆文件==（heap file），并且它不以特定的顺序存储数据（它可以是追加的，或者记录删掉的行以便用新数据在之后覆盖它们）。
在某些情况下，从索引到堆文件的额外跳转对于读取来说意味着太多的性能损失，因此可能希望将索引行直接存储在索引中。这被称为==聚集索引==（ clustered index）。例如，在 MySQL InnoDB 存储引擎中，表的主键始终是聚集索引，二级索引引用主键（而不是堆文件位置）。
聚集索引（在索引中直接保存行数据）和非聚集索引（仅存储索引中的数据的引用）之间有一种折中设计称为==覆盖索引==（ covering index）或包含列的索引（index with included columns），它在索引中保存一些表的列值。它可以支持只通过索引即可回答某些简单查询（在这种情况下，称索引覆盖了查询）。
与任何类型的数据冗余一样，聚集和覆盖索引可以加快读取速度，但是它们需要额外的存储，并且会增加写入的开销。此外，数据库还需要更多的工作来保证事务性，这样应用程序不会因为数据冗余而得到不一致的结果。
最常见的多列索引类型称为==级联索引==（concatenated index），它通过将一列追加到另一列，将几个字段简单地组合成一个键（索引的定义指定字段连接的顺序）。
==多维索引是更普遍的一次查询多列的方法，这对地理空间数据尤为重要==。例如，餐馆搜索网站可能有一个包含每个餐厅的纬度和经度的数据库。当用户在地图上查看餐馆时，网站需要搜索用户正在查看的矩形地图区域内的所有餐馆。这要求一个二维的范围查询，如下所示：
SELECT * FROM restaurants WHERE latitude > 51.4946 AND latitude < 51.5079
AND longitude > -0.1162 AND longitude < -0.1004;标准 B-tree 或 LSM-tree 索引无法高效地应对这种查询，它只能提供一个纬度范围内（但在任何经度）的所有餐馆，或者所有经度范围内的餐厅（在北极和南极之间的任何地方），但不能同时满足。
一种选择是使用空格填充曲线将二维位置转换为单个数字，然后使用常规的 B-tree 索引 。更常见的是使用专门的空间索引，如 ==R 树==。
与直觉相反，内存数据库的性能优势并不是因为它们不需要从磁盘读取。如果有足够的内存，即使是基于磁盘的存储引擎，也可能永远不需要从磁盘读取，因为操作系统将最近使用的磁盘块缓存在内存中。相反，==内存数据库可以更快，是因为它们避免使用写磁盘的格式对内存数据结构编码的开销==。
除了性能外，内存数据库的另一个有意思的地方是，它提供了基于磁盘索引难以实现的某些数据模型。例如，Redis 为各种数据结构（如优先级队列和集合）都提供了类似数据库的访问接口。由于所有的数据都保存在内存中，所以实现可以比较简单。
对比事务处理与分析系统的主要特性
| 属性 | 事务处理系统（OLTP） | 分析系统（OLAP） |
|---|---|---|
| 主要读特征 | 基于键，每次查询返回少量的记录 | 对大量记录进行汇总 |
| 主要写特征 | 随机访问，低延迟写入用户的输入 | 批量导入（ETL）或事件流 |
| 典型使用场景 | 终端用户，通过网络应用程序 | 内部分析师，为决策提供支持 |
| 数据表征 | 最新的数据状态（当前时间点） | 随着时间而变化的所有事件历史 |
| 数据规模 | GB 到 TB | TB 到 PB |
数据仓库则是单独的数据库，分析人员可以在不影响 OLTP 操作的情况下尽情地使用。数据仓库包含公司所有各种 OLTP 系统的只读副本。从 OLTP 数据库（使用周期性数据转储或连续更新流）中提取数据，转换为分析友好的模式，执行必要的清理，然后加载到数据仓库中。将数据导入数据仓库的过程称为 “提取-转换-加载”（Extract-Transform-Load, ETL）。
表面上，数据仓库和关系型 OLTP 数据库看起来相似，因为它们都具有 SQL 查询接口。然而，系统内部实则差异很大，它们针对迥然不同的查询模式进行了各自优化。许多数据库供应商现在专注于支持事务处理或分析工作负载，但不能同时支持两者。
根据不同的应用需求，事务处理领域广泛使用了多种不同数据模型。而另一方面，分析型业务的数据模型则要少得多。许多数据仓库都相当公式化的使用了星型模式，也称为维度建模。
图 3-9 所示的模式可用于零售数据仓库。模式的中心是一个所谓的==事实表==（ fact table）（在这个例子中，它被称为 fact sales) 。事实表的每一行表示在特定时间发生的事件（这里，每一行代表客户购买的一个产品)。如果我们正在分析网站流最而不是零售，则每一行可能表示页面视图或用户的单击。
通常，事实被捕获为单独的事件，这样之后的分析具有最大的灵活性。不过，这意味着事实表可能会变得非常庞大。
事实表中的列是属性，例如产品销售的价格和供应商处购买的成本（可以计算出利润率）。其他列可能会引用其他表的外键，称为==维度表==（dimension tables）。由于事实表中的每一行都代表一个事件，维度通常代表事件的对象（who） 、什么（what） 、地点（where） 、时间（when） 、方法（how）以及原因（why）。
该模板的一个变体称为雪花模式，其中维度进一步细分为子空间。
虽然事实表通常超过 100 列，但典型的数据仓库查询往往一次只访问其中的 4 或 5 个（"SELECT *" 查询很少用于分析）。
在大多数 OLTP 数据库中，存储以面向行的方式布局：来自表的一行的所有值彼此相邻存储。文档数据库也是类似，整个文档通常被存储为一个连续的字节序列。
面向行的存储引擎需要将所有行（每个由超过 100 个属性组成）从磁盘加载到内存中 、解析它们，并过滤出不符合所需条件的行。这可能需要很长时间。
面向列存储的想法很简单：不要将一行中的所有值存储在一起，而是将每列中的所有值存储在一起。如果每个列存储在一个单独的文件中，查询只需要读取和解析在该查询中使用的那些列，这可以节省大量的工作。该原理如图 3-10 所示。
面向列的存储布局依赖一组列文件，每个文件以相同顺序保存着数据行。因此，如果需要重新组装整行，可以从每个单独的列文件中获取第 23 个条目，并将它们放在一起构成表的第 23 行。
面向列的存储恰好非常适合压缩，看看图 3-10 中每列的值序列：它们看起来有很多重复，这是压缩的好兆头。取决于列中具体数据模式，可以采用不同的压缩技术。在数据仓库中特别有效的一种技术是==位图编码==（bitmap encoding），如图 3-11 所示。
通常，列中的不同值的数量小于行数（一个例子，零售商可能拥有数十亿个销售交易，但只有 100000 个不同的产品)。现在可以使用 n 个不同值的列，并将其转换为 n 个单独的位图：一个位图对应每个不同的值，一个位对应一行。如果行具有该值，该位为 1 ，否则为 0。
如果 n 非常小（例如，表示国家的列可能具有大约 200 个不同的值），那么这些位图由每行一位存储。但是, 如果 n 越大，在大多数位图中将会有很多零（它们很稀疏）。此时，位图也可以进行==游程编码==，如图 3-11 底部所示。这样列的编码非常紧凑。
这些位图索引非常适合在数据仓库中常见的查询。例如：
WHERE product_sk IN (30, 68, 69)：
加载 product_sk = 30 product_sk = 68 和 product_sk = 69 的三个位图，并计算三个位图的按位或，这可以非常高效地完成。
对于需要扫描数百万行的数据仓库查询，将数据从磁盘加载到内存的带宽是一大瓶颈。然而，这还不是唯一的瓶颈。分析数据库的开发人员还要关心如何高效地将内存的带宽用于 CPU 缓存，避免分支错误预测和 CPU 指令处理流水线停顿（bubbles），并利用现代 CPU 中的单指令多数据（SIMD）指令。
除了减少需要从磁盘加载的数据量之外，面向列的存储布局也有利于高效利用 CPU 周期。 例如，查询引擎可以将一大块压缩列数据放入 CPU 的 L1 缓存中，并以紧凑循环（即没有函数调用）进行迭代。对于每个被处理的记录，CPU 能够比基于很多函数调用和条件判断的代码更快地执行这种循环。列压缩使得列中更多的行可以加载到 L1 缓存。诸如先前描述的按位 AND 和 OR 的运算符，可被设计成直接对这样的列压缩数据块进行操作。这种技术被称为==矢量化处理==（vectorized processing ）。
在列存储中，行的存储顺序并不太重要。最简单的是按插入顺序保存，这样插入一个新行只是追加到每个列文件。但请注意，==单独排序每列是没有意义的==，如果这样的话就无法知道列中的某一项属于哪一行。因为知道某列中的第 k 项和另一列的第 k 项一定属于同一行，基于这种约定我们可以重建一行。
相反，即使数据是按列存储的，它也需要一次排序整行。数据库管理员可以基于常见查询的知识来选择要排序表的列。例如，如果查询经常以日期范围为目标，例如上个月，那么明智的做法是将 date_key 设置为第一个排序键。查询优化器只扣描上个月的行，这将比扫描所有行快得多。
上述这些优化对于数据仓库很有意义，因为大多数负载由分析人员运行的大型只读查询组成。面向列的存储 、压缩和排序都非常有助于==加速读取查询==。但是，它们的缺点是==让写入更加困难==。
像 B-tree 使用的原地更新方式，对于压缩的列是不可能的。如果在排序表的中间插一行，那么很可能不得不重写所有的列文件。因为各行是由它们在列中的位置标识的，所以插入操作必须一致地更新所有列。
幸运的是，在本章前面已经看到了一个很好的解决方案 LSM-tree。所有的写入首先进入内存存储区，将其添加到已排序的结构中，接着再准备写人磁盘。内存中的存储是面向行还是面向列无关紧要。当累积了足够的写入时，它们将与磁盘上的列文件合并，并批量写入新文件。
执行查询时，需要检查磁盘上的列数据和内存中最近的写入，并结合这两者。而查询优化器可以对用户隐藏这些内部细节。
数据仓库的另一个值得一提的是物化聚合（materialized aggregates）。如前所述，数据仓库查询通常涉及聚合函数，例如 SQL 中的 COUNT 、SUM 、AVG 、MIN 或 MAX。如果许多不同查询使用相同的聚合，每次都处理原始数据将非常浪费。为什么不缓存查询最常使用的一些计数或总和呢？
创建这种缓存的一种方式是==物化视图==（materialized view）。在关系数据模型中，它通常被定义为标准（虚拟）视图：一个类似表的对象，其内容是一些查询的结果。不同的是，物化视图是查询结果的实际副本，并被写到磁盘，而虚拟视图只是用于编写查询的快捷方式。
物化视图常见的一种特殊情况称为数据立方体或 OLAP 立方体，它是由不同维度分组的聚合网格，如图 3-12 所示的例子。
