【数据库系统】课程笔记 - part 2

· · 算法·理论

写在前面：

成绩 93/100，绩点 4.8。

由于 db 的笔记有点太多了（12 个 md 文档加在一起有 122K），因此将其按顺序均分为 3 个部分，每个部分包含 4 个 Lecture。

注：Lecture 1 为导论课，Lecture 7 为期中考试复习课，因此没有记录笔记。

另注：我已经尽可能写的详细了，但仍不保证知识点覆盖完全。

【数据库系统】课程笔记 - part 1：https://www.luogu.com.cn/article/47sozboa

【数据库系统】课程笔记 - part 2：https://www.luogu.com.cn/article/xcqqbg8c

【数据库系统】课程笔记 - part 3：https://www.luogu.com.cn/article/fk3j2hgg

Lecture 6 - Relational Database Design

First Normal Form（一范式）

一个 domain 被称为原子性的 (atomic)，如果其包含的信息是不可再分的。

如果一个关系模式 R 的所有属性的 domain 都是原子性的，则称 R 满足一范式 (first normal form)。

对于关系型数据库，需要所有的关系模式都满足一范式。

对于不满足原子性的 domain，可以进行一些改造：

Pitfalls in Relational Database Design

一个优秀的关系型数据库需要我们找到一些 “好” 的关系模式，那么什么样的关系模式是不好的：

接下来介绍如何将不好的关系模式变为好的。

Decomposition

最主要的方法就是分解，例如将 (ABCD) 这张表分为 (AB) 和 (BCD) 两个部分，其中，分解需要满足两个要求：

Functional Dependencies（函数依赖）

设 R 为一个关系模式，\alpha,\beta 为两个 R 的属性集（\alpha\subseteq R,\beta\subseteq R）。

如果对任何 R 上的关系实例 r，对 r 中的任意两个不同的元组 t_1,t_2，如果 t_1[\alpha]=t_2[\alpha]，则 t_1[\beta]=t_2[\beta]，则称：

并写作：\alpha\rightarrow \beta。

由以上定义不难得到：

Definition of Trivial and Non-Trivial Dependency

有一些函数依赖关系是平凡的 (trivial)，这些关系是显然成立 的，例如：A\rightarrow A,AB\rightarrow A。

换言之，如果 B\subseteq A，那么 A\rightarrow B 就是平凡的，否则是非平凡的。

Closure of a Set of Functional Dependencies

首先是逻辑导出 (logically imply)：显然由 A\rightarrow B,B\rightarrow C 可以推出 A\rightarrow C。

接下来定义函数依赖集 F 的闭包 (closure) F^+ 为：包含所有可以被 F 逻辑导出的函数依赖集合

Armstrong’s Axioms

给出一些公理，用于求解闭包：

这三条定律是完备的 (complete) 和 保真的 (sound)，它们可以精确地得到所有函数依赖（不重不漏不多）

为了方便使用，引申出一些二级公理来加速求解：

那么最暴力的寻找闭包的方法就是：

显然最坏情况下会有 (2^n)^2 条函数依赖，因此求解 F^+ 有时是不可接受的。

Closure of Attribute Sets

属性集的闭包就比函数依赖集的闭包要更容易求一些。

给出属性集 a，函数依赖集 F，定义 a 在 F 下的闭包 a^+ 为所有在 F 下由 a 直接或间接决定的属性集合。

那么：

上图是一个例子。

Canonical Cover（正则覆盖）

显然，一些函数依赖集中是存在冗余的，因此定义 F 的正则覆盖 F_c 是一个最小的（无多余的函数依赖，函数依赖中无多余的属性）函数依赖集，满足 F,F_c 等价。

那么 F_c 中所有函数依赖的左侧都是不同的，因为 A\rightarrow B,A\rightarrow C 可以合并为 A\rightarrow BC。

如何找出正则覆盖：

上图是一个求解正则覆盖的例子。

Decomposition

在一些情况下，一个关系模式 R 可能是不太好的，因此需要将其分解为若干个关系模式 R_1,R_2,\cdots,R_n，并满足：

无损连接分解

定理：设 R 的函数依赖集为 F，则将 R 分解为 R_1,R_2 是无损连接分解当且仅当在 F^+ 中二者至少满足其一：\{R_1\cap R_2\}\rightarrow R_1 或 \{R_1\cap R_2\}\rightarrow R_2（即两个子模式的共同属性必须是 R_1 或 R_2 的码）。

依赖保持

