DDIA 第三章：存储与检索

本文是《数据密集型应用系统设计》（DDIA）的读书笔记，一共十二章，我已经全部阅读并且整理完毕。
采用一问一答的形式，并且用列表形式整理了原文。 笔记的内容大概是原文的 1/5 ~
1/3，所以你如果没有很多时间看书的话，看我的笔记也就够了！

本章介绍了传统关系型数据库与“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） 的数据文件。
• 另一方面，如果这个数据库中有着大量记录，则这个db_get 函数的性能会非常糟糕。
  • 每次你想查找一个键时，db_get 必须从头到尾扫描整个数据库文件来查找键的出现。
  • 用算法的语言来说，查找的开销是 O(n) ：如果数据库记录数量 n 翻了一倍，查找时间也要翻一倍。

索引

为了高效查找数据库中特定键的值，我们需要一个数据结构：索引（index）。

• 索引背后的大致思想是，保存一些额外的元数据作为路标，帮助你找到想要的数据。
• 索引是从主数据衍生的**附加（additional）**结构。
• 许多数据库允许添加与删除索引，这不会影响数据的内容，它只影响查询的性能。
• 维护额外的结构会产生开销，特别是在写入时。写入性能很难超过简单地追加写入文件，因为追加写入是最简单的写入操作。
• 任何类型的索引通常都会减慢写入速度，因为每次写入数据时都需要更新索引。
• 这是存储系统中一个重要的权衡：精心选择的索引加快了读查询的速度，但是每个索引都会拖慢写入速度。

哈希索引

• 键值存储与在大多数编程语言中可以找到的字典（dictionary）类型非常相似，通常字典都是用散列映射（hash map）（或哈希表（hash table））实现的。

假设我们的数据存储只是一个追加写入的文件，最简单的索引策略就是：保留一个内存中的哈希映射，其中每个键都映射到一个数据文件中的字节偏移量，指明了可以找到对应值的位置

• 新的键值写入文件时，还要更新散列映射。
• 查找一个值时，使用哈希映射来查找数据文件中的偏移量，寻找（seek） 该位置并读取该值。
• Bitcask实际上就是这么做的，非常适合每个键的值频繁更新的情况。

如果一直追加文件，怎么防止用完磁盘空间？

• 将日志分为特定大小的段，当日志增长到特定尺寸时关闭当前段文件，并开始写入一个新的段文件。
• 然后，我们就可以对这些段进行压缩（compaction）。
• 压缩意味着在日志中丢弃重复的键，只保留每个键的最近更新。

也可以把多个段的内容压缩合并到一起。

• 段被写入后永远不会被修改，所以合并的段被写入一个新的文件。
• 冻结段的合并和压缩可以在后台线程中完成，在进行时，我们仍然可以继续使用旧的段文件来正常提供读写请求。
• 合并过程完成后，我们将读取请求转换为使用新的合并段而不是旧段 —— 然后可以简单地删除旧的段文件。
• 每个段都有自己的内存散列表，将键映射到文件偏移量。查找键时，依次遍历所有的散列表。

重要的问题：

1. 文件格式
   1. csv 不好，使用二进制格式更快。
2. 删除记录
   1. 删除一个键，则必须在数据文件（有时称为逻辑删除）中附加一个特殊的删除记录。
   2. 当日志段被合并时，逻辑删除告诉合并过程放弃删除键的任何以前的值。
3. 崩溃恢复
   1. 如果数据库重新启动，则内存散列映射将丢失。
   2. 可以根据日志文件重新恢复每个段的哈希映射，但段很大的时候，很费时间。
   3. Bitcask通过存储加速恢复磁盘上每个段的哈希映射的快照，可以更快地加载到内存中。
4. 部分写入记录
   1. 数据库可能随时崩溃，包括将记录附加到日志中途。
   2. Bitcask文件包含校验和，允许检测和忽略日志的这些损坏部分。
5. 并发控制
   1. 写操作是以严格顺序的顺序附加到日志中的，所以常见的方法是只有一个写线程。
   2. 读操作可以有多个线程同时读取。

为什么采用追加模式，而不是不更新文件，用新值覆盖旧值？
原因有几个：

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

哈希表索引的局限性：

• 散列表必须能放进内存：当有很多键的时候，Hash 冲突，占用内存。
• 范围查询效率不高：不支持查一个取值区间内的所有键。

