这篇文章是ddia第三章的阅读笔记。

0. Pre

数据库的功能简单来说就是两个：

• 插入数据时，数据库保存数据；
• 检索时，数据库返回数据。

很简单，但是为了达成这两个目的，数据库需要做好多事情。

这就是这篇文章所要讲述的东西。

即，数据库底层是如何存储数据的呢？当检索数据的时候，数据库又如何快速找到数据并返回呢？

这就涉及到了数据库的存储引擎（storage engine）。

1. 从hello world开始

既然数据库的功能就是存数据（set）与返回数据（get），那么可以通过下面的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；查询数据：db_get key。

这个最简单的数据库将数据存储在database文件中，新数据添加在文件的末尾，对于一个已有的key更新数据时不覆盖，而是直接添加到末尾。在查询这个key时，返回最后一条记录。

虽然想法很简单，但很多数据库内部都使用类似的日志（log）结构，这就是基于日志的数据库（log-structured database）。

另一种，是基于存储页（page-oriented）的。

2. Using Index

需要从读和写两方面来审视这个最简单的数据库。

由于直接在文件末尾添加数据，所以这个数据库的写操作是最简单的。

随着数据量的增加，对于给定的一个key，需要从头到尾扫描所有的数据来找到这个key的位置，时间复杂度是$O(n)$。

两个极端，需要平衡。这就是索引（index）的功能，提高读操作的性能。

索引其实就是基于数据提取元数据作为数据的路标，帮助数据库快速找到数据。

什么时候提取元数据？最好在插入数据的时候直接就提取了。

这样，加入索引的代价就是写操作性能降低了。

trade-off是计算机中一个重要的思想。我们在计算机相关的设计中经常遇见它。

2.1 Hash Indexes

索引就是地图（map），拿着地图就可以找到目标在哪。

而key-value类型的hash map是大多数编程语言内置的。所以最简单的索引就可以通过这个hash map来实现：

hash map的key就是存储数据的key，value就是对应数据在文件中的位置（偏移值）。

如果把所有key和位置放进内存，这就构成了一个简单的索引系统。

这样即使所有的value内存存不下也没关系，只需要一次磁盘寻址就可以找到它了。

而且如果部分数据加载到内存中，这部分数据根本就不需要读磁盘。

简单但可行，甚至这是Riak默认存储引擎Bitcask的核心做法。

适用场景：每个键的值频繁更新的场景。

2.2 File Gets Bigger Than Bigger

我们是使用一个文件来存储数据的，而且不会删除，只会增加。

这样下去是不行的，首先查询效率低；其次，操作系统也不允许无限大的文件。

咋整？分治吧，一个大文件拆成多个小文件。

由于同一个key后面的比前面的新，前面的就可以删掉了，所以拆成多个的小文件，还可以压缩：

每个小文件压缩之后还可以将多个小文件合并，进一步压缩：

有了多个文件（也就是段，segment）之后，写入没问题，那么查询呢？

每个文件对应一个自己的hash map，放在内存中作为索引。来一个查询，检查最新的段的hash map，如果没有就检查第二个，以此类推。

由于压缩与合并的存在，其实不需要维护很多段。

2.3 More Things to Consider

想法很不错也简单，但还要注意很多细节。

2.3.1 实现细节

file format

我们用的是csv格式。有什么问题吗？当然了，如果数据中包含csv的分隔符（字段分隔符与行分隔符）就炸了。

二进制格式文件是最常用的。

deleting records

那删除操作怎么办？

可以用一个字段来标记一下（也可以叫做墓碑，tombstone），mysql中的DELETE就是这么做的。

如果某条记录已经被删除，日志压缩合并的时候就可以忽略了。

crash recovery

如果数据库重启，那么内存中的hash map就会丢失。

可以重新扫描日志文件来重建索引，但是如果日志量大的话重建过程很慢。

可以将内存中的hash map的快照保存到磁盘中，下次重启就可以直接加载。

Bitcask就是这么做的。

partially written records

如果由于数据库奔溃导致日志出现损坏，可以通过添加校验值来发现。

concurrency control

写日志是严格按照先后顺序写的，通常的实现只有一个写线程。

日志文件是追加的且不可变，所以可以用多个读线程。

2.3.2 优势

想法很简单，但是设计非常不错。优势：

• 追加和分段合并主要是顺序写，通常比随机写快得多；
• 日志文件是追加的或不可变的，那么并发和奔溃恢复就简单得多；
• 日志合并可以避免碎片化问题。

2.3.3 局限

• hash map需要放进内存，如果放不下呢？
• 日志记录是根据时间排序的，区间查询就不太行了。

怎么办？

2.4 SSTables & LSM-Tree

日志结构的存储段都是key-value对的序列，严格根据写入时间排序，同一个key后面的优于前面的，而key的排序不重要。

前面提到了这种结构的一些不足，比如key不够存进内存以及区间查询等情况。