定理：将 R 分解为 R_1,R_2,\cdots,R_n 满足依赖保持，当且仅当：

那么 (F_1\cup F_2\cup \cdots\cup F_n)^+=F^+。

BCNF / 3-NF

将在之后介绍。

一个例子

例如 R=(A,B,C),F=\{A\rightarrow B,B\rightarrow C\}，那么：

下图给出了一个判定 \alpha\rightarrow \beta 在分解后是否保持的算法：

不断地从 \alpha 开始拓展，中间的 \alpha^+ 指的是在 R_i 这个范围内能推出的属性范围，不断更新上去即可（缩进似乎有问题），最后对所有的 \alpha\rightarrow \beta 都进行一次判定，如果都能保持则这个分解也满足依赖保持。

Boyce-Codd Normal Form

称一个关系模式 R（有函数依赖集 F）是满足 BC - 范式的，当且仅当：

那么 R 是否满足 BC - 范式检查起来也比较简单，只需要检查 F 中的所有 \alpha\rightarrow \beta 即可（无需检查 F^+ 中的所有）。

但如果要检查分解式是否满足 BC - 范式，则必须检查 F^+ 中的所有函数依赖。

一个分解算法

其思想为：每次找到一条 R_i 中违反 BCNF 的函数依赖 \alpha\rightarrow \beta，然后将 R_i 拆分为 (\alpha,\beta) 和 R_1-\beta，这样显然是无损连接分解（因为公共部分 \alpha 是 (\alpha,\beta) 的超码），不断重复这个过程，可以得到满足无损连接分解和满足 BCNF 的分解式，但 依赖保持可能无法满足。

换言之，满足 BCNF，满足无损连接分解，满足依赖保持三个条件可能无法同时成立。

Third Normal Form

BCNF 的限制太强，以至于可能无法满足依赖保持，因此设计了一种限制稍微弱一点的范式，即 3 - 范式。

称一个关系模式 R（有函数依赖集 F）是满足 3 - 范式的，当且仅当：

那么显然如果满足 BCNF 则一定满足 3 - NF，同时这里的第三个条件是为了能保证依赖保持做出的最低程度的弱化。

与 BCNF 类似，R 是否满足 3 - NF 也只需要检查 F 中的函数依赖即可。

判断一个关系是否满足 3 - NF 是 NP-hard 的（因为需要计算所有候选码），但进行 3 - NF 的分解是存在多项式复杂度的算法的，下面是一个例子：

这样，一定可以得到一个满足 3 - NF，满足无损连接分解，满足依赖保持的分解式。

Multivalued Dependencies

有时在满足 BCNF 的情况下依然会产生冗余，即多值依赖 (Multivalued Dependencies)。

下面是多值依赖的定义：

称两个属性 A,B 满足多值依赖 A→→B（A 多值决定 (multi-determine) B），当且仅当：

换言之，只要属性 A 的值相同，则 B,R-A-B 两部分的值可以任意取。

Fourth Normal Form

引入 4 - 范式，称一个关系模式 R（有函数依赖集和多值依赖集 D）是满足 4 - 范式的，当且仅当：

分解方法和 BCNF 的分解方法相同。

Lecture 8 - Storage and File Structure

Review

先对之前介绍过的一些内容进行回顾。

Storage Manager

存储管理器 (storage manager) 是一个程序模块，它在数据库中存储的底层数据，与提交给系统的应用程序和查询之间提供了接口。

其负责两项核心的内容：

并且其包含以下几个子模块：

Query Processor

询问处理器包括：DDL interpreter, DML interpreter, query processing，其主要功能为 转义 (parsing and translation)，优化 (optimization)，执行 (evaluation)。

这两个东西的整体结构如下图所示：

Overview of Physical Storage Media

在物理层面上，数据最终都存储在文件中，不同数据库系统有各自的文件格式，例如 .mdf/.ldf，.ora，.dbf 等等。

不同的存储介质可以用不同的方式进行分类：

如果按照可靠性分类，则有：

如果按照访问速度分类，则有：

Magnetic Disks

首先给出一张机械硬盘的结构示意图：

解释一下这张图中的各个部分：

那么不难得到读写一个扇区的方式：

一个硬盘通常包含 4\sim 16 个盘片，固定在同一主轴上同步旋转；每个盘片的每一面都有一个读写头，所有读写头都安装在同一个公共的磁盘臂上，同步移动。

柱面 (cylinder) 是指所有盘片上编号相同的磁道，那么显然同一柱面内的数据读写无需移动磁盘臂，效率更高。

