存储与索引

本章介绍了传统关系型数据库与“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 函数对于极其简单的场景其实有非常好的性能，因为在文件尾部追加写入通常是非常高效的。许多数据库在内部使用了日志（log），原理和db_set类似也就是一个 仅追加（append-only） 的数据文件（比如Kafka的存储和Cassandra、ES）。
缺点：如果这个数据库数据量比较大，则这个db_get 函数的查询性能会非常糟糕。每次你想查找一个键时，db_get 必须从头到尾扫描整个数据库文件来查找键的出现，时间复杂度为 O(n)。
所以为了在这种情况下能够高效的查询，所以我们需要一个新的数据结构：索引来解决

索引（Index）

索引是从主数据衍生的附加（additional）结构，索引不会影响数据的内容只影响查询和写入性能。任何类型的索引通常都会减慢写入速度，因为每次写入数据时都需要更新索引，同时索引的引入也会加速查询的速度，所以这是存储系统中一个重要的权衡：精心选择的索引加快了读查询的速度，但是每个索引都会拖慢写入速度。

哈希索引

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

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

新增：新的键值写入文件时，还要更新散列映射。
编辑：编辑时不会更改原有的内容而是插入新的值，更改映射
查询：使用哈希映射来查找数据文件中的偏移量，通过磁盘 Seek 该位置并读取该值
删除：建立墓碑机制，后续处理
Bitcask（参考链接）的实现就是这样，非常适合每个键的值频繁更新的情况。（有一些不理解需要后续再看下这个）
每次操作都是对这个文件得追加，有很多数据都是重复的（例如删除了编辑过都是追加），为了防止磁盘用完，大多数会采用分段的机制将日志分为特定大小的段，当日志增长到特定尺寸时关闭当前段文件，并开始写入一个新的段文件。然后，我们就可以对这些段进行压缩（compaction），压缩意味着在日志中丢弃重复的键，只保留每个键的最近更新，并且删除墓碑键值对。

压缩后段过小：由于压缩后一个段可能变得很小，所以也可以在压缩的时候把多个段的内容压缩合并到一起，由于段被写入后永远不会被修改，所以合并的段被写入一个新的文件。
压缩合并时支持查询：为了去支持压缩合并的时候还能够继续支持查询，所以冻结段的合并和压缩可以在后台线程中完成。
在合并完了之后我们将读取请求转换为使用新的合并段而不是旧段 —— 然后可以简单地删除旧的段文件。
每个段都有自己的内存散列表，将键映射到文件偏移量。查找键时依次遍历所有的散列表。

如此设计需要考虑的几个问题：
文件格式
csv 不好，使用二进制格式更快。
删除记录
删除一个键值对，则必须在数据文件（有时称为逻辑删除）中附加一个特殊的删除记录（墓碑机制）。然后当日志段被合并时，逻辑删除告诉合并过程放弃删除键的任何以前的值。
崩溃恢复
之前说的散列表都是在内存里的，原则上可以通过重放来恢复散列表，这将会导致耗时很长，可以通过对散列表做快照，使他能够更快的加载到内存中
部分写入记录
数据库可能随时崩溃，包括将记录附加到日志中途。Bitcask文件包含校验和，允许检测和忽略日志的这些损坏部分。
并发控制
写操作是以严格顺序的顺序附加到日志中的，所以常见的方法是只有一个写线程（Redis）。读操作可以有多个线程同时读取。

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

追加和分段合并是顺序写入操作，通常比随机写入快得多，尤其是在磁盘旋转硬盘上。在某种程度上，顺序写入在基于闪存的 固态硬盘（SSD） 上也是优选的（这个我持怀疑态度）。
如果段文件是附加的或不可变的，并发和崩溃恢复就简单多了，您不必担心在覆盖值时发生崩溃的情况，而将包含旧值和新值的一部分的文件保留在一起
合并旧段可以避免数据文件随着时间的推移而分散的问题。

哈希表索引的局限性：

