注：书本链接：GitHub - Vonng/ddia: 《Designing Data-Intensive Application》DDIA中文翻译
注：译者文本网站：简介 · ddia-cn
注：如有侵权，请联系删除

第三章：存储与检索

在 第二章 中，我们讨论了数据模型和查询语言，即程序员将数据录入数据库的格式，以及再次要回数据的机制。在本章中我们会从数据库的视角来讨论同样的问题：数据库如何存储我们提供的数据，以及如何在我们需要时重新找到数据。

针对 事务性 负载优化的和针对 分析性 负载优化的存储引擎之间存在巨大差异。

注：我觉得这两个概念与OLAP（在线分析处理）、OLTP（在线事务处理）是一致的。

日志结构（log-structured） 的存储引擎，以及 面向页面（page-oriented） 的存储引擎（例如 B 树）。

1、驱动数据库的数据结构

许多数据库在内部使用了 日志（log），也就是一个 仅追加（append-only） 的数据文件。

（1）散列索引

• 键值数据（key-value Data）

• 散列映射（hash map） 或 散列表（hash table）

• 段（segment）

• 压缩（compaction）

（2）SSTables和LSM树

• 排序字符串表（Sorted String Table）

现在我们可以让我们的存储引擎以如下方式工作：

• 有新写入时，将其添加到内存中的平衡树数据结构（例如红黑树）。这个内存树有时被称为 内存表（memtable）。

• 当 内存表 大于某个阈值（通常为几兆字节）时，将其作为 SSTable 文件写入硬盘。这可以高效地完成，因为树已经维护了按键排序的键值对。新的 SSTable 文件将成为数据库中最新的段。当该 SSTable 被写入硬盘时，新的写入可以在一个新的内存表实例上继续进行。

• 收到读取请求时，首先尝试在内存表中找到对应的键，如果没有就在最近的硬盘段中寻找，如果还没有就在下一个较旧的段中继续寻找，以此类推。

• 时不时地，在后台运行一个合并和压缩过程，以合并段文件并将已覆盖或已删除的值丢弃掉。

日志结构合并树（或 LSM 树）

基于这种合并和压缩排序文件原理的存储引擎通常被称为 LSM 存储引擎。

Lucene，是一种全文搜索的索引引擎，在 Elasticsearch 和 Solr 被使用，它使用类似的方法来存储它的关键词词典【12,13】。全文索引比键值索引复杂得多，但是基于类似的想法：在搜索查询中，由一个给定的单词，找到提及单词的所有文档（网页、产品描述等）。这也是通过键值结构实现的：其中键是 单词（term），值是所有包含该单词的文档的 ID 列表（postings list）。在 Lucene 中，从词语到记录列表的这种映射保存在类似于 SSTable 的有序文件中，并根据需要在后台执行合并【14】。

（3）B树

我们前面看到的日志结构索引将数据库分解为可变大小的段，通常是几兆字节或更大的大小，并且总是按顺序写入段。相比之下，B 树将数据库分解成固定大小的 块（block） 或 分页（page），传统上大小为 4KB（有时会更大），并且一次只能读取或写入一个页面。这种设计更接近于底层硬件，因为硬盘空间也是按固定大小的块来组织的。

• 分支因子（branching factor）

• 预写式日志（WAL，即 write-ahead log，也称为 重做日志，即 redo log）

• 锁存器（latches，轻量级锁）

（4）比较B树和LSM树

• 写入放大（write amplification）：在数据库的生命周期中每笔数据导致对硬盘的多次写入

2、其他索引结构

（1）将值存储在索引中

• 堆文件（heap file）

在 聚集索引（在索引中存储所有的行数据）和 非聚集索引（仅在索引中存储对数据的引用）之间的折衷被称为 覆盖索引（covering index） 或 包含列的索引（index with included columns），其在索引内存储表的一部分列【33】。这允许通过单独使用索引来处理一些查询（这种情况下，可以说索引 覆盖（cover） 了查询）【32】。