磁盘控制器 (disk controller) 是主机与硬盘硬件之间的接口，主要负责：

磁盘传输率 (data-transfer rate) 指的是磁盘在找到数据后，传输数据的速率，典型机械硬盘的最大传输速率约为 25\sim 100\rm MB/s，外圈磁道传输速率更高（周长更长，单位时间能扫过更多扇区）

平均故障时间 (mean time to failure, MTTF) 指的是磁盘连续工作不出问题的平均时间，典型的机械硬盘的 MTTF 在 3 至 5 年，并且随着硬盘使用时间增长而逐渐降低。

Optimization of Disk-Block Access

  1. 磁盘块 (block)：一个磁道上的连续若干个扇区组成的一个整体，在硬盘和内存进行数据传输时，以一个 block 为一个基本单元，通常一个 block 的大小在 512\rm B 至几 \rm KB。

  2. 设计一些算法优化磁头的移动路径，例如电梯算法 (elevator algorithm)。

  3. 文件组织 (file organization)：根据数据访问的模式来规划 block 的存储位置，从而减少访问时间。

  1. 非易失性写缓冲区 (Nonvolatile write buffers)：在进行磁盘写入时，不直接写磁盘，而是先被立即写入到非易失性 RAM 缓冲区（系统立刻就能确认写入完成，无需等待磁盘的机械操作），接着磁盘控制器会在磁盘空闲时，再把缓冲区里的数据批量写入磁盘。同时，缓冲区可以暂存多个写请求，然后按照电梯调度算法重新排序，减少磁盘臂移动距离。
  2. 在软件方面，也有日志盘 (log disk) 这种技术，实现起来类似非易失性 RAM。

RAID

RAID 的全称为独立磁盘冗余阵列 (Redundant Arrays of Independent Disks, RAID)，它是一种磁盘组织技术：

冗余 (redundancy)：存储额外的信息，当某块磁盘发生故障时，可以利用这些额外信息重建丢失的数据，避免数据丢失

典型实现之一：磁盘镜像 (mirroring/shadowing)

磁盘系统并行性的两大目标：提升吞吐量；降低相应时间

RAID Levels

RAID 0

块级条带化存储，无任何数据冗余备份，数据被拆分分散写到多块磁盘。

特点：读写并行度最高、性能最强，但只要任意一块磁盘故障，对应数据就会永久丢失。

适用场景：高性能优先、数据丢失风险可接受的业务，比如临时缓存、可重新生成的非核心数据存储。

RAID 1

磁盘镜像，每一份数据都完整存放在两块互为镜像的磁盘中。

之前已经介绍过了，不再复述。

RAID 2

采用比特级数据拆分，借鉴内存的 ECC（错误纠正码）机制，把数据按位分散到多块数据盘，同时用多块专用磁盘存储 ECC 校验码来实现错误纠正。

RAID 3

只需要 1 块专用奇偶校验盘就能完成错误纠正，且系统能定位故障磁盘。

写入数据时：同步计算对应奇偶校验位，写入专属校验盘

磁盘故障恢复：对其余所有正常磁盘（含校验盘）的比特做异或运算，就能还原故障盘丢失的数据。

RAID 3 可以实现 RAID 2 全部的容错收益，但只需要 1 块校验盘，硬件成本更低，直接替代了 RAID 2 的应用场景。

RAID 4

采用块级条带化存储，将数据按块分散存储在 n 块数据盘上，同时用一块独立的专用磁盘存储所有对应数据块的奇偶校验块。和 RAID 3 有点类似，但拆分方式不同。

读操作优于 RAID 3，但是写操作极差，因此基本被淘汰。

RAID 5

RAID 5 是 RAID 4 的改进版，采用分布式奇偶校验：不再把校验块集中存放在单块盘上，而是将数据块和奇偶校验块分散存储在所有 n+1 块磁盘中。

其解决了 RAID 4 的写瓶颈：由于校验块分散在不同磁盘上，多个写请求可以并行处理，避免了单块校验盘成为性能瓶颈。

RAID 6

在 RAID 5 的基础上，存储两份独立的校验信息，这意味着阵列中可以承受两块磁盘同时故障，仍能通过两份校验信息恢复数据，但相应地磁盘利用率进一步降低。

因此，RAID 6 主要用于对数据安全性要求极高的场景，应用不如 RAID 5 广泛。

Choice of RAID Level