SSTables和LSM树

在之前的存储中，每个日志结构存储段都是一系列键值对。这些对按照它们写入的顺序出现，而不是键值对的顺序。
我们做一个简单的改变：我们要求键值对的序列按键排序。把这个格式称为排序字符串表（Sorted String Table），简称 SSTable。同时，要求每个键只在每个合并的段文件中出现一次（压缩过程已经保证）。

SSTable 与散列索引日志段相比，有几个很大的优势：

1. 合并段是简单而高效的，即使文件大于可用内存。方法类似于归并排序。
   1. 如果在几个输入段中出现相同的键，该怎么办？
      1. 答：保留最近段的值，并丢弃旧段中的值。
2. 为了在文件中找到一个特定的键，你不再需要保存内存中所有键的索引。因为是有序的，可以先查找出键所处的范围，然后就找到这个键所在的偏移量的区间。比如可以从 handbag 和 handsome 的偏移量找到 handiwork 的区间。

构建和维护SSTables

如何让数据首先被按键排序呢？

• 在内存中排序简单的多，比如红黑树、AVL 树；

存储工作的操作步骤：

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

如何解决数据库崩溃，则最近的写入（在内存表中，但尚未写入磁盘）将丢失的问题？

• 我们可以在磁盘上保存一个单独的日志，每个写入都会立即被附加到磁盘上，
• 该日志不是按排序顺序，但这并不重要，因为它的唯一目的是在崩溃后恢复内存表。
• 每当内存表写出到SSTable时，相应的日志都可以被丢弃。

用SSTables制作LSM树

LSM 树：在 LevelDB 和 RocksDB 使用。

性能优化

1. 当查找数据库中不存在的键时，LSM树算法可能会很慢：您必须检查内存表，然后将这些段一直回到最老的（可能必须从磁盘读取每一个），然后才能确定键不存在。
   • 解决办法：布隆过滤器。
2. SSTables 被压缩和合并的顺序和时间
   • 大小分层压实。
   • LevelDB和RocksDB使用平坦压缩（LevelDB因此得名）；
   • HBase 使用大小分层；
   • Cassandra 同时支持。

B树

像SSTables一样，B树保持按键排序的键值对，这允许高效的键值查找和范围查询。
不同：

• 日志结构索引将数据库分解为可变大小的段，通常是几兆字节或更大的大小，并且总是按顺序编写段。
• B 树将数据库分解成固定大小的块或页面，传统上大小为4KB（有时会更大），并且一次只能读取或写入一个页面。
• 这种设计更接近于底层硬件，因为磁盘也被安排在固定大小的块中。

每个页面都可以使用地址或位置来标识，这允许一个页面引用另一个页面 —— 类似于指针，但在磁盘而不是在内存中。

查找过程：

• 一个页面会被指定为B树的根；在索引中查找一个键时，就从这里开始。
• 该页面包含几个键和对子页面的引用。
• 每个子页面负责一段连续范围的键，引用之间的键，指明了引用子页面的键范围。
• 最后，我们可以看到包含单个键（叶页）的页面，该页面包含每个键的内联值，或者包含对可以找到值的页面的引用。

更新过程：

• 搜索包含该键的叶页，更改该页中的值，并将该页写回到磁盘原来的位置（对该页的任何引用保持有效）

插入过程：

• 找到其范围包含新键的页面，并将其添加到该页面。
• 如果页面中没有足够的可用空间容纳新键，则将其分成两个半满页面，并更新父页面以解释键范围的新分区。

删除过程：

• 删除一个键（同时保持树平衡）就牵扯很多其他东西了。

深度：

• 该算法确保树保持平衡：具有 n 个键的B树总是具有 $O(logn)$ 的深度。
• 大多数数据库可以放入一个三到四层的 B 树，所以你不需要遵追踪多页面引用来找到你正在查找的页面。 （分支因子为 500 的 4KB 页面的四级树可以存储多达 256TB 。）

让B树更可靠

• B 树的基本底层写操作是用新数据覆盖磁盘上的页面。
• 假定覆盖不改变页面的位置；
• 而日志结构索引（如LSM树）只附加到文件（并最终删除过时的文件），但从不修改文件。

危险操作：