这个时候就需要另一种索引，除了时间顺序外，对key也进行排序。

这就是Sorted String Table，SSTable。

SSTable要求每个键在每个合并段文件中只出现一次（可以在压缩过程中保证）。

2.4.1 合并与索引

既然是日志型数据库，对数据就要进行压缩与合并。由于对key进行了排序，SSTable合并可以更加高效：

同样由于对key进行了排序，我们就可以进行区间查找了。同时，我们也不需要把所有的key都保存在内存中，可以将一部分key作为区间的端点保存在内存中作为索引。结构如下：

2.4.2 SSTable的构建与维护

首先面对的一个问题就是，插入是随机的，怎么维护key的顺序呢？

磁盘上排序可以使用B-tree，但是在内存中更容易，比如各种平衡树，插入的时候就可以维护key的顺序。

既然在内存中排序，那就意味着我们需要在内存中维护部分数据。整体的流程如下：

这个方案基本上可以工作得很好。

不过如果数据写入内存的时候数据库奔溃，导致部分数据没有写入到磁盘中，就会出现问题。

这也好解决，只要在磁盘上维护一个单独的日志，每个写入都立即追加到这个日志即可。

如果发生崩溃，就可以根据这个日志来进行恢复。同时这个日志也不需要按key排序，因为它的目的在于崩溃恢复。

当内存表写入磁盘后，这个日志就可以丢弃了。

2.4.3 Making an LSM-tree out of SSTables

很多数据库比如LevelDB和RocksDB使用了上面描述的这个算法。

这个索引结构最初由Patrick O’Neil等人以日志结构合并树（Log-Structured Merge-Tree，LSM-Tree）命名的。

所以，基于合并和压缩排序文件原理的存储引擎通常都被称为LSM存储引擎。

这也是Elasticsearch和Solr等全文搜索系统的索引引擎Lucene的基础。

此外，还有很多可以考虑的细节。

比如，如果一个key不存在，那么需要遍历所有key所在范围的段才能确定不存在。这时可以使用布隆过滤器。

SSTable压缩和合并也有不同的策略，有大小分级和分层压缩等。

3. B-Tree

日志结构索引之外还有一种截然不同的索引结构：B-Tree。

B-Tree和SSTable唯一相同之处在于也对key进行排序。SSTable使用不同的段来存储数据，而B-Tree是基于页的。

每个页固定大小（通常4KB），是读写的最小单元，这样更接近于底层硬件。

像内存中的指针一样，不同的页之间也可以互相引用。这样就可以构成树形结构：

其中的一页作为整棵树的根节点，每次查询都从它开始遍历。

B-Tree底层的基本写操作是使用新数据来覆盖磁盘上的旧页，这和SSTable只追加不同，覆盖后的页引用可以不变。

如果需要写的数据旧页装不下，那么就会发生页的分裂。分裂后需要更新父节点对这两个子页的引用。

如果部分写入的时候发生崩溃，会导致索引破坏。为了解决这个问题，可以使用预写日志（write-ahead log, WAL），也叫重做日志（redo-log）。

在B-Tree之上的优化：

• 使用写时复制来代替预写日志（LMDB）；
• 保存键的缩略信息，一个页可以保存更多键，降低树的深度；
• 相邻子页顺序保存在磁盘上；
• 添加兄弟页的引用；
• 分形树，减少磁盘寻道。

下面简单比较一下两者的优劣。

简单来说就是，B-Tree读快，LSM-Tree写快。

LSM-Tree在磁盘上顺序写，支持更好地压缩，所以文件通常比B-Tree小，也没有磁盘碎片。由于顺序写，所以写更快。

B-Tree的优点就是，每个键在索引上都有一个唯一对应的位置，这和LSM-Tree是不同的（LSM-Tree一个键可以在多个段中，只要每个段内键唯一即可）。

这样B-Tree就可以提供更强的事务支持。

不过最适用的才是最好的。

4. 其他索引结构

上面介绍的都是key-value索引，就像是关系型数据库中的主键，每个key唯一对应一条记录。

此外，二级索引（secondary index）也很常见，使用二级索引可以高效地执行行联结操作。

不过二级索引对应的值不是唯一的。不过值可以是匹配行的列表，也可以加追一些标识符来使键变成唯一的。

B-Tree和LSM-Tree都支持二级索引。

4.1 value里存什么

key就是键，那value里面存什么呢？两种：

第二种堆文件比较常见，可以避免复制数据。

不过索引到堆文件的跳转会有性能损耗，这样可以在value里直接存所有的数据，这就是聚集索引（clustered index）。

比如在MySQL InnoDB中，主键始终是聚集索引，二级索引引用主键（而不是堆文件）。

在聚集索引和非聚集索引之间，可以有一个折中设计，在value里存放部分值，叫做覆盖索引（covering index）或包含列的索引（index with included columns）。

读取方便那么就会给写入带来麻烦。数据冗余在写入时需要更多工作，不然就会出现不一致的结果。

