数据密集型应用系统设计--3.1 数据库核心：数据结构

3.1 数据库核心：数据结构

数据库只需做两件事情：向它插入数据肘，它就保存数据：之后查询时，它应该返回那些数据。

本章我们主要从数据库的角度再来探讨同样的问题，即如何存储输入的数据，井在收到查询请求时，怎样重新找到数据.

了解存储引擎的底层机制。

存储引擎用于大家比较熟悉的两种数据库，即传统的关系数据库和大多数所谓的NoSQL数据库。我们将研究两个存储引擎家族，即日志结构的存储引擎和面向页的存储引擎，比如B-tree 。

一、数据结构

---

世界上最简单的数据库，它由两个Bash函数实现：

echo ” $1,$2”> database

grep “^$1,” database| sed -e "s/^$1", //" | tail -n 1

这两个函数实现了一个key-value存储。当调用 db_set key value ，它将在数据库中保存你所输入的 key和value.

调用 db_get key ，它会查找与输入 key相关联的最新值并返回。

它底层的存储格式其实非常简单：一个纯文本文件。其中每行包含一个key-value对，用逗号分隔（大致像一个csv文件，忽略转义问题）。每次调用db set 即追加新内容到文件末尾，因此，如果多次更新某个键，旧版本的值不会被覆盖，而是需要查看文件中最后一次出现的键来找到最新的值（因此在db_get中使用tail-n1）。

对于简单的情况，追加到文件尾部方式通常足够高效。与db_set相似，许多数据库内部都使用日志（ lo g ），日志是一个仅支持追加式更新的数据文件。

虽然真正的数据库有很多更为复杂问题需要考虑（例如并发控制、回收磁盘空间以控制日志文件大小、处理错误和部分完成写记录等），但是基本的原理是相同的。