• 插入导致页面过度而拆分页面，则需要编写已拆分的两个页面，并覆盖其父页面以更新对两个子页面的引用。
• 这是一个危险的操作，因为如果数据库在仅有一些页面被写入后崩溃，那么最终将导致一个损坏的索引（例如，可能有一个孤儿页面不是任何父项的子项） 。

预写式日志（WAL）

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

并发访问：

• 更新页面时，如果多个线程要同时访问B树，则需要仔细的并发控制，否则可能会看到树处于不一致的状态。
• 通过使用锁存器（latches）（轻量级锁）保护树的数据结构来完成
• 而 LSM 比较简单：在后台完成所有的合并，不干扰查询；通过「原子交换」把旧的分段变为新的分段。

B树优化

• LMDB 数据库中使用「写时复制方案 」，而不是不是覆盖页面并维护 WAL 进行崩溃恢复。
  • 修改的页面被写入到不同的位置，并且树中的父页面的新版本被创建，指向新的位置。
  • 这种方法对于并发控制也很有用。
• 保存键的缩略信息，而不是完整的键。
  • 键只用保存一个区间，而不是具体的数值（类似于 B+树）。
  • 可以包含更多的键，减少树的层次。
• 不方便扫描大部分关键词的范围查找。
  • 许多B树实现尝试布局树，使得叶子页面按顺序出现在磁盘上。
  • 但是，随着树的增长，维持这个顺序是很困难的。
  • 相比之下，由于LSM树在合并过程中一次又一次地重写存储的大部分，所以它们更容易使顺序键在磁盘上彼此靠近。
• 额外的指针已添加到树中。
  • 例如，每个叶子页面可以在左边和右边具有对其兄弟页面的引用，这允许不跳回父页面就能顺序扫描。
• B树的变体如分形树借用一些日志结构的思想来减少磁盘寻道（而且它们与分形无关）。

比较B树和LSM树

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

LSM树的优点

• B树索引必须至少两次写入每一段数据：一次写入预先写入日志，一次写入树页面本身（也许再次分页）
• 即使在该页面中只有几个字节发生了变化，也需要一次编写整个页面的开销。
• 有些存储引擎甚至会覆盖同一个页面两次，以免在电源故障的情况下导致页面部分更新

写放大

• 反复压缩和合并SSTables，日志结构索引也会重写数据。
• 在数据库的生命周期中写入数据库导致对磁盘的多次写入 —— 被称为写放大（write amplification）。
• 存储引擎写入磁盘的次数越多，可用磁盘带宽内的每秒写入次数越少。

LSM树通常能够比B树支持更高的写入吞吐量：

• 部分原因是它们有时具有较低的写放大（尽管这取决于存储引擎配置和工作负载）
• 部分是因为它们顺序地写入紧凑的SSTable文件而不是必须覆盖树中的几个页面
• 这种差异在磁性硬盘驱动器上尤其重要，顺序写入比随机写入快得多。

文件碎片：

• LSM树可以被压缩得更好，因此经常比B树在磁盘上产生更小的文件。
• B树存储引擎会由于分割而留下一些未使用的磁盘空间
• 由于LSM树不是面向页面的，并且定期重写SSTables以去除碎片，所以它们具有较低的存储开销，特别是当使用平坦压缩时

LSM树的缺点

日志结构存储的缺点是压缩过程有时会干扰正在进行的读写操作。
B树的行为则相对更具可预测性。

高写入吞吐量：

• 磁盘的有限写入带宽需要在初始写入（记录和刷新内存表到磁盘）和在后台运行的压缩线程之间共享。
• 写入空数据库时，可以使用全磁盘带宽进行初始写入，但数据库越大，压缩所需的磁盘带宽就越多。

压缩和读取的速度：

• 如果写入吞吐量很高，并且压缩没有仔细配置，压缩跟不上写入速率。
• 在这种情况下，磁盘上未合并段的数量不断增加，直到磁盘空间用完，读取速度也会减慢，因为它们需要检查更多段文件。

键出现的个数：

• B树的一个优点是每个键只存在于索引中的一个位置，而日志结构化的存储引擎可能在不同的段中有相同键的多个副本。
• 有利于事务语义。
• 在许多关系数据库中，事务隔离是通过在键范围上使用锁来实现的，在B树索引中，这些锁可以直接连接到树

其他索引结构

前面讨论的是关键值索引，它们就像关系模型中的主键（primary key） 索引。主键唯一标识关系表中的一行、一个文档、一个顶点。

