DDIA 读书笔记（2）数据模型的存储与检索

大部分应用都是基于数据模型一层层封装诞生的，每一层的数据模型都是基于低一层的数据模型实现。程序员对业务模型进行抽象，构建数据模型，CRUD 的 API。并将数据模型转化为数据库 （SQL 或 NoSQL ）的通用结构并存储。而数据库则将自己的通用数据模型转化为磁盘上的字节流，中间还包含着基础数据结构的封装等。



不同的数据模型有各自的优劣，有的查询很快，有的新增很快，需要根据不同的业务场景选择合适的数据模型

关系模型与文档模型

关系数据库称霸了整个行业二三十年，期间也出现过其他的竞争对手，像网络模型、层次模型之类的，但最终都消磨在历史的尘埃当中，唯有关系数据库一直在随着时代不断地发展，并应用在了各种各样的领域。



进入 21 世纪后，新的竞争者 NoSQL 诞生了，经过一段时间的传播和曲解，现在基本成了非关系数据库的统称（Not Only SQL）。NoSQL 受欢迎的原因是因为它解决了 SQL 的数据库的一些痛点，比如超大数据量或是超高吞吐量，或是具有 SQL 无法匹及的灵活性。



文档数据库可以更好的展现业务模型，就像一份简历，上面会有姓名学校公司等，就是天生的一份文档，很容易就可以用 JSON 来表示其结构以及嵌套关系，如果使用 SQL 去存储，就需要定义很多的表，还需要整理表与表之间的关联。事实上为了方便存储和查询，开发人员会尝试将非索引字段也变成 json 并存储为表中的一个字段，也算是兼顾了文档模型与关系模型。



关系模型仍然保持着自己的优势，所有的表都是字段集合，没有复杂的嵌套结构，也不会有复杂的访问路径，我们可以通过任意条件来查询任意字段。而且 SQL 是一种声明式语言，我们只需要描述自己想要获取的数据，如何查询，怎么走索引，都可以交给优化器去做，大大解放了开发人员的心智负担。查询优化器经过了多年的发展，已经变得非常复杂，同时也算是一种壁垒，是其他数据库难以超越的。



虽然文档模式的灵活性被很多人称赞，但是其本质是把数据校验的活交给了应用层去实现，应用层在写入和读取是都需要去校验数据，唯一的好处大概是加字段的0成本吧，关系型的大表想要加字段都是伤筋动骨的操作。

数据存储与检索

OLTP 与 OLAP

早期数据库只是用来处理应用在线交互流程，根据用户的输入来插入或更新记录，或是通过指定的 key 查询少量数据，这类访问模式被称为在线事务处理（online transaction processing，OLTP）。



后来，随着数据量的增大，数据库也需要用来进行数据分析，它和传统的访问方式有很大的不同，数据分析通常需要读取大量的记录（GB 甚至 TB）,并取记录里少量几列进行计算并展示结果，这个结果是面向企业内部人员而不是用户，用来辅助业务决策，它对数据的时性要求没有传统方式那么高，因此新的数据通常也是批量写入。这类的模式称为在线分析处理（online analytic process，OLAP）。



早期 OLTP 和 OLAP 都是使用同一个数据库，SQL 足够灵活，可以同时胜任两种工作模式，但随着在线业务的增长，OLAP 的大量读取记录的特点很容易影响到 OLTP 业务的稳定性，因此 OLAP 业务大多都会迁移到单独的数据上进行工作，这个单独的数据库被称为数据仓库。



随着 OLTP 与 OLAP 分家，为了更好的满足业务需求，两者使用的数据模型虽然都是 SQL，但内部存储细节的实现已经完全不同，需要分开讨论。



OLTP 存储引擎

日志结构存储 SSTable 和 LSM-Tree

假设数据库的功能是简单地存取 KV 对，key 和 value 都是字节序列。



一个普通的日志结构存储方案是在写入时追加到文件末尾，读取时则扫描整个文件，取最后一个匹配的 key。这个方案有着世界最快的写入速度，毕竟除了简单的追加啥都没干，但是读取的时间复杂度是 O(n)。这种仅支持追加式更新的文件和日志非常相似，所以称之为日志结构。



接下来有两个问题



1. 是读取效率太低不可接受。为了提高读取效率，我们需要加上索引，也是怎么简单怎么来，直接在内存保存每个 key 对应的磁盘偏移量。

2. 追加式更新会导致文件越来越大，磁盘不够用。一个解决方案是将文件分段，当文件到达一定大小时就封存它，再开个新的文件进行写入。因为旧文件不会再有写入，我们可以再开个进程去压缩它（根据 key 去重），压缩之后代替旧文件进行读写即可。每个文件都有自己的内存索引，因此读取时也需要查询多个文件。



目前的哈希索引还有有很多限制，放内存里放不下多少，放磁盘上随机读不友好，而且不支持区间查询。让我们继续进行改造。



如果要做区间查询，就必须期望key是按照顺序排列的，这样才能顺序读取而不影响效率。在磁盘上维护排序结构会很复杂，我们把最新的文件段放在内存中，使用红黑树或者 AVL 树来保持 key 的顺序，当文件段到达一定大小或一定的时间就持久化到磁盘上。这样做的好处很明显

• 合并压缩磁盘上的文件段会变的更加简单高效，哪怕文件段比内存大，也可以用归并排序的办法去重。

• 索引不需要再记录每个 key 的偏移量，可以稀疏一些。（即使不知道某个 key 的确切偏移量，可以通过二分查找迅速定位）