选择 RAID 级别需要考虑的因素有：成本，正常性能，故障时性能，重建性能。

因此主要的选择在 RAID 1 和 RAID 5 之间，而这两者的选择：

Hardware Issues

上述内容都是硬件层面的 RAID，也有软件层面的 RAID，其完全由操作系统软件实现，没有专用硬件支持，但会占用主机 CPU 资源，性能和可靠性依赖于系统。

硬件 RAID 也会有一些问题，例如断电可能导致数据损坏，在这种情况下，系统恢复供电后，必须能检测到损坏的数据并修复它。

Storage Access

数据块 (block)：数据库文件会被逻辑上划分为固定长度的存储单元，也就是块 (Block)，它同时是数据库系统中存储分配和数据传输的基本单位。

缓冲区 (buffer)：缓冲区是主存 (RAM) 中用来存放磁盘块副本的一块区域。

由于磁盘访问速度远低于（大约 10^6 倍）内存访问速度，因此数据库系统的核心优化目标就是最小化磁盘和内存之间的块传输次数：尽量把常用的数据块留在内存缓冲区里，让 CPU 直接从内存读写。

这里对三个概念做一个区分：

在这里近似认为 page = block。

缓冲区管理器 (buffer manager)：负责在主存中分配、管理缓冲区空间的子系统。它要解决的核心问题是：缓冲区的大小是有限的，当缓冲区被占满、又需要加载新的磁盘块时，需要用特定的替换策略（如 LRU（最近最少使用）, MRU（最近最多使用）, Clock 等算法）来决定哪些块需要被 “淘汰” 写回磁盘。

这里再引入 pin ("钉住") 的概念：

File Organization

整个数据库以文件 (file) 的形式存储，每个文件以若干个记录 (record) 构成，每个记录有一系列的域 (field)（即各个属性）。在实际应用中，存在定长记录 (Fixed-length record) 和不定长记录 (Variable-length record) 两种存储方式。

Fixed-Length Records

优点是实现起来非常容易，第 i 个 record 的起始位置就是 n\times (i-1)，其中 n 是单个 record 的大小。

但注意可能出现一个 record 横跨两个 block 的情况，因此需要作出修改，禁止这种情况出现。

删除（假设是第 i 个）record 的方法：

Variable-Length Records

变长记录的出现有以下几种原因：

每个变长记录有两个部分：<offset,length> 和实际内容，其中 offset,length 分别指定了实际内容在文件中的开始位置和长度。

这种存储方式被称为 slotted page structure，它包含两个部分：

那么在删除的时候就可以移动这些存储的数据（同时也要修改 offset），来填补形成的空位。同时指针不应该直接指向 record 的数据，而是应该指向在 header 中的标识。

Organization of Records in Files

文件组织形式有以下几种：

Lecture 9 - Indexing and Hashing

Basic Concepts

为什么我们需要索引 (index)：避免全表扫描，具体来说可以类比字典中的目录，可以根据偏旁部首来快速地找到需要的汉字，而不用把整本字典翻一遍。

索引的相关性质：

Ordered Indices

顺序索引 (ordered indices)：有序索引中的索引项按 search-key 排序存储

顺序文件 (sequentially ordered file)：数据文件本身也是按 search-key 排序的

主索引 (primary index)：主索引的 search-key 与顺序数据文件的排序字段完全相同，通常但不一定是主码（只需要有序就可以了），同时，主索引也可以被称为聚集索引 (clustering index)，这是因为相邻的索引在物理存储上也在相邻的位置。另外，非顺序文件不存在主索引。

辅助索引 (secondary index)：辅助索引的 search-key 顺序与数据文件的物理排序方式不同，因此也被称为非聚集索引 (non-clustering index)，在辅助索引上进行扫描的开销是非常大的，因为可能涉及很多的磁盘 IO，产生这种索引是因为用户可能需要对其他的属性进行筛选。

数据删除

对于删除的情况，首先删除数据库表中的对应内容，接着更新索引的方式如下。

如果是稠密索引
如果是稀疏索引（那么它就不可能是辅助索引）

上面说的是对于一层的索引，多层索引就每一层套用同样的做法即可。

数据插入

对于插入的情况，先根据索引找到插入的位置，然后更新索引的方式如下。

如果是稠密索引
如果是稀疏索引

多层索引的情况同理。

B+ - Tree Index Files

这部分介绍数据库系统中的 B+ 树，它可以用来管理顺序索引，下面先给出一个例子：