二级索引

• 在关系数据库中，您可以使用 CREATE INDEX 命令在同一个表上创建多个二级索引，而且这些索引通常对于有效地执行联接而言至关重要。
• 一个二级索引可以很容易地从一个键值索引构建，区别是键不是唯一的。实现方式：
  • 通过使索引中的每个值，成为匹配行标识符的列表（如全文索引中的发布列表）
  • 通过向每个索引添加行标识符来使每个关键字唯一
  • 无论哪种方式，B树和日志结构索引都可以用作辅助索引。

将值存储在索引中

索引中的关键字是查询搜索的内容，它属于两种之一：

• 实际行（文档，顶点）
• 对存储在别处的行的引用。此时，行被存储的地方被称为**堆文件（heap file），**并且存储的数据没有特定的顺序
  • 堆文件很常见。
  • 它避免了在存在多个二级索引时复制数据
  • 新值字节数不大于旧值，原地覆盖；
  • 新值更大，需要移到堆中有足够空间的新位置；
    • 此时，要么所有索引都更新指向新堆位置；
    • 要么在旧堆位置留一个转发指针。

聚集索引

• 从索引到堆文件的额外跳转性能损失太大，希望可以把索引行直接进存储到索引中。被叫做聚集索引。
• 在 MySQL 的 InnoDB 存储引擎中，表的主键总是一个聚簇索引，二级索引用主键（而不是堆文件中的位置）
• 在SQL Server中，可以为每个表指定一个聚簇索引。

包含列的索引或覆盖索引

• 在 聚集索引（clustered index） （在索引中存储所有行数据）和 非聚集索引（nonclustered index） （仅在索引中存储对数据的引用）之间的折衷被称为 包含列的索引（index with included columns）或覆盖索引（covering index），其存储表的一部分在索引内。
• 允许通过单独使用索引来回答一些查询。
• 加快了读取速度，但是增加了额外的存储空间，增加了写入开销，还要事务保证。

多列索引

上面讨论的都是一个 key 对应一个 value，如果需要同时根据一个表中的多个列（或文档中的多个字段）进行查询，则不行。

• 连接索引（concatenated index）
  • 将一列的值追加到另一列后面，简单地将多个字段组合成一个键。
  • 但是这不能做复杂查询。
• 多维索引（multi-dimensional index）
  • 比如需要根据经纬度做二维范围查询，则 B 树和 LSM 树不能高效；
  • 普遍做法是用特殊化的空间索引，比如** R 树（TODO）**。
  • 多维索引除了地理位置，还可以用于其他很多地方：电子网站、天气数据。

全文搜索和模糊索引

上文讨论的索引都是查询确切的值或者确定范围的值，如果搜索类似的键，需要用模糊查询。

全文搜索引擎

• 允许搜索一个单词以扩展为包括该单词的同义词，忽略单词的语法变体，并且搜索在相同文档中彼此靠近的单词的出现，并且支持各种其他功能取决于文本的语言分析。
• 为了处理文档或查询中的拼写错误，Lucene能够在一定的编辑距离内搜索文本（编辑距离1意味着添加，删除或替换了一个字母）

Lucene

• 为其词典使用了一个类似于SSTable的结构。
• 这个结构需要一个小的内存索引，告诉查询在排序文件中哪个偏移量需要查找关键字。
• 在 LevelDB 中，这个内存中的索引是一些键的稀疏集合。
• 但在 Lucene 中，内存中的索引是键中字符的有限状态自动机，类似于trie。
• 这个自动机可以转换成 Levenshtein 自动机，它支持在给定的编辑距离内有效地搜索单词。

在内存中存储一切

对于磁盘和SSD，如果要在读取和写入时获得良好性能，则需要仔细地布置磁盘上的数据。
磁盘优点：耐用，成本低。
内存变得便宜，促进了内存数据库发展。

内存数据库

• 某些内存中的键值存储（如Memcached）仅用于缓存，在重新启动计算机时丢失的数据是可以接受的。
• 但其他内存数据库的目标是持久性，可以通过特殊的硬件（例如电池供电的RAM），将更改日志写入磁盘，将定时快照写入磁盘或通过复制内存来实现，记忆状态到其他机器。

实现