4.2 多列索引

前面提到的索引都是只有一个值的键。多列索引可以同时查询多个列。

最常见的多列索引是级联索引（concatenated index），只是简单地将多个列组合成一个列（组合的顺序按照索引定义的顺序）。

级联索引的问题是，需要指定组成索引的第一个列之后才能查找第二个列。

多维索引（multi-dimensional index）可以提供多个维度的同时筛选，这对于地理位置等很有用。

不过B-Tree和LSM-Tree不支持多维索引。

4.3 内存数据库

随着内存成本的降低，也可以将所有的数据存储在内存中。

内存数据库的优势并不是因为不需要从磁盘读取。如果内存足够，即使是基于磁盘的存储引擎，也可能不需要从磁盘中读取数据。内存数据库可以更快，是因为它们避免了将内存中的数据编码成磁盘存储格式的开销。

内存数据库可以支持大于内存的数据量。通过反缓存方法，将最近最少使用的数据存入磁盘即可空余出更多的内存空间。

5. Transaction Processing or Analytics？

数据库的使用模式可以分为在线事务处理（online transaction processing, OLTP）和在线分析处理（online analytic processing, OLAP）。两者区别如下：

SQL既可以用来做OLTP，也可以用来做OLAP。不过随着数据量的增加，现在开始使用独立的数据库来做OLAP，叫做数据仓库（data warehouse）。

5.1 Data Warehouse

业务可能会随着时间有越来越多的数据库，这些数据库对各自的业务都很重要，在这只上进行数据分析工作不太现实。

首先是数据隔离。一个统计分析可以涉及到多个数据库，这需要做表join。

其次，分析操作需要扫描大量记录，这对数据库的性能有很大的影响。

所以可以将各个数据库的数据复制一份到另外的地方，来做分析工作。这就是提取-转换-加载（Extract-Transform-Load, ETL）过程：

前面介绍的数据库都不太适合做OLAP，所以需要面向分析优化的存储引擎。

5.2 星型与雪花型分析模型

和事务处理领域广泛使用了多种不同数据模型不同，分析型业务的数据模型很少。

比如星型模型：

模型的中心是一个事实表（fact table），其中的列是属性，还有对其他表的外键，这些被引用的表叫做维度表（dimension tables）。

星型模型的一个变体是雪花模型，其中维度进一步细分为子空间。

数据仓库中的表可能非常宽，上百个列，包含所有分析数据的元数据。

这么宽的表也为分析带来了难度，这时就出现了列式存储。

6. 列式存储

用于数据分析的事实表基本上很宽，数据也很多（巨多行），但是查询的时候只会选择其中的几个列，大多数OLTP数据库中，存储是面向行的，即使选择几列，也要把改行所有的数据取出来。

这样一个直观的改变就是，面向列的存储：

每个列存在一个文件中，查询的时候只要解析使用的列就可以了。

列文件中按照一定的顺序存储行对应字段的数据，如果要获取某一行的话，将所有列对应记录取出来就可以了。

6.1 列压缩

数据库中的列，对应一个属性。而这个属性一般是小于行数的。

所以可以对列进行压缩，来进一步降低对磁盘吞吐量的要求。

对列的压缩可以使用位图编码：

也可以使用游程编码，进一步压缩。

怎么查询呢？

WHERE product_sk IN (30, 68, 69)

可以加载product_sk = 30, product_sk = 68和product_sk = 69三个位图，然后按位或操作即可。

就很神奇。

6.2 列存储的写操作

列存储的特点是可以加速查询，但是写入就更加困难了。

如果在表中插入一列，那么需要更新所有的列文件。不过可以使用类似LSM-Tree的方式，在文件结尾追加。

也可以使用这种方式来进行排序。

6.3 Aggregation: Data Cubes and Materialized Views

数据仓库在做分析的时候使用最多的操作就是聚合，比如SQL中的COUNT, SUM, AVG, MIN或MAX等。

如果聚合操作很多，那一个简单的想法就是，先对原始数据进行聚合，存起来，后面的分析不就可以直接使用了吗？

物化视图（materialized views）就是实现这种缓存的一种方法。

数据库中也有视图的概念，但那只是虚拟的，并没有真正存储数据。

物化视图是写入磁盘的实际结果副本，当底层数据变化时，物化视图也要更新。

物化视图的一个特殊情况是数据立方体（data cube），是由不同维度分组的聚合网格：

这里是两个维度：日期和产品。data cube可以扩展到多个维度，每一条记录都是所有维度的一个组合条件。

优点就是查询快，作为在原始数据上只经过一步处理的数据，可以在此基础上做进一步分析，不需要去重新扫描原始数据。

缺点也很明显，原始数据发生变化，data cube也要变化，显得不太灵活。

面对不同场景的应用，需要使用不同的工具。不同的工具有自己的优劣，了解它们才能更好地使用。