接着给出 B+ 树的一些性质（这里的 B+ 树和 ADS 中的 B+ 树基本是相同的）：

B+ 树节点的结构

一个典型的 B+ 树结构如下，其中 K_i 为 search-key 的具体的值，P_i 为指向子节点或 bucket 或物理地址，同时需要保证 K_i 随 i 增大而严格增大

B+ 树叶节点

将所有叶节点中的 K_i 顺次拼接则可以按顺序得到所有的 search-key，同时 P_n 指向下一个叶节点，这样在顺序扫描的时候会方便许多。

每个叶节点都有 \lceil (n-1)/2\rceil\sim n 个值。

B+ 树非叶结点

这里夹在 K_i 和 K_{i+1} 中的 P_{i+1} 表示其中的所有 search-key 的值都在 [K_i,K_{i+1}) 之间，同时每个内部节点都有 \lceil n/2\rceil\sim n 个儿子，根节点需要特殊讨论，但这里暂且不提。

所有非叶结点构成了一个多层索引。

那么如果一共有 m 个索引，则整个 B+ 树的高度不会超过 \lceil \log_{\lceil n/2\rceil}(m)\rceil。

下面再给出一个例子：

B+ 树上的操作

查询

比较简单，不作介绍

插入

先在树上进行一次查询找到需要插入的叶节点，如果还有空位则直接插入即可。

否则，需要进行分裂，左侧大小为 \lceil n/2\rceil，右侧为剩余的元素，此时需要在父节点处插入一个新的 K_i，如果父节点有空位则直接插入即可，否则需要对父节点进行分裂。

注意，这里和 ADS 中的定义不同，因为指针的个数比元素个数多一个：

例如 n=4，此时有两层结构：

再插入一个 10 则会导致叶节点分裂，同时上一层也需要分裂：

这张图片展示的是叶子结点分裂，父节点还未分裂的情况，一般的 B+ 树会将父节点分为两半，一边是 3,5 另一边是 7,9，但由于这里指针个数多一个，因此左侧部分实际上只需要一个 9 就可以了：

更上一级的情况不再重复展示。

或者使用课件里的例子，其实是一样的：

删除

与插入相反，可能会涉及到节点的合并，这里不再展开。

B - Tree Index Files

简而言之，课件中描述的 B 树与 B+ 树的核心区别就是：

这就导致了 B 树的树高会小一点，但插入删除等操作会变得复杂很多，总体来说不如 B+ 树。

Static Hashing

这部分介绍一下静态哈希 (static hashing)：

注意到实际操作的复杂度开销与一个桶中的指针个数相关，因此哈希函数需要让 search-key 的映射值尽可能均匀分布。

同时还有另一个问题：桶溢出，在数据库系统中，解决这个问题的常用方法是加一个桶，连接到溢出的桶之后，如下图：

再区分一下 Hash File Organization 和 Hash Index，前者是使用哈希方法直接进行数据存储，在桶中存放的就是数据；而后者属于索引，在桶中存放的是指针。

静态哈希中，桶的数量固定不变，因此随着表中数据的增加，一定会使 bucket 越来越满或者发生 overflow，从而导致整体操作效率降低。

Dynamic Hashing

使用动态哈希的方法可以有效处理上面静态哈希的一些缺陷。

动态哈希的核心思想就是先通过哈希函数生成一串较长的 01 序列，然后截取若干高位作为真正的哈希值，这里截取的长度可以动态调整，从而可以动态控制哈希辨别的灵敏度。

具体来说：

因此在插入时发生了溢出：

Write-optimized indices

Log Structured Merge (LSM) Tree

现在只考虑插入和查询操作，为了尽量降低磁盘操作的开销，引入 LSM Tree：

每个 L_i 都是一个数据结构（例如红黑树，跳表等），L_0 在内存中而 L_i 都在磁盘中，每个 L_i 都有一个设定的大小，其中 L_0,L_1 大小相同，之后每个大小翻倍。

初始插入的数据都放入 L_0 中，每次 L_i 满了的时候，都会与 L_{i+1} 进行归并，这样所有归并都是统一的顺序写磁盘，效率比较高，同时均摊复杂度也没有问题。因此，LSM 树比较适用于写密集系统。

但需要注意这种结构的删除和修改比较困难，同时查询也需要在多个数据结构中寻找，效率也有所降低。

Lecture 10 - Query Processing

Basic Steps in Query Processing

先介绍一下数据库进行操作的基本步骤：语义分析 - 优化 - 执行（这里 Evaluation 并非评估而是执行的意思）