• 内存数据库重新启动时，需要从磁盘或通过网络从副本重新加载其状态（除非使用特殊的硬件）。
• 尽管写入磁盘，它仍然是一个内存数据库，因为磁盘仅用作耐久性附加日志，读取完全由内存提供。
• 写入磁盘也具有操作优势：磁盘上的文件可以很容易地由外部实用程序进行备份，检查和分析。

常见产品

• VoltDB，MemSQL和Oracle TimesTen等产品是具有关系模型的内存数据库
• RAM Cloud是一个开源的内存键值存储器，具有持久性（对存储器中的数据以及磁盘上的数据使用日志结构化方法）
• Redis和Couchbase通过异步写入磁盘提供了较弱的持久性。

内存数据库性能优势到底在哪？

• 内存数据库的性能优势并不是因为它们不需要从磁盘读取的事实。
• 即使是基于磁盘的存储引擎也可能永远不需要从磁盘读取，因为操作系统缓存最近在内存中使用了磁盘块。
• 相反，它们更快的原因在于省去了将内存数据结构编码为磁盘数据结构的开销。

除了性能还有什么优势？

• 提供了难以用基于磁盘的索引实现的数据模型。
• 例如，Redis为各种数据结构（如优先级队列和集合）提供了类似数据库的接口。因为它将所有数据保存在内存中，所以它的实现相对简单。

内存不够用怎么办？

• 反缓存（anti-caching） 方法通过在内存不足的情况下将最近最少使用的数据从内存转移到磁盘，并在将来再次访问时将其重新加载到内存中。
• 这与操作系统对虚拟内存和交换文件的操作类似，但数据库可以比操作系统更有效地管理内存，因为它可以按单个记录的粒度工作，而不是整个内存页面。
• 尽管如此，这种方法仍然需要索引能完全放入内存中。

事务处理还是分析？

事务处理

• 早起的业务处理，典型的数据库写入与一笔商业交易（transaction）相对应，以后交易/事务（transaction） 仍留了下来。
• 事务不一定具有ACID（原子性，一致性，隔离性和持久性）属性。
• 事务处理只是意味着允许客户端进行低延迟读取和写入 —— 而不是只能定期运行（例如每天一次）的批量处理作业。
• 数据库仍然常被用作在线事务处理（OLTP, OnLine Transaction Processing） 。

数据分析

• 数据库也开始越来越多地用于数据分析，需要扫描大量记录；
• 为了将这种使用数据库的模式和事务处理区分开，它被称为在线分析处理（OLAP, OnLine Analytice Processing）

表3-1 比较交易处理和分析系统的特点

属性	事务处理 OLTP	分析系统 OLAP
主要读取模式	查询少量记录，按键读取	在大批量记录上聚合
主要写入模式	随机访问，写入要求低延时	批量导入（ETL），事件流
主要用户	终端用户，通过Web应用	内部数据分析师，决策支持
处理的数据	数据的最新状态（当前时间点）	随时间推移的历史事件
数据集尺寸	GB ~ TB	TB ~ PB

起初，相同的数据库用于事务处理和分析查询，SQL 可以支持 OLTP 和 OLAP。现在有趋势在用数据仓库。

数据仓库

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

• 使用单独的数据仓库，而不是直接查询OLTP系统进行分析的一大优势是数据仓库可针对分析访问模式进行优化。上文的索引不适合数据仓库，需要单独的存储引擎。

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

• 数据仓库的数据模型通常是关系型的，因为SQL通常很适合分析查询。
• 表面上，一个数据仓库和一个关系OLTP数据库看起来很相似，因为它们都有一个SQL查询接口。
• 实际上，内部完全不同，因为对不同的查询模式进行了优化。
• 一般的数据库都把重点放在支持事务处理或分析工作负载上，而不是两者都支持。

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

• 事务处理领域中，使用了大量不同的数据模型。
• 分析型业务中，数据模型的多样性则少得多。许多数据仓库都以相当公式化的方式使用，被称为星型模式（也称为维度建模）。

** 用于数据仓库的星型模式的示例**

• 在模式的中心是一个所谓的事实表（在这个例子中，它被称为 fact_sales）。
• 事实表的每一行代表在特定时间发生的事件（这里，每一行代表客户购买的产品）。
• 周围是维度表。