散列表必须全部放进内存：当有很多键的时候，Hash 冲突处理逻辑复杂，大量的随机IO（个人理解说的应该是随机IO 无法利用CPU三级缓存）
范围查询效率不高：不支持查一个取值区间内的所有键，只能逐个查询

SSTables和LSM树

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

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

合并段是简单而高效的，即使文件大于可用内存。方法类似于归并排序。合并时查看每个文件中的第一个键，复制最低键（根据排序顺序）到输出文件，并重复这个步骤。这产生一个新的合并段文件，也按键排序。当出现重复的Key 则保留最近的
为了在文件中找到一个特定的键，你不再需要保存内存中所有键的索引。因为是有序的，可以先查找出键所处的范围，然后就找到这个键所在的偏移量的区间。比如查询handiwork时，可以从 handbag 和 handsome 的偏移量找到 handiwork 的区间。然后再这个区间查找

构建和维护SSTables

现在比如B树、红黑树、AVL树都是SSTables的一种，使用这些数据结构，您可以按任何顺序插入键，并按排序顺序读取它们。
存储引擎工作：

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

如何解决数据库崩溃，则最近的写入（在内存表中，但尚未写入磁盘）将丢失的问题？
我们可以在磁盘上保存一个单独的日志，每个写入都会立即被附加到磁盘上，该日志不是按排序顺序，但这并不重要，因为它的唯一目的是在崩溃后恢复内存表。每当内存表写出到SSTable时，相应的日志都可以被丢弃。

用 SSTables 到 LSM树（Log-Structured Merge-Tree）

上面讲的算法，就是现在的LSM存储引擎的大致实现，在 LevelDB 和 RocksDB 使用。Cassandra和Hbase、ES中也使用了类似的方法

性能优化

查询效率：当查找数据库中不存在的键时，LSM-Tree算法可能很慢：在确定键不存在之前，必须先检查内存表，然后将段一直回溯访问到最旧的段文件（可能必须从磁盘多次读取），然后才能确定键不存在。你可以使用布隆过滤器，来实现过滤
压缩合并的顺序和时间：
还有不同的策略会影响甚至决定SSTables压缩和合并时的具体顺序和时机，LevelDB和RocksDB使用分层压缩

LevelDB和RocksDB使用分层压缩：键的范围分裂成多个更小得SSTables, 旧数据被移动到单独的＂层级” ，这样压缩可以逐步进行并节省磁盘空间
HBase 使用大小分级，较新的和较小的SSTables被连续合并到较旧和较大的SSTables
Cassandra 同时支持。

即使有许多细微的差异，但LSM-tree的基本思想（保存在后台合并的一系列SSTable)却足够简单有效。即使数据集远远大千可用内存，它仍然能够正常工作。由千数据按排序存储，因此可以有效地执行区间查询（从最小值到最大值扫描所有的键），并且由千磁盘是顺序写入的，所以LSM-tree可以支持非常高的写入吞吐量。

B树

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

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

查询过程：

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

更新过程：

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

插入过程：

找到其范围包含新键的页面，并将其添加到该页面。
如果页面中没有足够的可用空间容纳新键，则将其分成两个半满页面，并且父页也需要更新以包含分裂之后的新的键范围

该算法确保树保持平衡：具有n个键的B-tree总是具有0 (log n)的深度。大多数数据库可以适合3~4层的B-tree, 因此不需要遍历非常深的页面层次即可找到所需的页（分支因子为500的4KB页的四级树可以存储高达256 TB)。

让B树更可靠

覆盖操作底层逻辑复杂

因为 B 树的基本底层写操作是用新数据覆盖磁盘上的页面，假设的是覆盖不改变页面的位置，而日志结构索引（如LSM树）只附加到文件（并最终删除过时的文件），但从不修改文件，而磁盘的覆盖操作必追加复杂的
某些操作需要覆盖多个不同的页。例如插入导致页溢出，需要分裂页，并更新父页对两个新子页的引用，这不是一个原子操作，因为如果数据库在完成部分页写入之后发生崩溃，最终会导致索引破坏