• 最新的文件段在持久化之前可以进行压缩，节省磁盘空间，降低 IO。



还有一个小问题，假如数据库崩溃，内存中的文件段会丢失。因此还需要保留单独的日志文件，每一个写入都需要追加日志，用于崩溃后的恢复。



最后总结一下整个工作流程：

• 当有数据写入时，数据会被添加到内存中的平衡树（内存表）。

• 当内存表大于某个阀值或是超过某个时长未持久化时，将其作为文件写进磁盘中，同时开新的内存表来写心得数据。

• 处理读请求时，先查找内存表，然后按时间倒序查找磁盘段文件。

• 后台进程周期性地执行合并和压缩工作。

-

这种有序的文件结构就是 SSTable。基于这种 SSTable 建立的索引结构称之为 LSM-Tree

原地更新的 B-Tree

B-Tree 是另一种更流行的索引结构，几乎应用于所有的关系型数据库中。



相比于 LSM-Tree 会将数据库分解成几兆大小的块，B-Tree 分的更细，一块只有数 KB 大小，称为页。页是内部读写的最小单元，这种结构与磁盘本身的结构极为相似，因此非常适合用来存储数据。

[image:FA9944AF-0D3A-45F1-BC80-44851E2D8BD7-1231-00005909E6F6EBA6/Attachment.jpeg]

在 B-Tree 中，每一个页都是一个节点，除了叶子节点外，其他节点都会包含一定数量的键，键之间会有指针指向下一层节点，即键的范围所代表的索引节点。直到叶子节点获取真正的值（这个值可以是实际的数据，也可以是其他索引的指针）。当有数据写入时，首先搜索包含对应键的叶子节点，然后更新并写回磁盘。如果是新增键，而页中空间不够，该页就会被分裂成两个半满的列。



B-Tree 通过控制一个节点的子节点数量（分支因子）来控制它的深度，因此查询操作至多遍历3到4层就能获取结果。



针对数据库崩溃的情况，B-Tree 的做法是预写日志（write-ahead log，WAL），也叫重做日志。每次数据修改都需要先写 WAL 然后再更新数据。



B-Tree 和 LSM-Tree 的对比

LSM-Tree 能够承受更高的写入吞吐量，原因在于它可以将 SSTable 压缩并顺序写入磁盘，而不必重写树中的页。这样工作模式也会具有较低的写放大，缺点则是读的开销会相对较大，而且后台运行的压缩进程会影响到主线程，需要一定的控制。



B-Tree 的深度控制决定了它的读开销相对稳定，而且数据更新是直接作用在页上，因此可以实现非常强大的事务隔离机制。缺点是写开销有时过大（分裂页，合并页），且磁盘碎片过多。



索引中的值

上面说的索引的值是一个文件的偏移量，这依赖于数据的顺序存储。而索引也可以存储其他地方行的引用，存储的具体位置被称为堆，而不是依赖于特定的顺序。使用堆的好处是更新值会非常高效，而且建立多个索引时可以避免复制数据。



有些情况下从索引到堆的额外跳转会让读开销过大，因此可以将数据直接存储在索引里，这样的索引被称为聚集索引，比如 mysql 的主键。二级索引直接聚集索引。



内存数据库

随着内存的价格下降，纯内存的数据库也发展起来了。得益于内存存储自由度，内存数据库可以实现各种各样的数据结构。反直觉的一点是，内存数据库的性能优势并不是免除了磁盘 IO，因此磁盘数据库也是有内存缓存的。内存数据库真正避免了的是用写磁盘的格式对数据进行编码的开销。



另外虽然内存是易失性存储，但也会有各种各样的手段去持久化内存中的数据以便崩溃后恢复，比如内存快照，记录日志等。

针对 OLAP 的列式存储

数据仓库的表通常会有很多列（大于 100），而每次访问通常只需要取其中的几列，按照传统的行式存储会有极大的性能浪费。反而是列式存储会很合适。



列式存储依赖于一组文件，每个文件都存储着一列的所有值，查询时指定了哪些列，就只需要单独去读取特定文件即可。而且同一列的数据通常重复度极高，有些列甚至只是枚举值，因此列式存储的压缩效率也高得可怕。



由于列示存储的特性，给数据库建立索引是需要冗余的，单独给一个文件排序没有意义，需要给所有文件一起排序，而索引存储的值就只能是包含值的列，而不能是指向别处的指针。



总结

本节讲述了数据模型的概念以及不同存储引擎的简单原理



目前主流的数据模型是关系模型和文档模型。关系模型有成熟的声明式 DDL，简单的存储模型，虽然开发时会有一定的约束，但也会解放维护人员的心智负担；文档模型有着足够的灵活度，也意味着开发复杂度更高，数据格式的校验并没有被消除，而是转移到了应用层，好处是数据模型与业务模型相似，可以灵活表达各种嵌套关系；



存储引擎分为两大类，针对事务处理（OLTP）优化的架构和针对数据分析（OLAP）优化的架构。OLTP 面向用户，对数据实时性要求高，需要承接大量请求，每次请求只读取少量数据；OLAP 面向企业内部人员，请求少，但一次请求的数据量极大，对磁盘带宽和性能是巨大的挑战。



OLTP 主要有两个流派的存储引擎：

• 日志结构流派，它只允许追加式更新文件以及删除过是的文件，而不允许修改文件。写入效率高，读取效率低。

• 原地更新流派，将磁盘划分为无数固定大小的页，每次更新都会更改页。B-Tree 则是典型代表。

OLAP 需要重点考虑大数量的存储和读写，因此列式存储反而更加合适。