存储与检索

数据库核心:数据结构

世界上最简单的数据库可以用两个Bash函数实现：

#!/bin/bash
db_set () {
    echo "$1,$2" >> database
}

db_get () {        
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

底层的存储格式：

1. 一个文本文件，每行包含一条逗号分隔的键值对（忽略转义问题的话，大致与CSV文件类似）。
2. 每次对 db_set 的调用都会向文件末尾追加记录，所以更新键的时候旧版本的值不会被覆盖。
3. 查找最新值的时候，需要找到文件中键最后一次出现的位置（因此 db_get 中使用了 tail -n 1 。)

db_set 函数对于极其简单的场景其实有非常好的性能，因为在文件尾部追加写入通常是非常高效的。 与db_set做的事情类似，许多数据库在内部使用了日志（log），也就是一个 仅追加（append-only） 的数据文件

另一方面，如果这个数据库中有着大量记录，则这个db_get 函数的性能会非常糟糕。每次你想查找一个键时，db_get 必须从头到尾扫描整个数据库文件来查找键的出现。用算法的语言来说，查找的开销是 O(n) ：如果数据库记录数量 n 翻了一倍，查找时间也要翻一倍

索引

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

哈希索引

键值存储与在大多数编程语言中可以找到的字典（dictionary）类型非常相似，通常字典都是用散列映射（hash map）（或哈希表（hash table））实现的。
保留一个内存中的哈希映射，其中每个键都映射到一个数据文件中的字节偏移量，指明了可以找到对应值的位置

以类CSV格式存储键值对的日志，并使用内存哈希映射进行索引

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

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

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

压缩键值更新日志，只保留每个键的最近值

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

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

同时执行压缩和分段合并

一些真正实施中重要的问题是

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

为什么不更新文件，用新值覆盖旧值？但是只能追加设计的原因有几个：

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

哈希表索引也有局限性：

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

SSTables和LSM树

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

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

1. 合并段是简单而高效的，即使文件大于可用内存。方法类似于归并排序。
   如果在几个输入段中出现相同的键，该怎么办？保留最近段的值，并丢弃旧段中的值。

   
   合并几个SSTable段，只保留每个键的最新值

2. 为了在文件中找到一个特定的键，你不再需要保存内存中所有键的索引。假设你正在内存中寻找键 handiwork，但是你不知道段文件中该关键字的确切偏移量。然而，你知道 handbag 和 handsome 的偏移，而且由于排序特性，你知道 handiwork 必须出现在这两者之间。这意味着您可以跳到 handbag 的偏移位置并从那里扫描，直到您找到 handiwork（或没找到，如果该文件中没有该键）
   

   具有内存索引的SSTable

构建和维护SSTables
如何让数据首先被按键排序呢？在内存中排序简单的多，比如红黑树、AVL 树

存储工作的操作步骤：

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

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

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

用SSTables制作LSM树
LSM 树：在 LevelDB 和 RocksDB 使用

性能优化

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

B树

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

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

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

使用B树索引查找一个键

查找过程：

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

更新过程：

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

插入过程：

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

通过分割页面来生长B树

删除过程：

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

深度：

1. 该算法确保树保持平衡：具有 n 个键的B树总是具有 的深度。
2. 大多数数据库可以放入一个三到四层的 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树的变体如分形树借用一些日志结构的思想来减少磁盘寻道（而且它们与分形无关）。

比较树和LSM树

什么是LSM树（日志结构合并树）

其他索引结构

将值存储在索引中

1. 聚集索引（clustered index）
2. 非聚集索引（nonclustered index）
   多列索引

全文搜索和模糊索引

在内存中存储一切

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

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

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

事务处理还是分析处理？

比较交易处理和分析系统的特点

数据仓库

OLTP系统往往对业务运作至关重要，因而通常会要求 高可用 与 低延迟。所以DBA会密切关注他们的OLTP数据库，他们通常不愿意让业务分析人员在OLTP数据库上运行临时分析查询，因为这些查询通常开销巨大，会扫描大部分数据集，这会损害同时执行的事务的性能。

相比之下，数据仓库是一个独立的数据库，分析人员可以查询他们想要的内容而不影响OLTP操作

ETL至数据仓库的简化提纲

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

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

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

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

列存储

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

使用列存储关系型数据，而不是行

列压缩

压缩位图索引存储布局

内存带宽和向量处理

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

列存储中的排序顺序

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

解决方案：LSM树。
● 现在内存中存储，添加到一个已排序的结构中，然后准备写入磁盘。

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