（2）多列索引

• 最常见的多列索引被称为 连接索引（concatenated index）

注：这个就是Mysql Innodb中的复合索引

• 多维索引（multi-dimensional index） 是一种查询多个列的更一般的方法，这对于地理空间数据尤为重要。

• 空间填充曲线（space-filling curve） 将二维位置转换为单个数字，然后使用常规 B 树索引。

（3）全文搜索和模糊索引

（4）在内存中存储一切

• 反缓存（anti-caching）：通过在内存不足的情况下将最近最少使用的数据从内存转移到硬盘，并在将来再次访问时将其重新加载到内存中。

注：例如redis的内存淘汰策略

• 非易失性存储器（non-volatile memory, NVM）

3、事务处理还是分析？

数据仓库（data warehouse）

（1）数据仓库

• 将数据存入仓库的过程称为 “抽取 - 转换 - 加载（ETL）”

（2）星型和雪花型：分析的模式

4、列式存储

（1）列压缩

（2）内存带宽和矢量化处理

（3）列式存储中的排序顺序

• 几个不同的排序顺序

（4）写入列式存储

（5）聚合：数据立方体和物化视图

• 物化视图（Materialized View）

本章小结

在本章中，我们试图深入了解数据库是如何处理存储和检索的。将数据存储在数据库中会发生什么？稍后再次查询数据时数据库会做什么？

在高层次上，我们看到存储引擎分为两大类：针对 事务处理（OLTP） 优化的存储引擎和针对 在线分析（OLAP） 优化的存储引擎。这两类使用场景的访问模式之间有很大的区别：

• OLTP 系统通常面向最终用户，这意味着系统可能会收到大量的请求。为了处理负载，应用程序在每个查询中通常只访问少量的记录。应用程序使用某种键来请求记录，存储引擎使用索引来查找所请求的键的数据。硬盘查找时间往往是这里的瓶颈。

• 数据仓库和类似的分析系统会少见一些，因为它们主要由业务分析人员使用，而不是最终用户。它们的查询量要比 OLTP 系统少得多，但通常每个查询开销高昂，需要在短时间内扫描数百万条记录。硬盘带宽（而不是查找时间）往往是瓶颈，列式存储是针对这种工作负载的日益流行的解决方案。

在 OLTP 这一边，我们能看到两派主流的存储引擎：

• 日志结构学派：只允许追加到文件和删除过时的文件，但不会更新已经写入的文件。Bitcask、SSTables、LSM 树、LevelDB、Cassandra、HBase、Lucene 等都属于这个类别。

• 就地更新学派：将硬盘视为一组可以覆写的固定大小的页面。B 树是这种理念的典范，用在所有主要的关系数据库和许多非关系型数据库中。

日志结构的存储引擎是相对较新的技术。他们的主要想法是，通过系统性地将随机访问写入转换为硬盘上的顺序写入，由于硬盘驱动器和固态硬盘的性能特点，可以实现更高的写入吞吐量。

关于 OLTP，我们最后还介绍了一些更复杂的索引结构，以及针对所有数据都放在内存里而优化的数据库。

然后，我们暂时放下了存储引擎的内部细节，查看了典型数据仓库的高级架构，并说明了为什么分析工作负载与 OLTP 差别很大：当你的查询需要在大量行中顺序扫描时，索引的重要性就会降低很多。相反，非常紧凑地编码数据变得非常重要，以最大限度地减少查询需要从硬盘读取的数据量。我们讨论了列式存储如何帮助实现这一目标。

作为一名应用程序开发人员，如果你掌握了有关存储引擎内部的知识，那么你就能更好地了解哪种工具最适合你的特定应用程序。当你调整数据库的优化参数时，这种理解让你能够设想增减某个值会产生怎样的效果。

尽管本章不能让你成为一个特定存储引擎的调参专家，但它至少大概率使你有了足够的概念与词汇储备去读懂你所选择的数据库的文档。