• 事实表可能非常大，有万亿行和数PB的数据，列通常超过 100 列。
• 被称为“星型模式”是因为事实表在中间，维度表在周围，像星星一样。
• “雪花模式”：维度表进一步拆分成子维度表。
• “星型模式”比较简单，是首选。

列存储

• 事实表的高效存储和查询是问题。
• 维度表比较小，不讨论。
• 在分析中经常只查询部分列，而不是所有列。

面向列的存储

• 不是把每一行的值存储在一起，而是将每一列的所有值存放在一起。
• 面向列的存储布局依赖于每个列文件包含相同顺序的行。

列压缩

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

位图编码

• 当 n 非常大，大部分位图中将会有很多的零（我们说它们是稀疏的）。
• 位图可以另外进行游程编码，这可以使列的编码非常紧凑。
• 位图索引可以很方便的做各种查询：ADN/OR

内存带宽和向量处理

• 需要扫描数百万行的数据仓库查询来说，瓶颈：
  • 是从磁盘获取数据到内存的带宽。
  • 主存储器带宽到CPU缓存中的带宽，避免CPU指令处理流水线中的分支错误预测和泡沫，以及在现代中使用单指令多数据（SIMD）指令CPU
• 面向列的存储布局：
  • 可以将大量压缩的列数据放在CPU的L1缓存中，然后在紧密的循环中循环（即没有函数调用）
  • 更有利于 CPU 的计算。

列存储中的排序顺序

• 在列存储中，存储行的顺序并不一定很重要。
• 按插入顺序存储它们是最简单的，因为插入一个新行只需要追加到每个列文件。
• 每列独自排序是没有意义的，因为那样我们就不会知道列中的哪些项属于同一行
• 即使按列存储数据，也需要一次对整行进行排序。

好处

• 速度快：这样数据库的管理员可以根据他们对常用查询的了解来选择表格应该被排序的列。
• 压缩列：第一个排序键的压缩效果最强。

几个不同的排序顺序

• 不同的查询受益于不同的排序顺序，而无论如何，数据需要复制到多台机器，
• 在一个面向列的存储中有多个排序顺序有点类似于在一个面向行的存储中有多个二级索引。

写入列存储

列存储的优点：大部分只用查询；压缩和排序都有助于更快地读取这些查询。
缺点：写入困难。插入必须始终更新所有列。

解决方案：LSM树。

• 现在内存中存储，添加到一个已排序的结构中，然后准备写入磁盘。

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

并不是每个数据仓库都必定是一个列存储。列存储在迅速普及。

物化汇总

• 数据仓库查询通常涉及一个聚合函数，如SQL中的COUNT，SUM，AVG，MIN或MAX。
• 创建这种缓存的一种方式是物化视图（Materialized View）。

• 物化数据立方体的优点是某些查询变得非常快，因为它们已经被有效地预先计算了。

本章小结

优化 事务处理（OLTP） 或 在线分析（OLAP） 。这些用例的访问模式之间有很大的区别：

• OLTP系统通常面向用户，这意味着系统可能会收到大量的请求。为了处理负载，应用程序通常只访问每个查询中的少部分记录。应用程序使用某种键来请求记录，存储引擎使用索引来查找所请求的键的数据。磁盘寻道时间往往是这里的瓶颈。
• 数据仓库和类似的分析系统会低调一些，因为它们主要由业务分析人员使用，而不是由最终用户使用。它们的查询量要比OLTP系统少得多，但通常每个查询开销高昂，需要在短时间内扫描数百万条记录。磁盘带宽（而不是查找时间）往往是瓶颈，列式存储是这种工作负载越来越流行的解决方案。

在OLTP方面，我们能看到两派主流的存储引擎：
日志结构学派
只允许附加到文件和删除过时的文件，但不会更新已经写入的文件。 Bitcask，SSTables，LSM树，LevelDB，Cassandra，HBase，Lucene等都属于这个类别。
就地更新学派
将磁盘视为一组可以覆写的固定大小的页面。 B树是这种哲学的典范，用在所有主要的关系数据库中和许多非关系型数据库。
日志结构的存储引擎是相对较新的发展。他们的主要想法是，他们系统地将随机访问写入顺序写入磁盘，由于硬盘驱动器和固态硬盘的性能特点，可以实现更高的写入吞吐量。在完成OLTP方面，我们通过一些更复杂的索引结构和为保留所有数据而优化的数据库做了一个简短的介绍。