这里 Optimization 中确定哪种方案更优，就需要对不同的方案进行评估，通过设置合适的代价函数来进行计算：

Measures of Query Cost

使用 cost 来估计整个查询所需要的时间，具体包含三个部分：

其中磁盘访问时间占大头，因此主要分析这部分（在实际软件中另外的部分也是被计入的）。

为方便起见，假设：

Selection Operation

先来考察 select 语句的代价如何估计。

Algorithm 1：线性扫描

在不使用索引的前提下对整个数据库表进行线性扫描，一次测试每条数据是否满足 select 条件，这样：

因此估计的代价为 t_S+b_r\times t_T。

这种算法是最暴力的，对所有的 select 条件/数据存储顺序/是否有索引 的情况都适用。

Algorithm 2：二分查找

在进行等值查找的时候可以使用二分的方式来加速（例如 select score=60 这种）

那么整个过程分成两个部分：

Algorithm 3：使用主索引查找唯一值，等值查找

如果需要查找一条满足条件的数据，那么代价为：

Algorithm 4：使用主索引查找重复值，等值查找

此时可能有多条数据都满足条件，那么就是 h_t\times(t_S+t_T)+t_S+b\times t_T，这里 b=\lceil sc(A,r)/f_r\rceil 就是预估的满足条件的块个数。

Algorithm 5：使用辅助索引查找重复值，等值查找

首先在索引树上定位查找的内容，这部分代价也是 h_i\times (t_T+t_S)。

但是由于辅助索引内容和实际数据存储顺序可能不同，因此在最坏情况下会有 n\times (t_T+t_S) 的代价（其中 n 为满足条件的数据个数），这是因为每次寻找都需要一次寻道和块传输，因此可能会劣于线性扫描。

上图就是一个例子，在 balance 上有一个辅助索引，但是原始数据文件中 balance 是乱序的，那么就可能导致每次查找都需要一次寻道和块传输。

范围查询的情况

和等值查询差不多，如果是 \ge x 的查询则先找到 x 然后线性扫描之后的数据即可，如果是 \le x 的查询则直接从头开始扫描即可（这种情况不需要索引）

使用主索引和辅助索引的情况和上面基本是相同的，辅助索引仍然可能开销巨大。

Sorting

需要用到排序的情况通常有：

同时，如果整个表可以被放入内存，那么诸如快速排序等排序算法可以高效地解决，否则需要外部排序等技术。

快速排序不作介绍，因为内存中的操作都比较快，这里主要分析外部排序：

外部排序

设内存中一共有 M 个 page，那么：

代价分析

Join Operation

这里介绍五种不同的连接方法。

Nested-Loop Join 嵌套循环连接

其伪代码为：

for each tuple t_r in r do
    for each tuple t_s in s do
        test (t_r,t_s) and add t_r*t_s into the result

那么，在最坏情况（内存只能容纳每个表的 1 个 block）下：

最好情况下（s 表更小且全部始终处于内存中）

Block Nested-Loop Join

其伪代码为：

for each block B_r in r do
    for each block B_s in s do
        for each tuple t_r in B_r do
            for each tuple t_s in B_s do
                test (t_r,t_s) and add t_r*t_s into the result

那么同样在最坏情况下：

最好情况下（s 表更小且全部始终处于内存中）

中间情况（一共可以容纳 M 个块，其中 M<b_r,M<b_s），那么分配一个块给输出，一个块给内循环，M-2 个块给外循环，这样可以将 b_r 进一步优化到 \lceil b_r/(M-2)\rceil：

Indexed Nested-Loop Join

如果 join 为等值连接或者自然连接，同时内表有连接项上的索引，那么可以用索引优化寻找可以连接的 pair 的时间。

估计总代价为 b_r(t_S+t_T)+n_r\times c，其中 c 为遍历索引并取出所有匹配的 tuple 的时间。

Merge-Join 排序归并连接

只能用于等值连接或者自然连接，并假设两个表已经针对排序项排好序了。

具体的连接方式和二路归并基本相同，需要 b_r+b_s 次 block transfer 和 \lceil b_r/b_b\rceil+\lceil b_s/b_b\rceil 次 seek。

如果初始时无序的，则需要再加上排序的代价。

Hash-Join 哈希连接

只能用于等值连接或者自然连接，使用哈希函数将所有的 tuple 分成若干类，只有在同一类中的 tuple 才可能连接上。

代价分析

（*看不太懂）

Other Operations