第三章 存储与检索

驱动数据库的数据结构

使用一个函数实现在文件的末尾追加数据，另一个函数查找数据时从头到尾进行遍历查找。
这种方法对于极其简单的场景其实有非常好的性能，因为在文件尾部追加写入通常是非常高效的。
许多数据库在内部使用了日志（log），也就是一个 仅追加（append-only） 的数据文件。
真正的数据库有更多的问题需要处理（如并发控制，回收磁盘空间以避免日志无限增长，处理错误与部分写入的记录），但基本原理是一样的。
但是当数据库中有大量记录时这个查询函数的性能会非常糟糕。
因此需要索引来高效查找数据库中特定的键值。

精心选择的索引加快了读查询的速度，但是每个索引都会拖慢写入速度。因为这个原因，数据库默认并不会索引所有的内容，而需要你（程序员或DBA）通过对应用查询模式的了解来手动选择索引。你可以选择能为应用带来最大收益，同时又不会引入超出必要开销的索引。

哈希索引

如果数据存储只是一个追加写入的文件，最简单的索引策略就是：保留一个内存中的哈希映射，其中每个键都映射到一个数据文件中的字节偏移量，指明了可以找到对应值的位置。
当你将新的键值对追加写入文件中时，还要更新散列映射，以反映刚刚写入的数据的偏移量（这同时适用于插入新键与更新现有键）。
当你想查找一个值时，使用哈希映射来查找数据文件中的偏移量，寻找（seek） 该位置并读取该值。
可以使用“压缩”的方式，在日志中丢弃重复的键，只保留每个键的最近更新。

真正实施中重要的问题：

• 文件格式：使用二进制格式更快更简单。
• 删除记录：需要在数据文件中附加一个特殊的删除记录
• 崩溃恢复：数据库重启后要从磁盘上找到每个键的最近记录，需要花费很长的时间、
• 部分写入记录：数据库可能随时崩溃，包括将记录附加到日志中途。 Bitcask文件包含校验和，允许检测和忽略日志的这些损坏部分。
• 并发控制：常见的实现是只有一个写入器线程，数据文件段是附加的，或者是不可变的，所以它们可以被多个线程同时读取。

为什么不更新文件，用新值覆盖旧值，而是只能追加：

• 追加和分段合并是顺序写入操作，通常比随机写入快得多，尤其是在磁盘旋转硬盘上。
• 如果段文件是附加的或不可变的，并发和崩溃恢复就简单多了。
• 合并旧段可以避免数据文件随着时间的推移而分散的问题。

哈希表索引的局限性：

• 散列表必须能放入内存
• 查询效率不高

SSTables和LSM树

【上面所说的日志结构哈希索引的键是按写入的顺序出现的，在内存的索引虽然速度快，但是也要顺序查找，可以将键按照字母排序，加快查找速度】
这个格式称为排序字符串表（Sorted String Table），简称SSTable。
SSTable有几个很大的优势：

• 合并段是简单而高效的，即使文件大于可用内存。这种方法就像归并排序算法中使用的方法一样。
• 为了在文件中找到一个特定的键，你不再需要保存内存中所有键的索引。【也就是哈希表索引大小不再限制】
• 可以将哈希索引表分块存储在磁盘中。【相当于为索引添加索引，根据字母位置加载相应的索引表】

构建和维护SSTables

• 写入时，将其添加到内存中的平衡树数据结构（例如，红黑树）。这个内存树有时被称为内存表（memtable）。
• 当内存表大于某个阈值（通常为几兆字节）时，将其作为SSTable文件写入磁盘。这可以高效地完成，因为树已经维护了按键排序的键值对。新的SSTable文件成为数据库的最新部分。当SSTable被写入磁盘时，写入可以继续到一个新的内存表实例。
• 为了提供读取请求，首先尝试在内存表中找到关键字，然后在最近的磁盘段中，然后在下一个较旧的段中找到该关键字。
• 有时会在后台运行合并和压缩过程以组合段文件并丢弃覆盖或删除的值。
• 可以使用一个日志结构保存每一次写入操作进来，如果数据库崩溃可以按这个日志恢复内存表

用SSTables制作LSM树

性能优化

当查找数据库中不存在的键时，LSM树算法可能会很慢，为了优化这种访问，存储引擎通常使用额外的Bloom过滤器。
不同的策略来确定SSTables如何被压缩和合并的顺序和时间。最常见的选择是大小分层压实。在规模级别的调整中，更新和更小的SSTables先后被合并到更老的和更大的SSTable中。在水平压实中，关键范围被拆分成更小的SSTables，而较旧的数据被移动到单独的“水平”，这使得压缩能够更加递增地进行，并且使用更少的磁盘空间。

