第一部分 存储引擎
如果你正在找寻一个非常适合当下（或者未来）的工作负载的数据库，那么你所能做的最好的事情就是在不同的数据库系统上模拟这些工作负载、测量对你很重要的那些性能指标，并比较结果。
有些问题（特别是性能和可伸缩性方面的问题）只有在一段时间后或随着容量的增长才会开始显现出来。为了发现潜在的问题，最好在尽可能接近真实生产环境的环境中进行长期的运行测试。
TPC-C 基准：该基准关注的是执行的并发事务的性能和正确性。主要性能指标是吞吐量：数据库系统每分钟能够处理的事务数。其需要执行事务具备ACID属性并符合基准本身定义的属性集。
第1章 简介与概述
一般将数据库分为三大类:
- 联机事务处理(OLTP)数据库: 它处理大量面向用户的请求和事务。查询通常是预定义的，并且运行时间都很短。
- 联机分析处理(OLAP)数据库它处理复杂的聚合。OLAP数据库通常用于分析和数据仓库，能够处理复杂的、长时间运行的ad-hoc查询。
- 混合事务和分析处理(HTAP)数据库它结合了OLTP和OLAP存储的属性。
1.1 数据库架构
数据库使用客户端/服务器模型，其中数据库系统实例（节点）扮演服务器的角色，而应用程序实例则扮演客户端的角色。
查询解释器对该查询进行语法解析、解释和验证。数据库将执行访问控制检查。
解析后的查询被传递给查询优化器，后者首先消除查询中不可能执行的部分与冗余的部分，然后根据内部统计信息（索引基数、近似交集大小等）和数据分布（数据存储在集群中的哪些节点以及传输所需的成本），尝试找到执行查询的最高效方法。优化器既处理查询解析所需的关系操作（通常表示为依赖关系树），也处理查询优化（如索引排序、基数估计和访问方法的选择）。
事务管理器调度事务，并确保它们不会使数据库处于逻辑不一致的状态。
锁管理器为正在运行的事务锁定数据库对象，确保并发操作不会破坏物理数据的完整性。事务管理器和锁管理器共同负责并发控制：它们在保证数据的逻辑和物理完整性的同时，确保尽可能高效地执行并发操作。
访问方法（存储结构）管理磁盘上的数据访问并负责组织磁盘上的数据。访问方法包括堆文件和存储结构，例如B树和LSM树。
缓冲区管理器将数据页缓存在内存中。
恢复管理器维护操作日志并在出现故障时还原系统状态。
1.2 内存数据库与磁盘数据库
数据库系统将数据存储在内存和磁盘上。
内存数据库（有时称为主存数据库(main memory DBMS)）主要将数据储存在内存中，并使用磁盘进行数据恢复和日志记录。
数据库使用内存作为主要数据存储的主要原因是性能、相对较低的访问成本以及访问粒度。基于内存的编程也比基于磁盘的编程简单得多。操作系统抽象了内存管理，允许我们从分配和释放任意大小的内存块的角度进行思考。而在磁盘上，我们必须手动管理数据引用、序列化格式、释放的空间和碎片。
数据库在认定操作完成之前，必须先将其结果写入一个顺序日志文件。为了避免在启动过程中或崩溃后重放完整的日志内容，内存数据库维护了一个备份副本，该备份副本使用一个基于磁盘且已排序的数据结构，并且对该结构的修改通常是异步（与客户端请求解耦）且分批处理的，这样可以减少I/O操作的数量。在恢复过程中，数据库可以从备份和日志中还原数据库内容。
一些说法认为内存数据库相当于一个具有巨大页缓存的磁盘数据库，这是不公平的。即使页缓存在内存里，序列化格式和数据布局也会使磁盘数据库产生额外的开销，而不会达到与内存数据库相同的优化程度。
磁盘数据库则将大部分数据保存在磁盘上，并使用内存来缓存磁盘内容或作为临时存储。
磁盘数据库使用专门的存储结构，针对磁盘访问进行了优化。在内存中，我们可以比较快地跟踪指针，并且随机内存访问比随机磁盘访问要快得多。基于磁盘的存储结构通常具有宽树和矮树的形式，而基于内存的实现可以从更大范围的数据结构中进行选择，并实现不可能或难以在磁盘上实现的优化。同样，处理磁盘上的可变大小数据需要特别注意，而在内存中，这通常是一个用指针来引用值的问题。
1.3 面向列与面向行的数据库
表可以水平分区（将属于同一行的值存储在一起），也可以垂直分区（将属于同一列的值存储在一起）。
面向行的数据库的例子很多：MySQL、PostgreSQL和大多数传统的关系数据库。而两个开源的、面向列数据存储的先驱则是MonetDB和C-Store。
1.3.1 面向行的数据布局
适用于如下的场景：数据记录（姓名、出生日期和电话号码）由多个字段组成且由某个键所唯一标识。表示单个用户的数据记录的所有字段通常被一起读取。
将整行存储在一起可以提高空间局部性。因为诸如磁盘之类的持久性介质上的数据通常是按块访问的（换句话说，磁盘访问的最小单位是块），所以单个块可能将包含某行中所有列的数据。这对于我们希望访问整个用户记录的情况非常有用，但这样的存储布局会使访问多个用户记录某个字段的查询（例如，只获取电话号码的查询）开销更大，因为其他字段的数据在这个过程中也会被读入。
1.3.2 面向列的数据布局
面向列的存储非常适合计算聚合的分析型工作负载，例如查找趋势、计算平均值等。
在一次读取中，从同一列中读取多个值可以显著提高缓存利用率和计算效率。在现代CPU上，向量化指令可以使单条CPU指令一次处理多个数据点。
另外，将具有相同数据类型的值存储在一起（例如，数字与数字在一起，字符串与字符串在一起）可以提高压缩率。
我们可以根据不同的数据类型使用不同的压缩算法，并为每种情况选择最有效的压缩方法。要决定是使用面向列还是面向行的存储，你需要了解访问模式。
1.3.4 宽列式存储
宽列式存储中，数据表示为多维映射，列被分组为列族（通常存储相同类型的数据），并且在每个列族中，数据被逐行存储。
一个WebTable存储着一个带有某个时间戳、包含如下信息的快照：网页内容、属性以及它们之间的关系。页面由反向URL所标识，并且所有属性（如页面内容和锚，锚表示页面之间的链接）由生成这些快照的时间戳来标识。如下图所示：
数据存储在具有层次索引的多维排序映射中：我们可以通过特定网页的反向URL来定位与该网页相关的数据，也可以通过时间戳来定位该网页的内容或锚。每一行都按其行键进行索引。
在列族中，相关列被分组在一起（在本例中为contents和anchor），这些列族分别存储在磁盘上。列族中的每个列都由列键标识，该键是列族名称和限定符（在本例中为html，cnnsi.com，my.look.ca）的组合。
列族可以按照时间戳存储多个版本的数据。这种布局使得我们可以快速定位更高层的条目（在本例中为Web页面）及其参数（不同版本的内容和指向其他页面的链接）。
1.4 数据文件和索引文件
数据文件存储数据记录，而索引文件存储元数据并使用它来定位数据文件中的记录。
索引文件的大小通常比数据文件小。文件被划分成页(page)，每个页通常具有单个或多个磁盘块的大小。
页可以被组织成记录的序列或分槽页(slotted page)
1.4.1 数据文件
数据文件通常可以用索引组织表、堆组织表或哈希组织表来实现。
在堆文件中的记录不需要遵循任何特定的顺序，并且大多数情况下它们都是按写顺序放置的。这样，在追加新的页时，数据库便不需要额外的工作或文件重组。
1.4.2 索引文件
索引文件被组织成专门的结构，将键映射到数据文件里的记录。主索引是在主键或作为主键的一组键之上构建的。所有其他索引都称为二级索引(secondary index)。
聚簇索引（Clustered Index）
- 定义
数据行的物理存储顺序与索引顺序完全一致，索引的叶子节点直接存储数据行本身。 - 特点
- 一张表只能有一个聚簇索引（因为数据只能按一种物理顺序存储）。
- 主键默认是聚簇索引（例如 MySQL 的 InnoDB 引擎）。
- 范围查询效率高：相邻数据物理上连续存储，适合
BETWEEN、ORDER BY等操作。 - 插入/更新代价高：如果插入的数据打乱原有顺序，可能触发数据页分裂。
非聚簇索引（Non-Clustered Index）
- 定义
索引的叶子节点不存储实际数据行，而是存储指向数据行的指针（如数据行的物理地址）。 - 特点
- 一张表可以有多个非聚簇索引。
- 查询需要“回表”：通过索引找到指针后，需额外读取磁盘获取完整数据。
- 适合精确查找：对单条记录的查询效率高，但范围查询性能弱于聚簇索引。
- 存储开销更大：索引和数据分开存储，占用更多空间。
索引组织表以索引的顺序保存数据，因此按定义一定是聚簇的。主索引通常是聚簇的，而根据定义，二级索引一定不是聚簇的，因为它们是用于加速主键以外的键的访问的。聚簇索引既可以是索引组织的，也可以具有单独的索引和数据文件。
在未指定主键的情况下，存储引擎可以创建一个隐式主键（例如，MySQL InnoDB引擎会自动添加新的自增列并填充该列的值）。
1.4.3 间接的主索引
通过直接引用数据，我们可以减少查找磁盘的次数，但在维护过程中，每当更新或重新定位记录时，我们都必须承担更新指针所带来的成本。适合读操作更多的负载；
通过主索引间接引用数据可以降低指针更新的成本，但在读取路径上成本更高。适合写操作更多的负载；
1.5 缓冲 不可变性和有序性
存储结构有三个常见变量：是否使用缓冲、使用不可变的还是可变的文件，以及是否按顺序存储值（有序性）。
缓冲定义了存储结构在将数据放入磁盘之前是否选择在内存中保留一定数量的数据。每个基于磁盘的数据结构都必须在某种程度上使用缓冲，因为读写磁盘的最小数据传输单元是块，并且我们希望写入完整的块。
可变性定义了存储结构是否可以在文件的同一位置中读取文件的某些部分、更新它们并将更新的结果写入文件。不可变结构是只可追加的：写入后不修改文件内容，而是将修改附加到文件的末尾。
除此之外，还有其他方法来实现不可变性，其中之一便是写时复制（copy-on-write），其中持有更新记录的（即被修改的）页会被写入文件中的新位置而非原位置。通常，LSM树和B树之间的区别便是数据是不可变的还是原地更新的，但是也存在受B树启发但不可变的数据结构(如 Bw树)
有序性定义为数据记录是否按键顺序存储在磁盘上的页中。换句话说，紧密排序的键存储在磁盘上的连续段中。有序性常常决定了我们能否有效地扫描记录的范围，而不仅仅是定位单个数据记录。无序存储数据的方式（通常按插入顺序）对于某些写入时的优化提供了可能性。Bitcask和WiscKey直接在只可追加的文件中存储数据记录。
第2章 B树基础知识
2.1 二分搜索树
二分搜索树(BST)中每个节点将搜索空间分为左子树和右子树，如图所示：一个节点的键大于其左子树中存储的任何键，且小于其右子树中存储的任何键。此时查询的时间复杂度为
$$
O(log_2N)
$$
2.1.1 树的平衡
元素插入可能导致树不平衡的情况（即它的一个分支比另一个分支长）。最差的情况如图所示，我们最终得到一棵病态树(pathological tree)，它看起来更像一个链表。查询时会变成一个O(N)的时间复杂度。
平衡树指的是高度为log2N的树（其中N是树中数据项的总数），并且两个子树之间的高度差不大于1
树的平衡是通过以最小化树高并将每一边的节点数保持在界限内的方式重新组织节点来完成的。保持树的平衡的方法之一是在添加或删除节点后执行旋转：如果插入操作使分支不平衡（分支中的两个连续节点只有一个子节点），则可以围绕中间节点旋转树。
2.1.2 基于磁盘存储的树
二叉搜索树由于扇出较低（扇出是指每个节点允许拥有的最大子节点数），我们必须相当频繁地执行平衡操作、重新定位节点并更新指针。磁盘上会遇到以下几个问题：
- 局部性：由于元素是以随机顺序添加的，所以不能保证新创建的节点是在其父节点附近写入的，这意味着节点子指针可能跨越多个磁盘页。(修改树的布局或者使用分页二分树可以改善。)
- 由于二分树的扇出为2，必须执行O(log2N)次查找以定位要搜索的元素，这就要求执行相同数量的磁盘传输。
2.2 基于磁盘的结构
2.2.1 机械磁盘
在旋转型磁盘上，寻道增加了随机读取的成本，因为其需要磁盘旋转和机械磁头运动来将读/写磁头定位到期望的位置。然而，一旦完成了这些高成本的部分，读取或写入连续字节（即顺序操作）的成本就相对较低了。
旋转型驱动器的最小传送单元是扇区，因此当执行某些操作时，至少可以读取或写入一整个扇区。扇区大小通常从512字节到4KB不等。
2.2.2 固态硬盘
典型的SSD由记忆单元构成，这些单元连接成串（每个串通常为32到64个单元），串被组合成阵列，阵列被组合成页，页被组合成块。
一个单元可以保存一位或多位数据。不同设备的页大小不同，但通常在2KB到16KB之间。块通常包含64到512个页。块被组织成平面(plane)，最后，平面被放置在晶圆核心(die)上。SSD可以具有一个或多个晶圆核心。
可写（可编程）或可读的最小单元是页。但是，我们只能对空的记忆单元进行更改（即，对写入之前已擦除的单元进行更改）。最小的擦除实体不是页，而是保存多个页的块，这就是为什么它通常被称为擦除块。空块中的页必须按顺序写入。
闪存控制器有一个组件叫作闪存转换层(Flash Translation Layer，FTL)。它负责将页ID映射到对应的物理位置，并跟踪空的、被写过的和被丢弃的页。另外，它还负责垃圾收集，在此期间FTL会查找可以被安全擦除的块。有些块可能仍有活页，在这种情况下，它会将活页从这些块迁移到新位置，并将页ID重新映射到那里。在这之后，它擦除现在未使用的块，使它们变为可写状态。尽管垃圾收集通常是一个后台操作，但它可能会对写性能产生负面影响，特别是在随机和未对齐的写工作负载的情况下。
在SSD中，我们并不像在HDD中那样非常强调随机I/O和顺序I/O的区别，因为随机读取和顺序读取之间的延迟差异并不是很大。不过由于预取、读取连续的页和内部并行性的缘故，二者仍然存在一些差异。只写完整的块并将后续写操作组合到同一个块中，可以帮助减少所需的I/O操作的数量。
2.2.3 磁盘存储结构
磁盘操作的最小单元是块这一事实是构建有效的磁盘存储结构的主要限制和设计条件。跟踪指向块内特定位置的指针，我们必须获取整个块。
磁盘存储结构的设计要考虑到其目标存储介质的特性，并且通常要为实现更少的磁盘访问进行优化。我们可以通过提高局部性、优化结构的内部表示以及减少页外指针的数量来实现这一点
分页二叉树
磁盘存储结构的设计要考虑到其目标存储介质的特性，并且通常要为实现更少的磁盘访问进行优化。我们可以通过提高局部性、优化结构的内部表示以及减少页外指针的数量来实现这一点
2-3树的内容可阅读：
2.3 无处不在的B树
B树是建立在平衡搜索树的基础上的，不同之处在于前者具有更高的扇出（即具有更多的子节点）和更低的高度。
B树是有序的：B树节点内的键按顺序存储。B树中的查找页具有对数复杂度。在40亿(4×10^9)个项中找到搜索的关键字需要大约32次比较。
如果每一次比较都进行一次磁盘搜索，则搜索速度将大大降低，但是由于B树节点存储数十甚至数百个数据项，所以我们只需要在每个层跳转时进行一次磁盘搜索。
2.3.1 B树的层次结构
B树由多个节点组成。每个节点最多可容纳N个键和N+1个指向子节点的指针。
由于B树是一种页组织技术（即用于组织和导航固定大小的页的技术），所以节点和页这两个术语在描述中可相互替换。节点容量与其实际持有的键的个数之间的关系称为占用率。
B树的特征在于其扇出(fanout)：存储在每个节点中的键的个数。为保持树的平衡需要做出一些结构上的更改，而更高的扇出则有助于均摊这些更改的所带来的开销。
通过在单个块或多个连续块中存储指向子节点的键和指针，可以减少寻道的次数。平衡操作（即分裂和合并）会在节点已满或几乎为空时被触发。
B+树
B树允许在根节点、内部节点和叶节点当中的任意层上储存值。而B+树则仅在叶节点中存储值，其内部节点仅存储分隔键，用于指引搜索算法去找到叶节点上的关联值。
由于B+树中的值仅存储在叶节点这一层上，所以所有操作（插入、更新、删除和检索数据记录）仅影响叶节点，并且这些操作仅在分裂和合并期间才会传播到更高层。
B+树广为人知，因此我们像其他文献中一样称之为B树。例如，在[GRAEFE11]中，B+树被指定为默认设计，MySQL InnoDB也将其B+树的实现称为B树。
2.3.2 分隔键
存储在B树节点中的键称为索引条目(index entry)、分隔键(separator key)或分隔符单元格(divider cell)。它将树分割成子树（也称为分支或子范围），其持有包含对应键的范围。
键存储时已经排好序，以便使用二分搜索。查找算法通过定位一个键并跟随相应的指针从较高的层次移动到较低的层次来找到一个子树。
节点中的第一个指针指向小于第一个键的数据所在的子树，节点中的最后一个指针指向大于或等于最后一个键的数据所在的子树。其他指针指向两个键之间的子树：Ki-1≤Ks<Ki，其中K是一组键，Ks是属于子树的键。如下所示
一些B树变体还具有同级节点指针，它们通常位于叶子层上，以简化范围扫描。这些指针有助于避免在查找下一个同级节点时还要返回到父级节点的情况。
一些实现在两个方向上都有指针，在叶子层上形成一个双链表，这使得逆向迭代成为可能。
2.3.3 B树查找复杂度
从两个角度来讨论B树查找的复杂度：块传输的数量和查找期间完成的比较的次数。
从根节点每往下走一层，节点个数就多K倍。在查找期间，最多寻址logKM（其中M是B树中的项的总数）个页来查找一个搜索键。在从根到叶的通路上必须经过的子指针的数量也等于层数，换句话说，其等于树的高度h。
从比较次数的角度来看，对数基是2，因为在每个节点内搜索一个键是使用二分搜索完成的。每次比较都将搜索空间减半，因此复杂度为log2M
2.3.4 B树的查找算法
该算法从根节点上开始执行二分搜索算法，将要搜索的键与存储在根节点中的键进行比较，直到找到大于要搜索的键的第一个分隔键。
一旦找到子树，我们就顺着相应的指针继续相同的搜索过程（定位分隔键然后顺着指针往下找），直到我们到达目标叶节点，在那里我们要么找到了搜索的键，要么通过定位它的前驱节点而得出它不存在的结论。
进行范围扫描时，迭代从找到的最近的键值对开始，并顺着同级指针继续移动，直到到达范围的末尾或用尽范围谓词为止
2.3.5 键的数目
[BAYER72]提到了一个表示最佳页大小的、依赖于设备的自然数k。在这种情况下，页可以保存k到2k个键，但是可以被部分填充并保存最少k+1、最多2k+1个指向子节点的指针。
例如[GRAEFE11]，则描述了可以容纳多达N个分隔键和N+1个指针的节点
2.3.6 B树的节点分裂
在定位叶节点之后，键和值被追加到叶节点之上。更新操作则通过使用查找算法定位目标叶节点并将新值与现有键相关联来完成。
如果目标节点没有足够的可用空间，我们就说该节点溢出(overflow)了[NICHOLS66]，此时必须将其分裂为两部分才能放入新的数据。更准确地说，如果以下条件成立，则需要分裂节点：
- 对于叶节点：如果节点最多可以容纳N个键值对，且再插入一个键值对将使其超过其最大容量N。
- 对于非叶节点：如果节点最多可以容纳N+1个指针，且再插入一个指针将使其超过其最大容量N+1。
分裂是通过分配新节点、将一半元素从原分裂节点传输给它并添加它的第一个键和指向父节点的指针来完成的。在这种情况下，我们说这个键被提升(promote)了。执行分裂处的数组下标称为分裂点（也称为中点）。分裂点之后的所有元素（在非叶节点分裂的情况下，包括分裂点）都被传输到新创建的兄弟节点，其余元素保留在分裂节点中。在叶节点分裂的情况下，键连同其相关值一起被移动。
下图展示了向一个空间已满的叶节点插入新元素11的过程。我们在整个节点的中间画一条线，将一半的元素留在节点中，并将其余的元素移到新的节点中。分裂点的值被放置在父节点中，变为分隔键。
如果父节点已满，即没有容纳被提升的键和指向新创建节点的指针的空间时，也必须分裂父节点。此操作可能会一直递归传播到根节点。
一旦树达到其容量（例如，分裂一直传播到根节点），我们就必须分裂根节点。当根节点被分裂时，将分配一个新的根，该根具有分裂点的键。旧根节点（现在只拥有条目的一半）与新创建的同级节点一起被降级到下一层，从而使树高增加1。
‘在分裂根节点或合并两个节点以形成新根时，树高会发生变化。在叶节点和内部节点所在的层上，树只水平生长。
下图展示了向一个空间已满的非叶（即，根或内部）节点插入新元素11时的分裂过程。为了执行分裂，我们首先创建一个新节点，并将元素从下标N/2+1的元素处移动到该节点，随后分裂点的键被提升到父一级。
由于非叶节点分裂总是表现为从下一层传播上来的分裂，所以我们有一个额外的指针（指向下一层新创建的节点）。如果父一级没有足够的空间，则也必须被分裂。
是叶节点还是非叶节点（即，该节点是拥有键和值还是仅拥有键）被分裂并不重要。在叶节点分裂的情况下，键连同其相关值一起被移动。
分裂完成后有两个节点，我们必须选择正确的节点才能完成插入。为此，我们可以使用分隔键不变量。如果插入的键小于要提升的键，则最后插入到原分裂节点。否则，我们将要插入的键放入新创建的节点。
节点分裂分为四个步骤：
- 分配一个新节点。
- 将一半元素从分裂节点复制到新节点。
- 将新元素放入相应节点。
- 在分裂节点的父节点处，添加一个分隔键和指向新节点的指针。
2.3.7 B树的节点合并
为了进行删除，首先要定位目标叶节点。当叶节点被定位后，键和与其相关的值就被删除。
如果相邻节点所拥有的值太少（即，其占用率低于阈值），则需要合并同一层的节点。这种情况称为下溢(underflow)。
- 如果两个相邻节点具有公共父节点，并且它们的内容能够放入单个节点，则它们的内容应该合并（连接起来）；
- 如果它们的内容无法放入单个节点，则应在它们之间重新分配键以恢复平衡（参见4.4节）。
- 对于叶节点：如果一个节点可以容纳最多N个键值对，并且两个相邻节点中的键值对的数目加起来小于或等于N。
- 对于非叶节点：如果一个节点可以容纳最多N+1个指针，并且两个相邻节点中指针的数量加起来小于或等于N+1。
下图展示了删除元素16时的合并过程。在这个过程中，我们将元素从一个兄弟节点转移到另一个兄弟节点。一般来说，将来自同一层右边节点的元素移到同层左边的节点。当然，只要保留键的顺序，则把左边的节点移动到右边也可以完成合并。
下图展示了在删除元素10时必须合并的两个同级非叶节点。如果将它们的元素组合在一起后，其可被放入一个节点，那么我们只需一个节点即可。在合并非叶节点时，我们必须从父节点中下拉相应的分隔键（即降级）。父节点的指针数量减少了1，因为合并是从下层传播指针删除的结果，指针的删除则是由删除页引起的。就像分裂一样，合并可以一直传播到根节点这一层。
假设元素已经被删除，节点合并分为三步：
- 从右节点复制所有元素到左节点。
- 从父节点删除右节点指针（如果是非叶子节点合并，则将此指针进行降级）。
- 删除右节点。
为了减少分裂和合并的次数，B树经常采用的技术之一是再平衡。