总之覆盖操作实现上比较复杂，需要一些手段来使数据库能从崩溃中恢复，B-tree使用了以下手段
预写式日志（WAL）
为了使数据库对崩溃具有韧性，B树实现通常会带有一个额外的磁盘数据结构：预写式日志（WAL, write-ahead-log）（也称为重做日志（redo log））。这是一个仅追加的文件，每个B树修改都可以应用到树本身的页面上。当数据库在崩溃后恢复时，这个日志被用来使B树恢复到一致的状态.
并发访问
更新页面时，如果多个线程要同时访问B树，则需要仔细的并发控制，否则可能会看到树处于不一致的状态。通过使用锁存器（latches）（轻量级锁）保护树的数据结构来完成，而 LSM 比较简单：在后台完成所有的合并，不干扰查询；通过「原子交换」把旧的分段变为新的分段。

B树优化

多线程访问优化

LMDB 数据库中使用「写时复制方案」，而不是不是覆盖页面并维护 WAL 进行崩溃恢复：修改的页面被写入到不同的位置，并且树中的父页面的新版本被创建，指向新的位置。这种方法对于并发控制也很有用。（例如Mysql的MVVC）

减少索引层次

保存键的缩略信息，而不是完整的键：键只用保存一个区间，而不是具体的数值（类似于 B+树）。可以包含更多的键，减少树的层次。

更快速的范围查询

许多B树实现尝试布局树，使得叶子页面按顺序出现在磁盘上。但是随着树的增长，维持这个顺序是很困难的。相比之下，由于LSM树在在合并过程中一次重写大批存储段，因此它们更容易让连续的键在磁盘更为靠近

支持更快的扫描

额外的指针已添加到树中：例如，每个叶子页面可以在左边和右边具有对其兄弟页面的引用，这允许不跳回父页面就能顺序扫描。

B树的变体如分形树借用一些日志结构的思想来减少磁盘寻道（而且它们与分形无关）。

比较B树和LSM树

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

LSM树的优点

写入性能好

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

高吞吐量

B树会有写放大问题（一次写入请求带来多次磁盘写）存储引擎写入磁盘的次数越多，可用磁盘带宽中每秒可以处理的写入越少。同时由于LSM 是循序写入紧凑的SSTable文件，而不必重写树中的多个页，所以有更高的吞吐

低磁盘碎片

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

LSM树的缺点

压缩带来的不确定性
1. 日志结构存储的缺点是压缩过程有时会干扰正在进行的读写操作，而B树的响应延迟则则相对更具可预测性。
2. 字段的写入带宽和后台的压缩线程共享，如果写入吞吐量很高并且压缩没有仔细配置，那么就会发生压缩无法匹配新数据写入速率的情况。磁盘上未合并段的数量不断增加，直到磁盘空间不足，由于它们需要检查更多的段文件，因此读取速度也会降低。
没有强大的事务支持

其他索引结构

前面讨论的是Key-Value 索引，它们就像关系模型中的主键（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 树**。多维索引，可以用于很多地方：电子网站、天气数据、地理位置查询，主要是多个列查询。

全文搜索和模糊索引

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

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

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

在内存中存储一切

对于磁盘和SSD，如果要在读取和写入时获得良好性能，则需要仔细地布置磁盘上的数据。
磁盘优点：数据保存持久化，耐用，成本低。
内存变得便宜，促进了内存数据库发展。
内存数据库通常用于缓存，也可以支持通过将更改日志写入磁盘，将定时快照写入磁盘或通过复制内存来实现，记忆状态到其他机器。
实现

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

常见产品

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

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

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

除了性能还有什么优势？

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

内存不够用怎么办？

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

标签：存储,写入,索引,内存,磁盘,日志,页面
From： https://www.cnblogs.com/xxpdebug/p/17653021.html