B树

使用最广泛的索引结构是B树。
B树将数据库分解成固定大小的块或页面，传统上大小为4KB（有时会更大），并且一次只能读取或写入一个页面。这种设计更接近于底层硬件，因为磁盘也被安排在固定大小的块中。

让B树更可靠

为了使数据库对崩溃具有韧性，B树实现通常会带有一个额外的磁盘数据结构：预写式日志（WAL, write-ahead-log）（也称为重做日志（redo log））。这是一个仅追加的文件，每个B树修改都可以应用到树本身的页面上。当数据库在崩溃后恢复时，这个日志被用来使B树恢复到一致的状态

更新页面的一个额外的复杂情况是，如果多个线程要同时访问B树，则需要仔细的并发控制 —— 否则线程可能会看到树处于不一致的状态。这通常通过使用锁存器（latches）（轻量级锁）保护树的数据结构来完成。

B树优化

• 一些数据库（如LMDB）使用写时复制方案，而不是覆盖页面并维护WAL进行崩溃恢复。
• 我们可以通过不存储整个键来节省页面空间。
• 许多B树实现尝试布局树，使得叶子页面按顺序出现在磁盘上。
• 使用额外的指针指向左边和右边的兄弟页面，这允许不跳回父页面就能顺序扫描。
• B树的变体如分形树，借用一些日志结构的思想来减少磁盘寻道（而且它们与分形无关）。

比较B树和LSM树

通常LSM树的写入速度更快，而B树的读取速度更快。
LSM树上的读取通常比较慢，因为它们必须在压缩的不同阶段检查几个不同的数据结构和SSTables。

LSM树的优点

• LSM树通常能够比B树支持更高的写入吞吐量，部分原因是它们有时具有较低的写放大（尽管这取决于存储引擎配置和工作负载），部分是因为它们顺序地写入紧凑的SSTable文件而不是必须覆盖树中的几个页面。这种差异在磁性硬盘驱动器上尤其重要，顺序写入比随机写入快得多。
• LSM树可以被压缩得更好，因此经常比B树在磁盘上产生更小的文件。

LSM树的缺点

• 日志结构存储的缺点是压缩过程有时会干扰正在进行的读写操作。
• 磁盘的有限写入带宽需要在初始写入（记录和刷新内存表到磁盘）和在后台运行的压缩线程之间共享。

其他索引结构

在关系数据库中，可以在同一个表上创建多个二级索引，而且这些索引通常对于有效地执行联接而言至关重要。

将值存储在索引中

在某些情况下，从索引到堆文件的额外跳跃对读取来说性能损失太大，因此可能希望将索引行直接存储在索引中。这被称为聚集索引。
在 聚集索引（clustered index） （在索引中存储所有行数据）和 非聚集索引（nonclustered index） （仅在索引中存储对数据的引用）之间的折衷被称为 包含列的索引（index with included columns）或覆盖索引（covering index），其存储表的一部分在索引内。这允许通过单独使用索引来回答一些查询（这种情况叫做：索引 覆盖（cover）了查询）。
聚簇和覆盖索引可以加快读取速度，但是它们需要额外的存储空间，并且会增加写入开销。数据库还需要额外的努力来执行事务保证，因为应用程序不应该因为重复而导致不一致。

多列索引

最常见的多列索引被称为 连接索引（concatenated index） ，它通过将一列的值追加到另一列后面，简单地将多个字段组合成一个键（索引定义中指定了字段的连接顺序）。
多维索引（multi-dimensional index） 是一种查询多个列的更一般的方法，这对于地理空间数据尤为重要。

全?搜索和模糊索引

全文搜索引擎通常允许搜索一个单词以扩展为包括该单词的同义词，忽略单词的语法变体，并且搜索在相同文档中彼此靠近的单词的出现，并且支持各种其他功能取决于文本的语言分析。

在内存中存储一切

磁盘有两个显著的优点：它们是耐用的（它们的内容在电源关闭时不会丢失），并且每GB的成本比RAM低。
内存数据库的性能优势并不是因为它们不需要从磁盘读取的事实。即使是基于磁盘的存储引擎也可能永远不需要从磁盘读取，因为操作系统缓存最近在内存中使用了磁盘块。相反，它们更快的原因在于省去了将内存数据结构编码为磁盘数据结构的开销。

事务处理理还是分析？