每次想查找一个键，db_get必须从头到尾扫描整个数据库文件来查找键的出现位置。在算能术语中，查找的开销是 O(n ）。为了高效地查找数据库中特定键的值，需要新的数据结构：索引。背后的基本想怯都是保留一些额外的元数据，这些元数据作为路标，帮助定位想要的数据。

索引是基于原始数据报生而来的额外数据结构。很多数据库允许单独添加和删除索引，而不影响数据库的内容，它只会影响查询性能。维护额外的结构势必会引入开销，特别是在新数据写入时。对于写人，它很难超过简单地追加文件方式的性能，因为那已经是最简单的写操作了。由于每次写数据时，需要更新索引，因此任何类型的索引通常都会降低写的速度。

涉及存储系统中重要的权衡设计：适当的索引可以加速读取查询，但每个索引者ll会减慢写速度。

1.1 哈希索引

以键－值数据的索引开始。key-value类型并不是唯一可以索引的数据，但它随处可见，而且是其他更复杂索引的基础构造模块。key - value存储与大 多数编程语言所内置的字典结构非常相似，通常采用 hash map （或者 hash table ，哈希表）来实现。

既然已经有了内存数据结构的 hash map ，为什么不用它们在磁盘上直接索引数据呢？

假设数据存储全部采用追加式文件组成，如之前的例子所示 。 那么最简单的索引策略就是 ： 保存内存中的 hash map ，把每个键一一映射到数据文件中特定的字节偏移量 ，这样就可以找到每个值的位置。

每当在文件中追加新的key-value对，更新hash map来反映刚刚写入数据的偏移量 （包括插入新的键和更新已有的键）。 当查找某个值时，使用 hash map来找到文件中的偏移量 ，即存储位置，然后读取其内容.Bitcask(Riak中的默认存储引擎）所采用的核心做法。

只追加到一个文件，那么如何避免最终用尽磁盘空间？

一个好的解决方案是将日志分解成一定大小的段，当文件达到一定大小时就关闭它，井将后续写入到新的段文件中。然后可以在这些段上执行压缩，如图 3-2所示。压缩意味着在日志中丢弃重复的键，并且只保留每个键最近的更新。

每个段现在都有自己的内存哈希表 ，将键映射到文件的偏移量。 为了找到键的值，首先检查最新的段的 h as h map ；如果键不存在，检查第二最新的段，以此类推。由于合并过程可以维持较少的段数量 ，因此查找通常不需要检查很多 hash map

在真正地实现中有以下重要问题：文件格式、删除记录、崩愤恢复、部分写入的记录、并发控制

追加的日志乍看起来似乎很油费空间：为什么不原地更新文件，用新值覆盖旧值？但是，结果证明追加式的设计非常不错，主要原因有以下几个：追加和分段合并主要是顺序写，它通常比随机写入快得多，特别是在旋转式磁性硬盘上。在某种程度上，顺序写入在基于闪存的固态硬盘（ solidstatedrives,SSD ）上也是适合的；如果段文件是追加的或不可变的，并发和崩愤恢复要简单得多；合并旧段可以避免随着时间的推移数据文件出现碎片化的问题。

===SSTable&LSM-Tree===

现在简单地改变段文件的格式：要求key-value对的顺序按键排序。乍一看，这个要求似乎打破了顺序写规则，这种格式称为排序字符串表，或简称为SSTable.以上描述的算怯本质上正是LevelDBlGJ和RocksDB[?J所使用的，类似的存储引擎还被用于Cassa n dra矛口HBase[SJ ，这两个引擎都受到 Google的B i gtab l e论文［9］的启发（它引入了 SSTa bl e和内存表这两个术语）

存储引擎的基本工作流程如下：

1.当写入时，将其添加到内存中的平衡树数据结构中（｛列如红黑树）。这个内存中的树有时被称为内存表。

2.当内存表大于某个闹值（通常为几兆字节）时，将其作为 SSTable文件写入磁盘。由于树已经维护了按键排序的 key-value对，写磁盘可以比较高效。新的SSTable文件成为数据库的最新部分。当 SSTable写磁盘的同时，写入可以继续添加到一个新的内存表实例。

3.为了处理读请求，首先尝试在内存表中查找键，然后是最新的磁盘段文件，接下来是次新的磁盘段文件，以此类推，直到找到目标（或为空）

4.后台进程周期性地执行段合并与压缩过程，以合并多个段文件，并丢弃那些已被覆盖或删除的值。

这个索引结构 由 Patrick 0 ’Nei l等人以日志结构的合井树（ Log-Structured MergeTree ，或LSM-Tree) [IOJ命名，它建立在更早期的日志结构文件系统之上 l 门 l 。因此，基于合井和压缩排序文件原理的存储引擎通常都被称为LSM存储引擎。但LS M-t ree 的基本思想（保存在后台合井的一系列SSTable ）却足够简单有效

===B-tree===

最广泛使用的索引结构是另一种不同的： B-tree,像SSTable一样， B-tree保留按键排序的ke）叫 alue对，这样可以实现高效的key-value查找和区间查询。但相似仅此而已：B-tree本质上具有非常不同的设计理念。

日志结构索引将数据库分解为可变大小的段，通常大小为几兆字节或更大，并且始终按顺序写入段。相比之下， B-tree将数据库分解成固定大小的块或页，传统上大小为4KB（有时更大），页是内部读／写的最小单元。这种设计更接近底层硬件，因为磁盘也是以固定大小的块排列。

每个页面都可以使用地址或位置进行标识，这样可以让一个页面引用另一个页面，类似指针，不过是指向磁盘地址，而不是内存。可以使用这些页面引用来构造一个树状页面.

某一页被指定为 B-tree的根：每当查找索引中的一个键时，总是从这里开始。该页面包含若干个键和对子页的引用。每个孩子都负责一个连续范围内的键，相邻引用之间的键可以指示这些范围之间的边界。

B-tree中一个页所包含的子页引用数量称为分支因子。例如，在图 3-6 中，分支因子为6 。在实际中，分支因素取决于存储页面引用和范围边界所需的空间总量，通常为几百个。

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

===使B-tree可靠

B-tree底层的基本写操作是使用新数据覆盖磁盘上的旧页。它假设覆盖不会改变页的磁盘存储位置，也就是说，当页被覆盖时，对该页的所有引用保持不变。这与日志结构索引（如LSM-tree ）形成鲜明对比， LSM-tree仅追加更新文件（并最终删除过时的文件），但不会修改文件。

Btree索引必须至少写两次数据：一次写入预写日志，－次写入树的页本身（还可能发生页分裂）。即使该页中只有几个字节更改，也必须承受写整个页的开销。

MySQL InnoDB存储引擎中，表的主键始终是聚集索引，二级索引引用主键。

迄今为止讨论的索引只将一个键映射到一个值。如果需要同时查询表的多个列（或文档中的多个字段），那么这是不够的。

最常见的多列索引类型称为级联索引，它通过将一列追加到另一列，将几个字段简单地组合成一个键（索引的定义指定宇段连接的顺序）