元数据
数据库系统内幕
- 书名： 数据库系统内幕
- 作者： 【美】亚历克斯·彼得罗夫
- 简介： 这本书既不是关于关系型数据库的书，也不是关于NoSQL的书，而是关于在各种数据库系统中使用的算法和概念的书，重点是存储引擎和负责数据分布的组件。第一部分讨论节点本地的进程，并着重于存储引擎这个数据库系统的核心组件以及最重要的一个特有元素。第二部分讨论负责数据分布的子系统和组件，介绍如何将多个节点组织到一个数据库集群中。
- 出版时间： 2020-05-18 00:00:00
- ISBN： 9787111655169
- 分类： 计算机-数据库
- 出版社： 机械工业出版社
- PC地址：https://weread.qq.com/web/reader/b1c32af07291af69b1cf317
高亮划线
推荐序一
📌 比如访问其他机器的内存（~10s）比读本地的SSD（~100s）要快一个数量级，访问远程数据和访问本地磁盘数据的性能变得接近。 ⏱ 2022-09-28 09:59:22
📌 目前的SSD都是建议按4K来寻址，NVM却可以按字节寻址 ⏱ 2022-09-29 09:51:50
📌 原生的本质是资源池化，多台服务器上的CPU、内存和磁盘资源通过分布式技术组成一个多租户、容量更大、容错能力更强且可弹性伸缩的计算池、内存池和存储池。 ⏱ 2022-09-29 09:52:50
译者序
📌 如存储格式、索引数据结构、数据一致性 ⏱ 2022-03-28 13:32:09
前言
📌 于水平扩展（scale out），即通过运行多个数据库实例（表现得像是一个单一逻辑单元）来提高性能并增加容量 ⏱ 2022-09-29 13:12:12
📌 水平扩展仍然是客户期望的最重要的数据库特性之一 ⏱ 2022-09-29 13:12:06
📌 Dynamo ⏱ 2023-02-21 09:23:34
📌 ：在键值存储、NoSQL和最终一致性数据库之后，我们开始看到一些可扩展性更强、性能更高的数据库，它们能够在保证具有更强一致性的同时执行复杂的查询。 ⏱ 2023-02-21 09:24:39
📌 通常建议直接阅读论文 ⏱ 2022-09-29 13:13:22
📌 学习基本概念、证明和算法的一个优点是它们永不过时。 ⏱ 2022-03-28 13:34:58
📌 关于在各种数据库系统中使用的算法和概念的书，且重点是存储引擎和负责数据分布的组件。 ⏱ 2022-09-29 13:19:19
📌 数据库系统之间最显著的区别集中在两个方面：如何存储和分布数据 ⏱ 2022-03-28 13:36:21
📌 本书分为两部分，讨论了负责数据存储（第一部分）和数据分布（第二部分）的子系统和组件。 ⏱ 2022-09-29 13:20:07
第一部分 存储引擎
📌 数据库是模块化的系统，由多个部分组成：接受请求的传输层、决定以最高效方式运行查询的查询处理器、执行操作的执行引擎以及存储引擎 ⏱ 2023-02-21 09:42:50
📌 存储引擎（或数据库引擎）是数据库的一个软件组件，它负责在内存和磁盘上存储、检索和管理数据，而设计它的目的是长久保存每个节点的数据[REED78]。 ⏱ 2022-03-29 10:51:59
📌 从某个角度来看，数据库是构建在存储引擎之上的应用程序，它提供了表结构（schema）、查询语言、索引、事务和许多其他有用的特性。 ⏱ 2022-03-29 10:52:17
📌 为了获得灵活性，键和值都可以是没有预设格式的任意字节序列。它们的排序和表示语义是在更高级别的子系统中定义的。 ⏱ 2022-09-29 13:23:58
📌 用于基准测试、性能评估和比较的一个流行工具是Yahoo! Cloud Serving Benchmark（YCSB）。 ⏱ 2022-03-29 10:55:46
📌 TPC-C是一个联机事务处理（OLTP）基准，它是只读事务和更新事务的混合，用于模拟常见的应用程序工作负载。 ⏱ 2022-03-29 10:56:11
📌 该基准关注的是执行的并发事务的性能和正确性。主要性能指标是吞吐量：数据库系统每分钟能够处理的事务数。 ⏱ 2022-03-29 10:56:34
第1章 简介与概述
📌 联机事务处理（OLTP）数据库它处理大量面向用户的请求和事务。查询通常是预定义的，并且运行时间都很短。 ⏱ 2023-02-21 09:49:37
📌 联机分析处理（OLAP）数据库它处理复杂的聚合。OLAP数据库通常用于分析和数据仓库，能够处理复杂的、长时间运行的ad-hoc查询。 ⏱ 2023-02-21 09:49:48
📌 混合事务和分析处理（HTAP）数据库它结合了OLTP和OLAP存储的属性。 ⏱ 2023-02-21 09:49:51
1.2 内存数据库与磁盘数据库
📌 内存数据库（有时称为主存数据库（main memory DBMS））主要将数据储存在内存中，并使用磁盘进行数据恢复和日志记录。而磁盘数据库则将大部分数据保存在磁盘上，并使用内存来缓存磁盘内容或作为临时存储。 ⏱ 2022-03-30 00:03:13
📌 内存数据库增长的主要限制因素是内存的易失性（换言之，缺乏数据持久性）以及成本。 ⏱ 2022-09-29 13:35:15
📌 磁盘更容易维护，价格也低得多。 ⏱ 2023-02-21 21:33:01
📌 NVM存储减少甚至完全消除了（取决于某个确切的技术）读和写的延迟之间的不对称，进一步提高了读写性能，并允许字节可寻址（byte-addressable）访问。 ⏱ 2022-03-30 00:04:20
📌 数据库在认定操作完成之前，必须先将其结果写入一个顺序日志文件 ⏱ 2022-03-30 00:05:42
📌 预写日志 ⏱ 2023-02-21 21:33:34
📌 在处理该批日志数据之后，备份将持有截止到这一特定时间点的数据库快照，因此可以丢弃之前的日志内容。这个过程称为生成检查点（checkpointing）。 ⏱ 2022-03-30 00:05:58
📌 磁盘数据库使用专门的存储结构，针对磁盘访问进行了优化。在内存中，我们可以比较快地跟踪指针，并且随机内存访问比随机磁盘访问要快得多。 ⏱ 2022-03-30 00:06:35
1.3 面向列与面向行的数据库
📌 对数据库进行分类的方法之一是按数据在磁盘上的存储方式进行分类：按行或按列进行分类。表可以水平分区（将属于同一行的值存储在一起），也可以垂直分区（将属于同一列的值存储在一起）。图1-2描述了这种区别：a）显示了按列分区的值，b）显示了按行分区的值。 ⏱ 2022-09-29 13:51:46
📌 面向列的存储非常适合计算聚合的分析型工作负载 ⏱ 2022-09-29 13:53:05
📌 一些列存储使用隐式标识符（虚拟ID），并使用该值的位置（换句话说，其偏移量）将其映射回相关值[ABADI13]。 ⏱ 2022-09-29 13:53:44
📌 向量化指令 ⏱ 2022-04-22 10:36:42
📌 将具有相同数据类型的值存储在一起（例如，数字与数字在一起，字符串与字符串在一起）可以提高压缩率。 ⏱ 2022-04-22 10:36:38
📌 面向列的数据库不应与宽列式存储（如BigTable或HBase）相混淆 ⏱ 2022-09-29 13:54:56
📌 列被分组为列族（通常存储相同类型的数据），并且在每个列族中，数据被逐行存储。 ⏱ 2022-04-22 10:37:13
📌 列族中的每个列都由列键标识，该键是列族名称和限定符（在本例中为html，cnnsi.com，my.look.ca）的组合。列族可以按照时间戳存储多个版本的数据。 ⏱ 2022-09-30 08:54:59
📌 列族被单独存储，但在每个列族中，属于同一键的数据被存储在一起。 ⏱ 2022-09-30 08:55:31
1.4 数据文件和索引文件
📌 数据库系统确实使用文件来存储数据，但它不是依赖于目录和文件的文件系统层次结构来定位记录，而是使用特定于实现的格式来组织文件。 ⏱ 2023-02-22 21:10:40
📌 数据库系统通常将数据文件和索引文件分开：数据文件存储数据记录，而索引文件存储元数据并使用它来定位数据文件中的记录。 ⏱ 2022-04-22 10:58:15
📌 页可以被组织成记录的序列或分槽页（slotted page） ⏱ 2023-02-22 21:12:39
📌 。大多数现代存储系统不显式地删除页上的数据。相反，它们使用删除标记（deletion marker，也称为墓碑（tombstone）），其中包含此删除动作的元数据，如键和时间戳。 ⏱ 2023-02-22 21:13:14
📌 数据文件（有时称为主文件（primary file））通常可以用索引组织表（Index-Organized Table，IOT）、堆组织表（heap-organized table，即堆文件）或哈希组织表（hash-organized table，即哈希文件）来实现。 ⏱ 2022-04-30 09:20:45
📌 索引组织表将数据记录存储在索引自身。由于记录是按键的顺序存储的，所以索引组织表中的范围扫描可以通过顺序扫描其内容来实现。 ⏱ 2022-09-30 09:54:58
📌 索引是一种为了高效检索数据而对磁盘上的数据记录进行组织的结构。索引文件被组织成专门的结构，将键映射到数据文件里的记录。这些记录由对应的键（在堆文件的情况下）或主键（在索引组织表的情况下）所标识。 ⏱ 2022-09-30 09:55:38
📌 索引是一种为了高效检索数据而对磁盘上的数据记录进行组织的结构。 ⏱ 2022-04-30 09:30:21
📌 主（数据）文件上的索引称为主索引。但是，在大多数情况下，我们还可以假设主索引是在主键或作为主键的一组键之上构建的。所有其他索引都称为二级索引（secondary index）。 ⏱ 2022-09-30 09:59:38
📌 二级索引可以直接指向数据记录，也可以简单地存储它的主键 ⏱ 2022-09-30 09:59:43
📌 聚簇索引既可以是索引组织的，也可以具有单独的索引和数据文件 ⏱ 2022-09-30 10:03:08
📌 。通过直接引用数据，我们可以减少查找磁盘的次数，但在维护过程中，每当更新或重新定位记录时，我们都必须承担更新指针所带来的成本。通过主索引间接引用数据可以降低指针更新的成本，但在读取路径上成本更高。 ⏱ 2022-04-30 09:36:41
📌 我们还可以使用混合方法将数据文件偏移量和主键存储在一起。首先，你要检查数据偏移量是否仍然有效，如果它已经发生变化了，则需要额外对主键索引进行遍历，在找到新的偏移量后更新索引文件。 ⏱ 2022-04-30 09:38:20
1.5 缓冲 不可变性和有序性
📌 存储结构有三个常见变量：是否使用缓冲、使用不可变的还是可变的文件，以及是否按顺序存储值（有序性）。 ⏱ 2022-09-30 19:32:26
📌 缓冲定义了存储结构在将数据放入磁盘之前是否选择在内存中保留一定数量的数据。 ⏱ 2022-04-30 09:40:24
📌 可变性定义了存储结构是否可以在文件的同一位置中读取文件的某些部分、更新它们并将更新的结果写入文件。 ⏱ 2022-04-30 09:41:03
📌 不可变结构是只可追加的：写入后不修改文件内容，而是将修改附加到文件的末尾。除此之外，还有其他方法来实现不可变性，其中之一便是写时复制 ⏱ 2022-04-30 09:41:14
📌 LSM树和B树之间的区别便是数据是不可变的还是原地更新的，但是也存在受B树启发但不可变的数据结构（例如，Bw树，见6.5节）。 ⏱ 2023-02-22 21:17:38
📌 有序性定义为数据记录是否按键顺序存储在磁盘上的页中。 ⏱ 2022-04-30 09:42:07
📌 无序存储数据的方式（通常按插入顺序）对于某些写入时的优化提供了可能性。 ⏱ 2022-04-30 09:42:24
第2章 B树基础知识
📌 不可变性为影响数据库设计和实现的核心概念之一 ⏱ 2022-09-30 19:36:30
📌 存储引擎通常允许同一数据记录在数据库中存在多个版本，例如：当使用多版本并发控制（multi-version concurrency control，参见5.3.6节）或分槽页结构（参见3.5节）时。 ⏱ 2022-04-30 09:49:17
📌 插入操作并不会遵循任何特定模式，元素插入可能导致树不平衡的情况（即它的一个分支比另一个分支长）。最差的情况如图2-3b所示，我们最终得到一棵病态树（pathological tree） ⏱ 2023-02-22 21:20:04
📌 平衡树指的是高度为log2N的树（其中N是树中数据项的总数），并且两个子树之间的高度差不大于1[KNUTH98][插图]。 ⏱ 2022-04-30 09:58:09
📌 为了防止在一个分支保持为空的时候还在另一个分支上增加新的元素使之变得更长（如图2-3b所示），我们可以在每次操作之后对树进行平衡。树的平衡是通过以最小化树高并将每一边的节点数保持在界限内的方式重新组织节点来完成的。 ⏱ 2022-04-30 09:58:39
📌 更一般地，二分搜索树将子树之间的高度差保持在一个小的常数因子内。 ⏱ 2022-04-30 09:58:54
📌 由于元素是以随机顺序添加的，所以不能保证新创建的节点是在其父节点附近写入的，这意味着节点子指针可能跨越多个磁盘页。 ⏱ 2022-04-30 09:59:42
📌 一个在磁盘上存储二分搜索树的简单方法所需的磁盘寻道次数与比较次数一样多，因为这样的结构原生不具备数据局部性。 ⏱ 2022-04-30 10:00:14
📌 更适合磁盘实现的树必须具有以下属性：·高扇出，以改善邻近键的数据局部性。·低高度，以减少遍历期间的寻道次数。 ⏱ 2022-04-30 10:15:43
📌 新型数据结构仍在不断涌现，它们被优化以应用于非易失性的字节可寻址存储 ⏱ 2022-05-01 10:00:13
📌 在旋转型磁盘上，寻道增加了随机读取的成本，因为其需要磁盘旋转和机械磁头运动来将读/写磁头定位到期望的位置。然而，一旦完成了这些高成本的部分，读取或写入连续字节（即顺序操作）的成本就相对较低了。 ⏱ 2022-05-01 10:00:32
📌 顺序I/O将会从磁盘读取和写入连续的存储段。 ⏱ 2022-05-01 10:00:44
📌 典型的SSD由记忆单元构成，这些单元连接成串（每个串通常为32到64个单元），串被组合成阵列，阵列被组合成页，页被组合成块[LARRIVEE15]。 ⏱ 2022-09-30 19:45:59
📌 可写（可编程）或可读的最小单元是页。但是，我们只能对空的记忆单元进行更改（即，对写入之前已擦除的单元进行更改）。最小的擦除实体不是页，而是保存多个页的块，这就是为什么它通常被称为擦除块。空块中的页必须按顺序写入。 ⏱ 2022-09-30 19:46:39
📌 闪存转换层（Flash Translation Layer，FTL） ⏱ 2022-09-30 19:47:02
📌 因此每当我们从块设备读取单个字时，包含它的整个块将会被读取。这是我们不能忽视的一个限制，在处理基于磁盘存储的数据结构时应该始终考虑到这一点。 ⏱ 2022-09-30 19:47:21
📌 尽管垃圾收集通常是一个后台操作，但它可能会对写性能产生负面影响，特别是在随机和未对齐的写工作负载的情况下。 ⏱ 2022-09-30 19:51:34
📌 只写完整的块并将后续写操作组合到同一个块中，可以帮助减少所需的I/O操作的数量。
- 💭 针对ssd优化的关键点 - ⏱ 2022-09-30 19:49:06
📌 除了磁盘访问本身的成本之外，磁盘操作的最小单元是块这一事实是构建有效的磁盘存储结构的主要限制和设计条件。 ⏱ 2022-05-01 10:02:38
📌 磁盘存储结构的设计要考虑到其目标存储介质的特性，并且通常要为实现更少的磁盘访问进行优化。 ⏱ 2022-05-01 10:03:25
📌 即高扇出和低高度是实现最佳磁盘数据结构所需的特性。 ⏱ 2022-09-30 19:54:38
📌 B树结合了这些思想：增加节点扇出、减少树高和节点指针的数量、降低平衡操作的频率。 ⏱ 2022-05-01 10:03:38
2.3 无处不在的B树
📌 ，B树是建立在平衡搜索树的基础上的，不同之处在于前者具有更高的扇出（即具有更多的子节点）和更低的高度。 ⏱ 2022-05-03 09:25:53
📌 B树由多个节点组成。每个节点最多可容纳N个键和N+1个指向子节点的指针 ⏱ 2022-09-30 20:10:22
📌 节点容量与其实际持有的键的个数之间的关系称为占用率。 ⏱ 2022-09-30 20:11:46
📌 B树的特征在于其扇出（fanout）：存储在每个节点中的键的个数。为保持树的平衡需要做出一些结构上的更改，而更高的扇出则有助于均摊这些更改的所带来的开销。同时，通过在单个块或多个连续块中存储指向子节点的键和指针，可以减少寻道的次数。平衡操作（即分裂和合并）会在节点已满或几乎为空时被触发。 ⏱ 2022-05-03 09:27:44
📌 B树允许在根节点、内部节点和叶节点当中的任意层上储存值。而B+树则仅在叶节点中存储值，其内部节点仅存储分隔键，用于指引搜索算法去找到叶节点上的关联值。 ⏱ 2022-05-03 09:28:04
📌 由于B+树中的值仅存储在叶节点这一层上，所以所有操作（插入、更新、删除和检索数据记录）仅影响叶节点，并且这些操作仅在分裂和合并期间才会传播到更高层。 ⏱ 2022-09-30 20:12:42
📌 一些B树变体还具有同级节点指针，它们通常位于叶子层上，以简化范围扫描。 ⏱ 2022-05-03 10:15:49
📌 使B树与众不同的是，它不是自上而下构建的（像二分搜索树那样），而是采用相反的构建方式——自下而上。 ⏱ 2022-05-03 10:16:07
📌 如果两个相邻节点具有公共父节点，并且它们的内容能够放入单个节点，则它们的内容应该合并（连接起来）；如果它们的内容无法放入单个节点，则应在它们之间重新分配键以恢复平衡 ⏱ 2022-05-04 17:10:01
📌 为了减少分裂和合并的次数，B树经常采用的技术之一是再平衡 ⏱ 2022-05-04 17:10:38
3.2 二进制编码
📌 布局（layout） ⏱ 2022-09-30 20:31:44
📌 当处理多字节数值时，务必在编解码时使用相同的字节序（byte-order或endianness），字节序决定了一组字节的先后顺序。 ⏱ 2022-09-30 20:32:11
📌 数据记录由数值、字符串、布尔值之类的原始类型以及它们的组合构成。但是，当通过网络传输数据或是将其存储在磁盘上时，我们只能使用字节序列。 ⏱ 2022-05-04 17:20:34
📌 字符串和其他变长数据类型（比如定长类型的数组）可以序列化为一个表示长度的数值字段size再加上size个字节，后面的这些字节是实际的数据。 ⏱ 2022-09-30 20:34:40
📌 枚举值（enum）可以被表示为整数，常被用于二进制格式和通信协议。枚举值用于表示重复多、基数少的值。 ⏱ 2022-09-30 20:36:55
📌 标志，它是打包的布尔值和枚举值的组合。标志可以表示多个非互斥的布尔值参数 ⏱ 2022-09-30 20:37:21
📌 像布尔值一样，我们可以利用位掩码和位运算符从打包的值中读写各个标志位。 ⏱ 2022-09-30 20:37:57
3.3 通用原理
📌 是否要将文件拆分为相同大小的页、哪些页由单个块或多个连续块所组成 ⏱ 2022-09-30 20:38:38
📌 文件通常以定长的头部（header）开始，可能以一个定长的尾部（trailer）结束。尾部包含需要被快速访问的辅助信息或解析文件其余部分所必要的信息。 ⏱ 2022-09-30 20:39:12
📌 许多数据库的表结构（schema）是固定的，其指定了表中字段的数量、顺序和类型。 ⏱ 2022-09-30 20:39:36
📌 固定的表结构有助于减少磁盘上存储的数据量：只需使用位置标识符而不用让每条记录都带上字段名。 ⏱ 2022-09-30 20:40:01
📌 为了避免涉及多个字段的计算，我们可以将偏移量和长度都编入定长区域，这样就可以独立地定位任何一个变长字段。 ⏱ 2022-09-30 20:40:44
3.4 页的结构
📌 数据库将数据记录存储在数据文件和索引文件中。这些文件被划分为固定大小的单元，称为页。页大小通常是文件系统块的整数倍，一般是4～16KB。 ⏱ 2022-09-30 20:41:27
3.5 分槽页
📌 当存储变长记录时，主要的问题是如何管理可用空间：已删除记录所占用的空间需要被回收。 ⏱ 2022-09-30 20:47:35
📌 为了简化变长记录的空间管理问题，我们可以将页分成固定大小的段。 ⏱ 2022-09-30 20:47:52
📌 空间回收可以通过简单地重写页并移动记录来完成，但是需要保证记录的偏移量不变，因为页外的指针会用到这些偏移量。 ⏱ 2022-09-30 20:48:07
📌 分槽页（slotted page） ⏱ 2022-09-30 20:48:28
📌 我们将页组织成一个槽或单元格（cell）的集合，并将指针和单元格分别存放在页两侧的独立内存区域中。 ⏱ 2022-09-30 20:49:03
📌 分槽页具有一个固定大小的头部，其中包含关于页和单元格的重要信息（参见4.1节）。单元格的大小可能各不相同，并且可以容纳任意数据：键、指针、数据记录等。 ⏱ 2022-09-30 20:49:24
📌 动态布局：从页外部，只能通过槽ID来引用槽，而确切的位置是由页内部决定的。 ⏱ 2022-09-30 20:49:43
3.6 单元格布局
📌 单元格分为键单元格和键值单元格两种。键单元格包含一个分隔键和一个指针，该指针指向两个相邻键之间的页。键值单元格包含键和相关联的数据记录。 ⏱ 2022-09-30 20:54:42
📌 由于页大小是固定的，并且页由页缓存来管理（参见5.1节），我们只需要存储页ID即可，使用时再通过查找表将其转换成真正的文件偏移量。 ⏱ 2022-09-30 20:58:43
📌 单元格偏移量是页局部的概念，它是相对于页起始位置的偏移量：因此，我们可以使用比较小的整数基数，从而使格式更紧凑。 ⏱ 2022-09-30 20:59:18
📌 单元格中的键和值不一定是定长的，它们都可以是变长的，其位置可以通过偏移量从定长的单元格头部计算得到。 ⏱ 2022-09-30 20:59:35
3.7 将单元格放进分槽页
📌 要把单元组织成页，我们可以使用在3.4节中讨论过的分槽页技术。我们将单元格追加到页的右侧（从尾向头），并将单元格偏移量/指针放在页的左侧 ⏱ 2022-09-30 21:00:11
3.8 管理变长数据
📌 从页删除一条记录不用删除实际的单元格，也不用移动其他单元格以重用这些释放的空间。相反，可以将这个单元格标记为已删除，并根据被释放内存的大小以及指针更新内存中的可用列表。 ⏱ 2022-09-30 21:01:03
📌 可用列表保存了可用段的偏移量及其大小。每当插入新单元格时，我们首先检查可用性列表，看看是否有能放得下的段。 ⏱ 2022-09-30 21:01:10
📌 SQLite把未被占用的段称为空闲块（freeblock），并将指向第一个空闲块的指针保存在页头部。此外，页上还保存了可用字节总数，用来快速检查新元素能否在碎片整理后被放入该页中。 ⏱ 2022-09-30 21:01:24
📌 ：页标识符用于在树文件中定位子节点，而单元格偏移量用于在页内定位单元格。 ⏱ 2022-09-30 21:02:26
3.9 版本
📌 版本也可以直接存储在索引文件的头部。在这种情况下，头部的一部分（或整个头部）必须用一种不随版本变化的格式进行编码。 ⏱ 2022-09-30 21:05:27
3.10 校验和
📌 校验和是用XOR结合奇偶校验或求和来计算的 ⏱ 2022-09-30 21:06:09
📌 CRC可以帮助检测突发错误（比如多个连续比特位的损坏），其通常使用查找表和多项式除法来实现[STONE98]。 ⏱ 2022-09-30 21:06:17
📌 校验和通常是针对每个页计算的，并保存在页头部 ⏱ 2022-09-30 21:07:54
4.1 页头
📌 页头保存有关可用于页定位、维护和优化的信息。它通常包含描述页内容和布局的标志位、页中单元格的数量、标记空闲空间的上界与下界偏移量（用于追加单元格偏移量和数据）以及其他有用的元数据。 ⏱ 2022-09-30 21:11:20
📌 魔数通常用于校验和完整性检查[GIAMPAOLO98]。 ⏱ 2022-09-30 21:11:53
📌 一些实现存储了前序和后继指针，指向左、右同级页。这些指针有助于定位相邻节点，而不必返回父节点。 ⏱ 2022-09-30 21:12:41
📌 存储同级指针的缺点之一是在分裂和合并期间必须更新它们。 ⏱ 2022-09-30 21:13:03
📌 由于更新必须在同级节点中进行，而不是在分裂/合并节点中进行，所以可能需要额外的锁。 ⏱ 2022-09-30 21:13:19
📌 我们可以采用一种稍微不同的方法，将单元格中的最右指针与节点的高键（high key）存储在一起。节点的高键表示当前节点下的子树中可能存在的最高的键。 ⏱ 2022-09-30 21:15:27
📌 为Blink树 ⏱ 2022-09-30 21:15:39
📌 Blink树向每个节点添加一个KN+1键。它指定了指针PN指向的子树中所存储的键的上限，因此它是当前子树中所存储的值的一个上限。 ⏱ 2022-09-30 21:16:00
📌 B树算法规定每个节点持有特定数量的元素。 ⏱ 2022-09-30 21:18:49
📌 为了实现变长节点而无须将数据复制到新的连续区域，我们可以从多个链接起来的页中构建节点。 ⏱ 2022-09-30 21:22:20
📌 我们可以分配一个4K的扩展页，并从原始页链接到它。这些链接起来的页被称为溢出页（overflow page）。为简洁起见，在本节中，我们将原始页称为主页（primary page）。 ⏱ 2022-09-30 21:22:44
📌 使用这种方法，我们根本不会遇到页面没有可用空间的情况，因为页面总是至少具有max_payload_size个字节。 ⏱ 2022-09-30 21:23:05
📌 当分配第一个溢出页时，其页ID存储在主页的头部。如果单个溢出页不够，则通过在前一个溢出页的头部保存下一个溢出页的ID的方式，将多个溢出页链接在一起。要查找给定的数据，我们可能不得不遍历多个溢出页。 ⏱ 2022-09-30 21:24:37
📌 由于键通常具有很高的基数，所以只存储键的一部分是有意义的，因为大多数比较可以通过驻留在主页中的部分截断的键来进行。 ⏱ 2022-09-30 21:24:55
4.2 二分搜索
📌 在较高的层次上，大多数搜索并不会产生精确的匹配，此时我们感兴趣的是搜索的方向，在这种情况下，我们必须找到第一个大于搜索元素的值，然后跟随相应的子链接进入相关联的子树。 ⏱ 2022-09-30 21:25:58
📌 B树页中的单元格按插入顺序存储，只有单元格偏移量保留了逻辑元素的顺序。 ⏱ 2022-09-30 21:26:06
4.3 传播分裂与合并
📌 一些实现（例如WiredTiger）将父指针用于叶节点的遍历以避免死锁，死锁可能在使用同级指针时发生（参见[MILLER78]、[LEHMAN81]）。 ⏱ 2022-09-30 21:28:25
📌 导航信息包含从根节点一路下来的引用，用于在传播分裂或合并时进行反向回溯。对此，最自然的数据结构是栈。例如，PostgreSQL将导航信息存储在栈中，内部称之为BTStack。 ⏱ 2022-09-30 21:29:18
4.4 再平衡
📌 一些B树的实现方案试图推迟分裂和合并操作，以便通过在层内再平衡各元素来平摊代价，或将元素从占用较多的节点转移到占用较少的节点中，通过这一方式尽可能推迟分裂或合并。 ⏱ 2022-09-30 21:30:06
📌 我们可以在插入和删除操作期间执行负载平衡[GRAEFE11]。 ⏱ 2022-09-30 21:30:15
4.5 仅在右侧追加
📌 许多数据库系统使用单调自增的数值作为主索引的键。这为优化创造了机会，因为所有的插入都发生在索引的末尾（在最右边的叶子中），所以大多数分裂发生在每层的最右节点上。 ⏱ 2022-09-30 21:37:59
📌 PostgreSQL称这种情况为快速路径（fastpath）。当插入的键严格地大于最右页中的第一个键，并且最右页有足够的空间来容纳新插入的条目时，新条目被插入缓存的最右叶中的适当位置，并且可以跳过整个读取路径。 ⏱ 2022-09-30 21:38:08
📌 由于创建树所需的数据已经被排序，所以在批量加载过程中，我们只需要将数据项追加到树中最右边的位置。 ⏱ 2022-09-30 21:38:54
📌 在这种情况下，我们可以完全避免分裂和合并，并自下而上地构建树，逐层写出，或者在有足够的指针指向已经写出的低层节点时立即写出高层节点。 ⏱ 2022-09-30 21:39:06
📌 实现批量加载的一种方法是在叶子层上按页写入预排序数据（而不是插入单个元素）。在叶子页被写入之后，我们将它的第一个键传播给父页，并使用一个标准算法来构建更高的B树层级 ⏱ 2022-09-30 21:39:16
📌 不可变B树可以用同样的方式创建，但与可变B树不同的是，它不需要为后续的修改预留空间 ⏱ 2022-09-30 21:39:32
4.6 压缩
📌 较大的压缩率可以提升数据存储空间利用率，允许你在一次访问中获取更多的数据，但这可能需要更多的内存和CPU周期来进行压缩和解压缩。 ⏱ 2022-09-30 21:43:24
📌 然而，这样一来，被压缩的页只能占用磁盘块的一部分。并且，由于传输通常以磁盘块为单位进行，所以可能需要换入额外的字节[RAY95] ⏱ 2022-09-30 21:44:23
📌 另一种方法是仅压缩数据，要么按行（压缩整条数据记录），要么按列（对每一列进行压缩）。在这种情况下，页的管理和压缩是解耦的 ⏱ 2022-09-30 21:44:49
4.7 清扫与维护
📌 由于性能，通常不会对垃圾区域进行填零操作，因为这些区域最终还是会被新数据所覆盖。 ⏱ 2022-09-30 21:47:24
📌 当页被分裂时，只对偏移量进行调整。由于页的其余部分不可寻址，所以偏移量被截断的单元格不再可访问，因此每当新数据到达时，它们将被覆盖，或者在清扫进程中被垃圾收集。 ⏱ 2022-09-30 21:47:55
📌 负责空间回收和页重写的过程称为压实（compaction）、清扫（vacuum）或直接称为维护（maintenance） ⏱ 2022-09-30 21:50:40
第5章 事务处理与恢复
📌 数据库事务必须遵从原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持久性（Durability），这些属性通常合称为ACID ⏱ 2022-09-30 21:57:19
📌 一致性是一种特定于具体应用的保证：事务只能将数据库从一个有效状态带到另一个有效状态，并保持所有的数据库不变量（比如约束、引用完整性等） ⏱ 2022-09-30 21:57:47
📌 锁管理器可保护对资源的访问，并防止那些可能破坏数据完整性的并发访问。 ⏱ 2022-09-30 22:03:32
📌 页缓存充当了持久性存储（磁盘）和存储引擎其余部分之间的中介。 ⏱ 2022-09-30 22:03:51
📌 日志管理器记录了已应用在缓存页上的操作（日志条目），这些操作尚未与持久性存储同步，而日志可以确保这些操作不会在崩溃时丢失。 ⏱ 2022-09-30 22:04:04
📌 日志来重新应用这些操作并重建缓存状态。日志条目也可以用来撤销已中止的事务所做的更改。 ⏱ 2022-09-30 22:04:14
5.1 缓冲区管理
📌 页缓存负责缓存从磁盘读取的页。如果数据库崩溃或意外关闭，则缓存的内容也将丢失。 ⏱ 2022-09-30 22:06:50
📌 很多数据库系统使用O_DIRECT标志打开文件。该标志允许I/O系统调用绕过内核的页缓存直接访问磁盘，并使用数据库专用的缓冲区管理 ⏱ 2022-09-30 22:07:54
📌 只能从内存同步到磁盘，而不能反过来进行。 ⏱ 2022-09-30 22:09:19
📌 若想让页缓存不要换出某些页，则可以将它们固定（pin）。 ⏱ 2022-09-30 22:10:01
📌 如果页的内容与磁盘是同步的（已刷写过或从未修改过），并且该页面未被固定或引用，则可以立即将其换出。脏页则必须在刷写之后才能换出。如果页正在被其他线程使用，则不能将其换出。 ⏱ 2022-10-01 02:57:09
📌 如果每次换出页都刷写磁盘，则其性能可能会很差。因此某些数据库使用单独的后台进程，该进程循环检查可能被换出的脏页，更新其磁盘上的版本。 ⏱ 2022-10-01 02:57:23
📌 为了确保所有更改都被持久化，检查点进程会协调刷写进程。检查点进程控制预写日志（WAL）和页缓存，并确保两者协同工作。 ⏱ 2022-10-01 02:57:45
📌 被固定的页会在内存中保留更长的时间，这有助于减少磁盘访问次数并提高性能[GRAEFE11]。 ⏱ 2022-10-01 11:48:00
📌 页缓存也允许存储引擎对预取和换出进行细粒度的控制，存储引擎可以指示页缓存在访问页之前提前加载页 ⏱ 2022-10-01 11:48:43
📌 最长时间未使用策略（LRU）[TANENBAUM14]。 ⏱ 2022-10-01 11:51:25
📌 2Q（双队列LRU）维护两个队列，在初次访问时放入第一个队列，在后续访问时将它们移入第二个热队列，从而区分最近访问的页和经常访问的页[JONSON94]。LRU-K通过跟踪最近的K次访问来识别频繁用到的页，并使用此信息来估计访问时间[ONEIL93]。 ⏱ 2022-10-01 11:51:55
📌 CLOCK算法变体常常被用作LRU的一种更加紧凑、更加缓存友好且并发性更好的替代品 ⏱ 2022-10-01 11:52:43
📌 CLOCK-sweep算法将页的引用和与之关联的访问位保存在环形缓冲区中。 ⏱ 2022-10-01 11:52:47
📌 使用环状缓冲区的一个优点是：时钟指针和缓冲区内容都可以用比较-置换（CAS）原子操作来修改，无须额外的加锁机制。 ⏱ 2022-10-01 11:53:53
📌 为了改善这一情况，我们可以追踪页引用事件而不是页换入事件。其中一种实现是跟踪具有最小使用频率（LFU）的页。 ⏱ 2022-10-01 11:54:08
📌 TinyLFU是一种基于频率的页置换策略，它正是这样做的：TinyLFU不根据页换入的时间来换出页，而是根据使用频率对页进行排序 ⏱ 2022-10-01 11:54:31
5.2 恢复
📌 预写日志（Write-Ahead Log，WAL，也称为提交日志）是一种仅追加的辅助磁盘数据结构，用于崩溃和事务的恢复。 ⏱ 2022-10-01 11:56:35
📌 将缓存的内容刷写回磁盘之前，WAL是保留操作历史的唯一磁盘副本 ⏱ 2022-10-01 11:57:51
📌 预写日志的主要功能可以概括为：·在允许页缓存将页上的修改缓存起来的同时，保证数据库系统仍然具有持久性语义。·在那些受操作影响的缓存页被同步到磁盘上之前，将所有操作持久化到磁盘上。每个修改数据库状态的操作必须先写日志到磁盘上，然后才能修改相关页的内容。·当发生崩溃时，使系统可以从操作日志中重建内存中丢失的更改。 ⏱ 2022-10-01 11:58:10
📌 检查点进程会定期刷写所有脏页（即修改过的页），它通过执行fsync()内核调用来将脏页的内容同步到磁盘，同时清除页上的脏标志。 ⏱ 2022-10-01 11:58:46
📌 在Linux和其他少数操作系统中，即使发生了I/O错误，fsync也会从刷新失败的页中清除脏标志。此外，错误只会被报告给故障发生时打开着的文件描述符，因此fsync将不会返回在调用它的文件描述符打开之前发生的任何错误[CORBET18]。 ⏱ 2022-10-01 11:59:04
📌 预写日志是仅追加的，并且已写入的内容是不可变的，因此所有对日志的写入都是顺序的 ⏱ 2022-10-01 11:59:32
📌 由于日志记录不一定占据整个磁盘块，所以其内容会被缓存在日志缓冲区中，并在强制刷盘（force）操作时被刷写到磁盘上 ⏱ 2022-10-01 12:01:09
📌 强制刷盘操作发生在日志缓冲区被填满时，也可能被来自事务管理器或页缓存的请求所触发。各日志记录必须以LSN的顺序刷写到磁盘上。 ⏱ 2022-10-01 12:01:12
📌 除了单独的操作记录外，WAL还会保存事务完成的记录。只有当事务提交记录完成刷盘之后，才能将该事务视为已提交。 ⏱ 2022-10-01 12:09:49
📌 系统在回滚或恢复期间也有可能发生崩溃，为了确保这种情况下系统能继续正常工作，某些系统会在撤销操作时记录补偿日志记录（CLR）并将其存储在日志中。 ⏱ 2022-10-01 12:10:11
📌 模糊检查点（fuzzy checkpoint） ⏱ 2022-10-01 12:10:51
📌 日志头部的last_checkpoint指针记录了最后一次成功的检查点信息。模糊检查点以特殊的begin_checkpoint日志记录开始（标志着检查点的开始），结束于end_checkpoint日志记录，其中包含脏页的信息以及事务表的内容。 ⏱ 2022-10-01 12:36:31
📌 影子页（shadow paging）——一种写时复制（copy-on-write）技术 ⏱ 2022-10-01 12:37:20
📌 新内容被存放在一个新的、未发布的影子页中，并通过指针翻转使其可见，从旧页切换到包含更新内容的新页。 ⏱ 2022-10-01 12:38:36
📌 任何状态变化都可以由前像（before-image）和后像（after-image）或相应的重做（redo）和撤销（undo）操作表示。 ⏱ 2022-10-01 12:38:57
📌 使用逻辑日志记录执行撤销操作（以提升并发），使用物理日志记录执行重做操作（以缩短恢复时间） ⏱ 2022-10-01 12:39:27
📌 在事务提交之前允许刷写事务修改过的页，这被称为steal策略。而no-steal策略不允许将未提交的事务内容刷写到磁盘。之所以称为steal策略，是因为它将脏页偷窃（steal）出来，将其中的内容刷写到磁盘上，并从磁盘加载另一个页到该位置。 ⏱ 2022-10-01 12:40:09
📌 force策略要求在事务提交前将事务修改的所有页刷写到磁盘上。而在no-force策略中，即使事务修改的某些页尚未刷写到磁盘上，该事务也可以提交。 ⏱ 2022-10-01 12:40:45
📌 撤销操作会回滚那些已提交事务强制刷盘的页上的更新，而重做操作会将已提交事务执行的更改应用到磁盘上。 ⏱ 2022-10-01 14:12:12
📌 在使用force策略时，崩溃恢复无须任何其他工作即可重建已提交事务的结果，因为这些事务修改的页都已被刷写到磁盘。该方法的主要缺点是，由于在事务提交中必须要进行I/O操作，所以提交时间更长。 ⏱ 2022-10-01 14:13:00
📌 ARIES是一种steal/no-force的恢复算法。它使用物理重做日志来提高恢复期间的性能（因为能更快地应用更改），并使用逻辑撤销日志来提高正常操作期间的并发（因为逻辑撤销操作可以独立地应用到页中）。 ⏱ 2022-10-01 14:13:55
5.3 并发控制
📌 并发控制是一组用于处理并发事务间交互的技术。 ⏱ 2022-10-01 14:15:26
📌 乐观并发控制（OCC）允许多个事务执行并发的读取和写入操作，最后确定其执行结果能否被串行化（serializable[插图]） ⏱ 2022-10-01 14:15:38
📌 多版本并发控制（MVCC）允许一条记录同时存在多个时间戳的版本，通过这种方式保证事务读到的是数据库过去某个时刻的一致视图。 ⏱ 2022-10-01 14:15:58
📌 悲观（也称为保守）并发控制（PCC）既有基于锁的实现，也有不加锁的实现，它们的主要区别在于如何管理和授权对共享资源的访问。 ⏱ 2022-10-01 14:16:33
📌 悲观的调度可能导致死锁：多个事务需要互相等待对方释放锁才能继续执行。 ⏱ 2022-10-01 14:16:38
📌 如果一个调度等效于同一组事务的某一完整串行调度，则该调度是可串行化的。换句话说，它产生的结果与我们以某种顺序一个接一个地执行一组事务的结果相同。 ⏱ 2022-10-01 14:18:26
📌 隔离级别指定了事务的各部分如何以及何时可以被其他事务看到。 ⏱ 2022-10-01 14:18:48
📌 脏读、不可重复读和幻读。 ⏱ 2022-10-01 14:19:08
📌 脏读（dirty read）是指一个事务能读到其他事务未提交的更改。 ⏱ 2022-10-01 14:19:14
📌 不可重复读（nonrepeatable read，有时也称为模糊读（fuzzy read）），是指同一事务两次查询同一行却得到不同的结果。 ⏱ 2022-10-01 14:19:43
📌 幻读是指事务两次查询同样的行集合却得到不同的结果。它与不可重复读类似，但仅适用于范围查询。 ⏱ 2022-10-01 14:21:16
📌 丢失更新，脏写和写偏斜。 ⏱ 2022-10-01 14:21:46
📌 丢失更新（lost update）发生在事务T1和T2同时尝试更新V的值时。T1和T2读取V的值。T1更新V并提交，之后T2也更新V并提交。由于这两个事务不知道彼此的存在，所以如果允许二者都提交，则T1的结果将被T2的结果覆盖，T1的更新将丢失。 ⏱ 2022-10-01 14:21:49
📌 脏写（dirty write）指的是某个事务拿到了一个未提交的值（即脏读），对其进行修改并保存。 ⏱ 2022-10-01 14:40:16
📌 写偏斜（write skew）是指各个单独的事务都遵守要求的约束，但它们的组合却违反了这些约束 ⏱ 2022-10-01 14:40:22
📌 最低（换句话说，最弱）的隔离级别是读未提交（read uncommitted） ⏱ 2022-10-01 14:41:35
📌 脏读是不允许的，但幻读和不可重复读是允许的。该隔离级别称为读已提交（read commited）。 ⏱ 2022-10-01 14:42:16
📌 最强的隔离级别是可串行化（serializability）。 ⏱ 2022-10-01 14:42:21
📌 在快照隔离中，一个事务可以观察到所有在该事务开始前已提交的事务所做的状态更改。每个事务都会获取一个数据快照，并在快照上执行查询 ⏱ 2022-10-01 14:42:55
📌 快照隔离中可能发生写偏斜异常：如果两个事务分别读取本地状态、修改不同的记录并且遵守本地的约束，则二者都可以提交 ⏱ 2022-10-01 14:43:32
📌 在该步骤完成后，我们就知道了事务的所有依赖条件（读集合），以及事务会产生的所有副作用（写集合） ⏱ 2022-10-01 14:45:07
📌 验证阶段确定提交事务是否遵守ACID性质。 ⏱ 2022-10-01 14:45:23
📌 验证有两种实现方式：检查与已提交事务的冲突（后向式），以及检查与当前处于验证阶段的事务的冲突（前向式）。 ⏱ 2022-10-01 14:45:41
📌 多版本并发控制是数据库中实现事务一致性的一种方法，它允许记录存在多个版本，并使用单调递增的事务ID或时间戳。 ⏱ 2022-10-01 14:46:34
📌 MVCC区分已提交和未提交的版本，对应于已提交和未提交事务的值的版本。最后提交的值的版本也就是值的当前版本。 ⏱ 2022-10-01 14:46:50
📌 时间戳排序是最简单的悲观（无锁）并发控制方案之一，其中每个事务都有一个时间戳，事务操作能否执行取决于是否已经提交过时间戳更晚的事务。 ⏱ 2022-10-01 14:48:05
📌 基于锁的并发控制方案是悲观并发控制的一种形式，它对数据库对象显式地加锁，而不是用时间戳排序之类的协议来制定操作的顺序。 ⏱ 2022-10-01 14:48:51
📌 是两阶段锁（2PL） ⏱ 2022-10-01 14:49:07
📌 最简单的处理死锁的方法是引入超时机制并中止长时间运行的事务 ⏱ 2022-10-01 14:49:40
📌 死锁检测通常是用等待图（waits-for graph）实现 ⏱ 2022-10-01 14:49:55
📌 在事务处理过程中，保护逻辑和物理数据完整性的机制有所不同。负责逻辑和物理完整性的两个概念分别是锁（lock）和闩锁（latch）。 ⏱ 2022-10-01 14:51:26
📌 因为这里说的闩锁在系统编程中通常称为锁，但在本节中我们将阐明它们的区别和含义。 ⏱ 2022-10-03 17:39:21
📌 锁通常在树实现之外进行存储和管理，它表示一个较高层级的概念，由数据库的锁管理器管理。 ⏱ 2022-10-02 17:19:20
📌 一个通用的规则是尽可能缩短持有闩锁的时间（即只在读取或更新页时）以提高并发性。 ⏱ 2022-10-02 17:19:50
📌 读写锁允许多个读操作同时访问该对象，而只有写操作（通常相对较少）必须获得对该对象的排他性访问。 ⏱ 2022-10-03 17:41:51
📌 忙等（busy-wait）算法。忙等算法允许线程等待一小段时间，而不是将控制权直接交还给调度器。 ⏱ 2022-10-03 17:42:40
📌 闩锁耦合是一种非常简单的方法：它允许持有闩锁的时间更短，并在当前操作明显不再需要它们时立即释放。在读取路径上，一旦找到子节点并获得它的闩锁，就可以释放父节点的闩锁。 ⏱ 2022-10-03 17:44:00
📌 闩锁升级（latch upgrading）。这种方法沿着搜索路径获取共享锁，并在必要时将其升级为排他锁。 ⏱ 2022-10-03 17:45:44
📌 写操作一开始仅在叶节点上获取排他锁。如果叶节点需要分裂或合并，则沿着树向上，将父节点的共享锁升级为排他锁，从而获得树上受影响部分（即那些也要被分裂或合并的节点）的排他所有权。 ⏱ 2022-10-03 17:48:04
📌 Blink树构建在B*树的基础上（参见4.4节）并添加了高键（参见4.1.4节）和同级链接（sibling link）指针[LEHMAN81] ⏱ 2022-10-03 17:48:33
📌 Blink树允许存在所谓的半分裂状态，这时该节点已被同级指针引用，但没有被上一层的子节点指针引用。通过检查节点高键，可以识别出半分裂状态。 ⏱ 2022-10-03 17:50:40
6.1 写时复制
📌 有些数据库并不构建复杂的锁机制，而是使用写时复制（copy-on-write）技术来保证并发操作时的数据完整性 ⏱ 2022-10-03 17:59:01
📌 旧版本的树对于与写入者并发的读取者而言仍然是可访问的，而访问修改后的页的写入者必须等待之前的写操作完成 ⏱ 2022-10-03 18:00:19
6.4 FD树
📌 另一种方法是通过使用仅追加存储和合并过程将不同节点的更新归并在一起，这一想法也启发产生了LSM树 ⏱ 2022-10-03 18:15:51
读书笔记
2.2.2 固态硬盘
划线评论
📌 只写完整的块并将后续写操作组合到同一个块中，可以帮助减少所需的I/O操作的数量。 ^15826765-7CF8mqrmx - 💭 针对ssd优化的关键点 - ⏱ 2022-09-30 19:49:24
5.2.3 steal和force策略
划线评论
📌 撤销和重做 ^15826765-7CGirwDXL - 💭 undo和redo - ⏱ 2022-10-01 14:10:01