应用程序通常使用索引通过某个键查找少量记录。根据用户的输入插入或更新记录。由于这些应用程序是交互式的，因此访问模式被称为 在线事务处理（OLTP, OnLine Transaction Processing） 。
一些查询通常由业务分析师编写，并提供给帮助公司管理层做出更好决策（商业智能）的报告。为了区分这种使用数据库的事务处理模式，它被称为在线分析处理（OLAP, OnLine Analytice Processing）。
比较交易处理和分析系统的特点：

数据仓库

这些OLTP系统往往对业务运作至关重要，因而通常会要求 高可用 与 低延迟。
相比之下，数据仓库是一个独立的数据库，分析人员可以查询他们想要的内容而不影响OLTP操作。
数据仓库包含公司各种OLTP系统中所有的只读数据副本。从OLTP数据库中提取数据（使用定期的数据转储或连续的更新流），转换成适合分析的模式，清理并加载到数据仓库中。将数据存入仓库的过程称为“抽取-转换-加载（ETL）”，

使用单独的数据仓库，而不是直接查询OLTP系统进行分析的一大优势是数据仓库可针对分析访问模式进行优化。

OLTP数据库和数据仓库之间的分歧

数据仓库的数据模型通常是关系型的，因为SQL通常很适合分析查询。有许多图形数据分析工具可以生成SQL查询，可视化结果，并允许分析人员探索数据（通过下钻，切片和切块等操作）。

星型和雪花型：分析的模式

列存储

数据库查询中很少使用select * 语句查询，通常只需要部分列，而普通行存储的数据库往往会将整个一行的数据都读入到磁盘中，这对于有几百列的表来说会浪费很多性能。
面向列的存储背后的想法很简单：不要将所有来自一行的值存储在一起，而是将来自每一列的所有值存储在一起。如果每个列存储在一个单独的文件中，查询只需要读取和解析查询中使用的那些列，这可以节省大量的工作。

面向列的存储布局依赖于包含相同顺序行的每个列文件。 因此，如果您需要重新组装整行，您可以从每个单独的列文件中获取第23项，并将它们放在一起形成表的第23行。

列压缩

除了仅从磁盘加载查询所需的列以外，我们还可以通过压缩数据来进一步降低对磁盘吞吐量的需求。幸运的是，面向列的存储通常很适合压缩。

例如位图编码和游程编码

内存带宽和向量处理

按位“与”和“或”运算符可以被设计为直接在这样的压缩列数据块上操作。这种技术被称为矢量化处理

列存储中的排序顺序

在列存储中，存储行的顺序并不一定很重要。
排序顺序的另一个好处是它可以帮助压缩列。如果主要排序列没有多个不同的值，那么在排序之后，它将具有很长的序列，其中相同的值连续重复多次。

几个不同的排序顺序

不同的查询受益于不同的排序顺序，数据需要复制到多台机器，这样，如果一台机器发生故障，您不会丢失数据。您可能还需要存储以不同方式排序的冗余数据，以便在处理查询时，可以使用最适合查询模式的版本。

写?列存储

使用B树的更新就地方法对于压缩的列是不可能的。如果你想在排序表的中间插入一行，你很可能不得不重写所有的列文件。由于行由列中的位置标识，因此插入必须始终更新所有列。

幸运的是，本章前面已经看到了一个很好的解决方案：LSM树。所有的写操作首先进入一个内存中的存储，在这里它们被添加到一个已排序的结构中，并准备写入磁盘。内存中的存储是面向行还是列的，这并不重要。当已经积累了足够的写入数据时，它们将与磁盘上的列文件合并，并批量写入新文件。

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

数据仓库的另一个值得一提的是物化汇总。如果相同的聚合被许多不同的查询使用，那么可以缓存一些查询使用最频繁的计数或总和。

创建这种缓存的一种方式是物化视图。在关系数据模型中，它通常被定义为一个标准（虚拟）视图：一个类似于表的对象，其内容是一些查询的结果。
物化数据立方体的优点是某些查询变得非常快，因为它们已经被有效地预先计算了。
当底层数据发生变化时，物化视图需要更新，因为它是数据的非规范化副本。数据库可以自动完成，但是这样的更新使得写入成本更高，这就是在OLTP数据库中不经常使用物化视图的原因。在读取繁重的数据仓库中，它们可能更有意义（不管它们是否实际上改善了读取性能取决于个别情况）。

缺点是数据立方体不具有查询原始数据的灵活性，大多数数据仓库试图保留尽可能多的原始数据，并将聚合数据（如数据立方体）仅用作某些查询的性能提升。

第三章