CS186 笔记01

数据库管理系统 (DBMS) 总体架构

是什么 (What it is)

DBMS 架构是一个分层的软件系统，负责将用户的高级数据请求（如 SQL）转化为对物理存储设备的底层操作。它像一个精密的工厂，每一层都有明确的分工。

为什么 (Why it's needed)

直接操作磁盘是极其复杂和低效的。一个分层的架构可以将复杂的问题分解，每一层专注于解决特定的问题（如查询解析、并发控制、内存管理、磁盘 I/O），从而实现关注点分离。这使得 DBMS 的设计、实现和维护变得更加模块化和高效。

怎么做 (How it works)

一个典型的 DBMS 从上到下可以分为以下几个核心层次：

查询处理层 (Query Processing)
- 查询解析与优化 (Parser & Optimizer): 接收用户发起的 SQL 查询，将其解析成内部的语法树，并生成一个最高效的查询执行计划（Query Plan）。例如，决定是使用索引扫描还是全表扫描，以及多表连接的顺序。
- 关系操作符 (Relational Operators): 真正执行查询计划的组件。它包含一系列操作，如表扫描、索引扫描、连接 (Joins)、分组 (Grouping)、排序 (Sorting) 等。
存储管理层 (Storage Management)
- 文件与索引管理 (File & Index Management): 负责将表、记录等逻辑概念组织成逻辑文件中的页面集合。它提供了“按记录ID查找”、“插入记录”等抽象接口给上层使用。
- 缓冲区管理 (Buffer Manager): 这是性能优化的核心。它在内存中开辟一块称为 缓冲池 (Buffer Pool) 的区域。所有的数据操作（读、写、修改）都只在内存的缓冲池中进行，为上层制造了“数据总是在内存里”的假象。当上层需要一个页面时，它会：
  - 如果页面已在缓冲池中，直接返回。
  - 如果不在，就调用下一层的磁盘空间管理器，从磁盘加载页面到缓冲池。
- 磁盘空间管理 (Disk Space Manager): 这是与物理存储交互的最底层。它负责将“页面”的逻辑地址翻译成磁盘上的物理扇区地址，并执行实际的 I/O 读写操作。
跨层服务 (Cross-Layer Services)
- 并发控制 (Concurrency Control): 使用锁机制 (Locking) 或多版本并发控制 (MVCC) 等技术，确保多个事务同时访问数据时不会产生冲突和数据不一致的问题。
- 恢复 (Recovery): 通过预写日志 (Write-Ahead Logging, WAL) 等机制，确保在系统断电或崩溃后，数据库能够恢复到一致的状态，保证数据的持久性。

核心抽象：页面 (Page)

是什么 (What it is)

页面 (Page)，也常被称为 块 (Block)，是 DBMS 进行磁盘 I/O 的最小单位。数据库在逻辑上被看作是一个巨大的页面数组。一个数据库文件由一系列页面组成，一个页面又由一系列记录组成，构成了 文件 -> 页面 -> 记录 的存储层次。

为什么 (Why it's needed)

磁盘 I/O 是数据库中最昂贵的操作之一，其耗时主要在寻道和旋转延迟上，而非数据传输本身。如果每次只读写一条记录（几十或几百字节），那么大部分时间都会浪费在 I/O 的固定开销上。

通过以 页面（通常为 4KB, 8KB, 16KB） 为单位进行读写，DBMS 可以：

摊销 I/O 开销: 一次 I/O 读取更多有效数据，大大提高吞吐量。
利用局部性原理: 当访问一条记录时，其物理上相邻的记录很可能也即将被访问。将它们一次性读入内存，可以减少未来的 I/O 次数。

页面大小如何选择 (How to choose Page Size)

页面大小的选择是一个权衡，通常与底层硬件和操作系统紧密相关。

匹配操作系统页面: 现代操作系统也以页（通常是 4KB）为单位管理内存。将 DBMS 页面大小设为操作系统页面大小的整数倍，可以简化内存映射，减少内存拷贝和碎片，并有助于减少 TLB (Translation Lookaside Buffer) Miss，从而加速内存访问。
优化磁盘 I/O: 页面大小通常是磁盘物理块大小的倍数。较大的页面可以摊薄单次 I/O 的寻道成本，但如果页面过大，又可能在查询只需少量数据时，浪费 I/O 带宽和内存来加载不必要的数据。
影响数据结构效率: 对于 B+树这样的索引结构，更大的页面意味着每个节点可以容纳更多的子节点指针（即更高的扇出 fan-out），这可以降低树的高度，从而减少遍历索引时所需的 I/O 次数。

文件组织 (File Organization)

是什么 (What it is)

文件组织是指数据库中的记录如何在页面中以及页面如何在文件中进行排列和管理的方式。

为什么 (Why it's needed)

不同的文件组织方式适用于不同的数据访问模式。选择合适的组织方式是查询性能优化的基础。例如，有些场景需要快速插入，有些则需要按特定顺序快速检索。

怎么做 (How it works)

主要的组织方式有以下几种：

无序堆文件 (Unordered Heap Files)
- 是什么: 记录被插入到文件中的任何有可用空间的页面中，没有特定的顺序。
- 怎么做: 为了管理空闲空间，通常不使用低效的链表，而是采用 页面目录 (Page Directory) 的方式。
  - DBMS 维护一个或多个特殊的 头页面 (Header Pages)。
  - 每个头页面包含一个条目数组，每个条目指向一个数据页，并记录该数据页的 剩余空闲空间。
  - 当需要插入一条新记录时，DBMS 只需扫描（通常已在内存中的）头页面，就能快速定位到一个有足够空间的页面，而无需遍历所有数据页。
- 优点: 插入速度非常快。
- 缺点: 查找记录（除了通过记录ID）必须进行全文件扫描，效率低下。
排序文件 (Sorted Files)
- 是什么: 所有记录按照某个（或某几个）字段的值进行排序存储。
- 优点: 对于基于排序键的范围查询（如 WHERE age > 30）和排序操作非常高效，可以使用二分查找等算法快速定位。
- 缺点: 插入和删除操作非常昂贵，因为可能需要移动大量记录来维持顺序。
索引文件 (Index Files)
- 是什么: 一种独立于数据文件的辅助性数据结构，其目的是为了加速数据检索。最常见的就是 B+树。
- 怎么做: 索引文件中存储着（键值，记录ID）对。当根据某个键值查询时，DBMS 可以通过高效遍历索引（如 B+树）快速找到对应记录的记录ID，然后用该 ID 直接定位到数据记录。
- 优点: 极大地提升了基于索引键的查询性能。

页面布局 (Page Layout)

是什么 (What it is)

页面布局定义了单张页面内部的记录是如何组织的。它直接关系到如何通过记录ID（Record ID）定位记录，以及如何管理页面内的空间。

为什么 (Why it's needed)

一个好的页面布局必须能够高效地：

支持固定长度和可变长度的记录。
在插入和删除记录后，保持记录ID的稳定，因为索引等外部结构会引用这些ID。
有效地管理和回收页面内的碎片空间。

怎么做 (How it works)

A. 固定长度记录的简单布局

紧密填充 (Packed):
- 做法: 记录一个挨一个紧密存放。记录ID可以是 (PageID, RecordNumber)。
- 问题: 删除一条记录后，为了保持紧密，必须移动其后的所有记录来填补空隙。这会导致这些记录的 RecordNumber 改变，从而使所有指向它们的外部引用（如索引）失效，维护成本极高。
非紧密填充 + 位图 (Unpacked with Bitmap):
- 做法: 页面头部维护一个 位图 (Bitmap)，每个位对应一个记录槽位（Slot），1 表示已占用，0 表示空闲。记录ID仍然是 (PageID, SlotNumber)。
- 优点: 删除记录时，只需将位图中对应的位从 1 改为 0 即可，无需移动任何数据。记录ID保持稳定，非常高效。

B. 可变长度记录的通用布局：槽页 (Slotted Page)

这是现代数据库系统中最常用、最优雅的解决方案，它同时也能很好地支持固定长度记录。

是什么: 一种在页面内部使用 槽目录 (Slot Directory) 来管理记录的布局。

怎么做 (布局结构):

<----------------------- Page (e.g., 8KB) ----------------------->
+------------------+---------------------+-----------------------+
| Page Header      | Records...          | Free Space...         | Slot Dir... |
| (NumSlots, etc.) | (Grow right ------>) | (<---- Grow left)     | (Slots)     |
+------------------+---------------------+-----------------------+
^ Page Start                                                Page End ^

为什么这样设计 (Why this design):
- 最大化空间利用: 这种“两端向中间增长”的设计，让连续的空闲空间最大化，可以容纳任意大小的新记录，直到空间被完全用尽。
- 稳定的记录ID: 记录ID被定义为 (PageID, SlotNumber)，即页面ID和它在槽目录中的索引。
  - 插入: 在空闲空间中放入新记录，并在槽目录中增加一个新槽指向它。
  - 删除: 只需将对应槽位的内容清空（或标记为无效），记录的物理数据暂时成为碎片，但其他记录的槽位号（即记录ID）完全不受影响。
  - 页面重组 (Compaction): 当碎片过多时，DBMS可以移动页面内的记录，将它们重新紧密排列，然后更新槽目录中受影响的偏移量指针即可。这个过程对外部是透明的，因为 记录ID (SlotNumber) 始终不变。

记录格式 (Record Format)

是什么 (What it is)

记录格式定义了单条记录内部的字段是如何被组织和存储的。

为什么 (Why it's needed)

记录格式的设计目标有两个核心：

存储紧凑: 节约磁盘空间和I/O带宽，尤其是在处理含有很多 NULL 值或变长字段的表时。
字段快速访问: 查询中最频繁的操作就是获取特定字段的值（例如 SELECT name FROM users WHERE id = 1），这个操作必须极快。

怎么做 (How it works)

A. 固定长度字段

做法: 所有字段类型固定（如 INT, CHAR(10), DOUBLE）。访问第 i 个字段的偏移量可以通过简单的数学计算 (起始地址 + 前 i-1 个字段的长度之和) 得出，速度极快。
问题: 对于 CHAR(10) 却只存了 "Hi" 两个字符的情况，会浪费8个字节。如果 NULL 值很多，空间浪费更严重。

B. 可变长度字段 (最佳实践：带头部的记录)

为了同时解决空间效率和访问效率问题，现代数据库普遍采用带 记录头 (Record Header) 的格式。

是什么: 在每条记录的实际数据之前，附加一小段元数据作为记录头。

怎么做 (记录头结构):

<-------------------------- Record -------------------------->
+--------------+------------------+---------------------------+
| Record Header| Fixed-Length     | Variable-Length           |
|              | Fields...        | Fields...                 |
+--------------+------------------+---------------------------+
| Null Bitmap  |                  |                           |
| Offset Array |                  |                           |
+--------------+                  |                           |

空值位图 (Null Bitmap): 一个位图，每个位对应一个字段。如果某位是 1，表示对应字段值为 NULL，记录中将不会为该字段存储任何数据。这极大地节省了空间。
偏移量数组 (Offset Array): 这是实现 快速访问 的关键。它是一个数组，存储了 每个变长字段 在记录数据区内的 起始偏移量。

偏移量数组的巨大优势 (Why Offset Array is great):
- O(1) 随机访问: 要访问第 i 个变长字段，DBMS 无需从头扫描记录。它直接读取记录头中的偏移量数组，获取第 i 个条目，就知道了该字段的准确起始位置。这是一种直接寻址，时间复杂度为 O(1)，效率极高。相比之下，使用分隔符（如 CSV）或在每个字段前存长度的方法，访问第 i 个字段需要扫描前 i-1 个字段，时间复杂度为 O(N)。

系统目录 (System Catalogs)

是什么 (What it is)

系统目录，也叫 数据字典 (Data Dictionary)，是数据库的元数据集合。它是一组特殊的系统表，用于存储关于数据库自身结构的所有信息。本质上，DBMS 使用自己的表来管理和描述自己。

为什么 (Why it's needed)

系统目录是 DBMS 的“大脑”和“地图”。当执行一个 SQL 查询时，DBMS 需要查询系统目录来：

验证表名、列名是否存在。
获取列的数据类型，以便进行类型检查和数据转换。
查找有哪些可用的索引，以帮助查询优化器选择最佳执行计划。
检查权限和完整性约束（如主键、外键）。

怎么做 (How it works)

系统目录中存储了丰富的信息，包括但不限于：

关于表 (Relations): 表名、表所属用户、文件存储位置、文件组织方式（如堆文件）。
关于列 (Attributes): 列名、数据类型、长度、是否允许为空。
关于索引 (Indexes): 索引名、所属表、索引类型（如 B+树）、构成索引的列。
关于视图 (Views): 视图名及其定义（即其背后的 SELECT 语句）。
其他信息: 用户和权限、数据库的统计信息（用于查询优化）、存储过程等。

例子:

在 PostgreSQL 或 MySQL 中，你可以通过查询 information_schema 下的表（如 information_schema.tables, information_schema.columns）来查看这些元数据。
在 SQLite 中，sqlite_master 表扮演了类似的角色。

文件组织 (File Organizations)

在数据库管理系统（DBMS）中，数据记录在磁盘上存储的方式被称为文件组织。它决定了数据是如何被物理排列和管理的。

为什么需要不同的文件组织方式？ 数据库系统面临着多样化的数据访问模式。没有一种“万能”的文件组织方式能够高效应对所有场景。例如，某些应用可能极其频繁地插入新数据，而另一些则需要快速检索按特定顺序排列的数据，或者高效执行某个值范围内的查询。不同的文件组织方式正是为了在这些不同的访问模式之间做出最优的权衡。理解这些内在的权衡是数据库系统设计的核心。

常见的几种文件组织方式：

堆文件 (Heap Files)：
- 是什么？ 堆文件是记录的无序集合。这意味着新记录会被添加到文件中任何有可用空间的页面中，记录之间没有预设的逻辑或物理顺序。
- 为什么有它？ 堆文件之所以存在，是因为它提供了最快速的记录插入能力。由于无需维护任何顺序，新数据可以被简单地追加到文件的末尾或第一个找到的空闲空间。当主要的数据访问模式是需要处理所有记录的全文件扫描（例如，对所有员工计算平均工资）时，堆文件也是一种简单有效的选择。
- 怎么做？ 在实现上，DBMS 通常不会使用简单的链表来连接页面（因为查找空闲空间会很慢）。取而代之的是，它会维护一个页面目录（Page Directory）。这个目录通常位于文件中的一个或多个特殊头页面里，每个目录条目会记录对应数据页面当前剩余的空闲空间大小。当需要插入记录时，DBMS 可以快速查询这个目录来找到有足够空间的页面。
排序文件 (Sorted Files)：
- 是什么？ 排序文件中的所有记录都根据一个（或几个）指定的搜索键字段进行物理上的严格排序存储。这意味着如果你按员工 ID 排序，ID 为 100 的员工记录会排在 ID 为 101 的员工记录之前，且它们尽可能地存储在相邻的页面中。
- 为什么有它？ 这种组织方式的主要优势在于它能极大地优化那些需要按特定顺序检索数据（如按产品名称列出所有产品），或者需要查询某个范围内记录（如“查找销售额在 1000 到 5000 之间的所有订单”）的场景。数据预先排序，可以显著加速这类查询，因为数据已经有序，可以直接读取而无需额外的排序步骤。
- 怎么做？ 维持排序文件的秩序需要付出代价。在插入新记录时，DBMS 必须首先找到它在文件中的正确排序位置，然后将新记录插入其中。这通常需要移动该位置之后的所有现有记录来为新记录腾出空间，这可能涉及多个页面乃至文件的很大一部分。类似地，删除记录后，为了保持紧凑和排序，也可能需要移动记录来填补空隙。
聚簇文件与索引 (Clustered Files & Indexes)：
- 是什么？ 这是一种更高级的文件组织或辅助数据结构，例如 B+ 树。它们通过将相关数据逻辑或物理地分组到存储块中，以实现更快的查找和更高效的修改。聚簇索引就是其中一个例子，它会决定数据行在磁盘上的物理存储顺序，确保物理相邻的数据在逻辑上也相邻。
- 为什么有它？ 它们旨在弥补堆文件查找效率低和排序文件修改开销大的不足，提供一个更优的折中方案，实现既能高效查询又能相对高效修改的平衡。

Ⅱ. 成本模型与分析 (Cost Model and Analysis)

为了能够定量地比较不同文件组织方式在实际操作中的性能差异，我们需要建立一个简化的成本模型。

为什么需要成本模型？ 数据库系统设计涉及复杂的权衡。一个量化的成本模型能够帮助我们：

量化比较：直观地比较不同数据操作方案的开销，例如“这个操作比那个快多少？”
优化依据：为 DBMS 内部的查询优化器提供选择最佳执行计划的依据，使其能够预测并选择最快的查询路径。
性能洞察：帮助我们深入理解各种文件组织方式的性能瓶颈和潜在的优化方向。

成本模型假设 (为了简化分析)： 在分析中，我们通常会引入以下简化假设，以便专注于核心趋势而不过于纠缠于细节：

B：文件中的数据块（或页面）的总数量。
R：每个数据块中可以存储的记录数量。
D：平均读取或写入一个磁盘块所需的时间。这个参数代表了一次磁盘 I/O 操作的平均成本。
关注点：我们的分析将主要集中在平均情况下的磁盘 I/O 成本，因为磁盘 I/O 通常是数据库操作中最耗时的部分。
忽略项：为了简化，我们暂时不区分顺序 I/O 和随机 I/O 的细微时间差异，不考虑 DBMS 可能进行的预取（提前加载数据），以及任何在内存中执行的计算成本（因为它们通常远小于磁盘 I/O 成本）。
操作特定假设：假设每次插入和删除操作都只涉及单条记录；相等性选择查询（即通过主键或唯一键查找）总是精确返回一条匹配记录。
堆文件插入特定假设：为简化，假设新记录总是追加到文件的最后一个页面（如果该页面有空间）。
排序文件特定假设：文件始终根据搜索键严格排序；为保持紧凑，删除操作后文件会进行“压缩”（compacted），以消除空洞。

尽管这些是简化模型，但它们足以揭示不同文件组织方式在不同操作下的总体性能趋势。

Ⅲ. 操作成本分析：堆文件 vs. 排序文件

现在，我们使用上述成本模型来对比堆文件和排序文件在几种常见数据库操作下的 I/O 成本。

示例参数： 假设我们的文件相对较小，便于理解。文件有 B=5 个数据块，每个块可以存储 R=2 条记录，平均读取/写入一个磁盘块的时间 D=5ms。

堆文件示例：记录 (2,5), (1,6), (4,7), (3,10), (8,9) 随意分布在 5 个块中。
排序文件示例：记录 (1,2), (3,4), (5,6), (7,8), (9,10) 严格按照键值排序并存储。

1. 全文件扫描 (Scan All Records)

操作：读取文件中的所有记录。
堆文件：
- 怎么做：由于记录没有任何顺序，DBMS 必须从文件开头到结尾逐个读取所有块，以确保不遗漏任何记录。
- I/O 成本：B * D。
排序文件：
- 怎么做：尽管记录有序，但全文件扫描的本质仍然是读取所有记录。因此，同样需要读取文件中的所有块。
- I/O 成本：B * D。
结论：在全文件扫描操作下，堆文件和排序文件的 I/O 成本是相同的。

2. 相等性搜索 (Equality Search)

操作：根据特定键值查找并返回单条匹配记录（例如 WHERE Key = 8）。
堆文件：
- 怎么做：由于记录在文件中是无序的，DBMS 无法知道目标记录在哪里。它必须从文件开头开始，顺序扫描每个块，检查其中的记录，直到找到匹配的记录。在平均情况下，我们假设目标记录位于文件的中间。
- I/O 成本：0.5 * B * D。这意味着平均需要读取文件总块数的一半。
- 例子：在一个有 5 个块的堆文件中查找 Key 为 8 的记录。最坏情况可能需要读取所有 5 个块（如果 8 在最后一个块）。平均则为 2.5 个块。
排序文件：
- 怎么做：由于记录是排序的，DBMS 可以利用**二分查找（Binary Search）**算法来高效地定位目标记录所在的块。二分查找通过不断减小搜索范围，以对数级的步数快速逼近目标。一旦找到目标记录所在的块，就加载该块。
- I/O 成本：log2B * D。这意味着只需要读取对数数量的块。
- 例子：在一个有 5 个块的排序文件中查找 Key 为 8 的记录。log2(5) 大约是 2.32。这表示平均只需要读取 2-3 个块就能定位到包含 8 的页面，远快于堆文件的平均扫描。
结论：在相等性搜索方面，排序文件凭借其有序性支持的二分查找，性能远优于堆文件。

3. 范围搜索 (Range Search)

操作：查找键值在特定范围内（例如 WHERE Key BETWEEN 7 AND 9）的所有记录。
堆文件：
- 怎么做：由于记录是无序的，DBMS 无法预测哪些块可能包含符合范围条件的记录。因此，它必须扫描整个文件，检查每一个记录是否落在指定的范围内。
- I/O 成本：B * D。需要读取文件中的所有 B 个块。
排序文件：
- 怎么做：排序文件的优势在此处显现。DBMS 可以首先使用二分查找算法快速定位到范围的起始点（或接近起始点）所在的块。一旦找到起始块，就可以从该块开始，进行顺序扫描，逐个读取后续的块，直到找到范围的结束点。
- I/O 成本：(log2B + pages_in_range) * D。其中 log2B * D 是定位起始块的成本，pages_in_range * D 是扫描范围内所有相关块的成本。如果范围内的记录数量不多，pages_in_range 会很小，其总成本远低于堆文件的全扫描。
结论：排序文件在范围搜索方面具有显著优势，它能够利用数据的物理有序性进行高效定位和顺序读取，避免了对整个文件的扫描。

4. 插入 (Insert)

操作：向文件中添加一条新记录。
堆文件：
- 怎么做：新记录通常会被追加到文件的最后一个数据块中（前提是该块有可用空间）。这个过程包括：读取最后一个块到内存，将新记录写入该块，然后将修改后的块写回磁盘。
- I/O 成本：2 * D。一次读取（最后一个块）和一次写入（修改后的块）。
- 例子：插入记录 4.5 到一个堆文件。DBMS 找到最后一个页面，加载它，添加 4.5，然后将该页面写回磁盘。
排序文件：
- 怎么做：插入操作在排序文件中是相对昂贵的。首先，DBMS 必须使用二分查找来定位新记录应该插入的正确位置，以维持文件的排序状态。一旦找到位置，为了腾出空间给新记录，DBMS 可能需要移动该位置之后的所有现有记录（这可能跨越多个块），将它们向后“推”一个位置。然后，所有受影响的块（被移动和修改的）都需要被写回磁盘。
- I/O 成本：(log2B + B) * D。log2B * D 是定位插入点的成本，而 B * D 则代表了在最坏情况下（例如插入到文件开头）可能需要移动并写入几乎整个文件的所有块。
- 例子：插入 4.5 到一个排序文件。它应该位于 (3,4) 和 (5,6) 之间。这意味着 (5,6), (7,8), (9,10) 以及它们所在的页面都需要被移动，并被写回磁盘。
结论：堆文件在插入方面拥有巨大的性能优势，其常数级的插入成本使其成为写入密集型（Insert-heavy）工作负载的首选。

5. 删除 (Delete)

操作：从文件中删除一条具有特定键值的记录。
堆文件：
- 怎么做：首先，DBMS 需要通过相等性搜索找到目标记录，这平均需要扫描文件的一半。找到记录所在的块后，将其从块中删除（例如，通过在页面内部的槽位目录中标记为无效），然后将修改后的块写回磁盘。
- I/O 成本：(0.5 * B + 1) * D。0.5 * B * D 用于查找记录，1 * D 用于将修改后的块写回。
排序文件：
- 怎么做：首先，使用二分查找定位目标记录所在的块。然后，从该块中删除记录。为了保持文件紧凑和排序，删除位置之后的所有记录都必须向前移动，以填补空隙。这意味着需要移动文件的大部分数据，并写入受影响的块。
- I/O 成本：(log2B + B) * D。log2B * D 用于定位记录，B * D 用于移动和写入后续所有块（最坏情况下需要移动整个文件）。
结论：堆文件在删除方面的成本通常也低于排序文件，因为排序文件为了维持其物理秩序需要付出高昂的数据移动成本。

总结：操作成本对比

下表概括了堆文件和排序文件在不同操作下的理论 I/O 成本：

操作类型	堆文件成本	排序文件成本	性能差异总结
全文件扫描	`B * D`	`B * D`	相同：都需读取所有数据块。
相等性搜索	`0.5 * B * D`	`(log2B) * D`	排序文件显著优越：利用二分查找，I/O 次数呈对数级增长，远快于线性扫描。
范围搜索	`B * D`	`(log2B + pages_in_range) * D`	排序文件显著优越：可快速定位范围起点并顺序读取，避免全表扫描。
插入	`2 * D`	`(log2B + B) * D`	堆文件显著优越：常数级 I/O，而排序文件需高昂的数据移动开销。
删除	`(0.5 * B + 1) * D`	`(log2B + B) * D`	堆文件优越：查找成本加少量写入，而排序文件需大量数据移动。

从上述分析可以看出，堆文件非常适合写入密集型（频繁插入、删除）且查询主要为全表扫描的工作负载。而排序文件则更适合读取密集型，特别是包含相等性查找和范围查询的工作负载，但其写入成本很高。

我们能做得更好吗？ 显然，堆文件和排序文件各有其局限性。排序文件在读取方面有优势，但写入效率低下；堆文件写入快，但读取（非全扫描）效率低。为了在两者之间找到更好的平衡点，同时实现高效的随机查找，就需要引入更复杂、更强大的数据结构——索引。索引能够提供快速查找能力，而无需改变数据的物理存储顺序。

索引的背景和基本概念

是什么 (What it is)

堆文件 (Heap Files): 数据库中的数据通常以“堆文件”的形式存储。在堆文件中，数据记录的存储是无序的。
数据访问 API: 访问数据通常有两种方式：通过记录的唯一标识符 recordId (即 pageId, slotId) 直接获取记录，或者从某个页面开始扫描整个文件。
索引的出现: 索引是一种建立在数据之上的、用于加速数据检索的辅助性数据结构。

为什么 (Why it's needed)

堆文件查找效率低: 如果我们想根据某个值（search key，搜索键）来查找数据，而不是 recordId，堆文件效率会非常低，因为可能需要扫描整个文件才能找到目标数据。
加速数据检索和修改: 索引的目的就是为了根据搜索键实现数据的快速查找和高效修改。搜索键可以是表中的任何列或列的子集，且不一定唯一。

怎么做 (How it works)

数据条目 (Data Entries): 索引中存储的项。通常，它是一个 (key, recordId) 对，其中 key 是索引的键值，recordId 是指向实际数据记录在堆文件中位置的指针。

ISAM (Indexed Sequential Access Method) - 静态索引的局限性

是什么 (What it is)

ISAM 是一种早期且相对静态的索引技术。它的基本思想是：

数据排序和预留空间： 首先，将堆文件中的数据记录按照键值进行物理排序，并存储在连续的磁盘区域中，同时预留一些空闲空间。这意味着数据页在磁盘上是按照逻辑顺序物理存储的，支持高效的顺序访问。
构建静态索引树： 在这些物理排序好的数据之上，构建一个高扇出的树形索引结构。索引页只包含 (key, page id) 对（键值和指向数据页的指针），不包含实际的记录数据。

为什么 (Why it's problematic)

ISAM 的主要问题在于其静态性，这导致它在数据频繁更新的场景下性能表现不佳：

静态结构，更新困难： ISAM 的主数据区在创建时是固定的。当需要插入新记录时，如果目标数据页已满，它不会移动后面的数据来腾出空间。相反，新记录会被放置在溢出页 (Overflow Pages) 中。
溢出页的问题： 这些溢出页通常在磁盘上是物理不连续的，并且它们的内容是按插入顺序存储，不是按键值排序的。
查询性能急剧退化： 频繁的插入会导致大量的溢出页，形成长长的溢出链。当你查询数据时，如果数据位于溢出页，你需要沿着这些无序、分散的溢出页进行多次随机磁盘 I/O，这会显著降低查询性能，尤其是范围查询的性能会急剧下降。
- 举例： 想象一个按姓名排序的电话簿。如果中间有人搬家，新住户的信息就写在“附页”上，并用笔在原电话簿上做个标记。如果附页越来越多，而且写得很乱，那么找一个新搬来的人就会非常慢，因为你需要在主电话簿和各个附页之间来回翻找，每次跳转到附页都像一次耗时的“随机翻页”。
不平衡的性能： 不同的查询路径会因为溢出链的长度不同而产生巨大差异。有些查询很快，有些则非常慢，性能变得不可预测。
维护成本高： ISAM 是一种旧技术（IBM 在 1960 年代引入）。只有通过周期性的昂贵索引重组才能恢复其性能。

怎么做 (How it works - Limitations)

查找 (Search): 查找过程与 B+ 树类似，从根节点开始，在每个节点（页）内进行二分查找，然后沿着指针向下到下一层，直到找到数据。这种方式能有效减少 I/O 次数。但在有溢出页的情况下，后续查找效率会下降。
插入 (Insert) 流程：
1. 找到新数据应该在的主数据页。
2. 如果该页有空间，直接插入并可能重新排序页内数据。
3. 如果该页已满，将新记录放入一个新的溢出页。
4. 原始数据页会有一个指针，指向这个溢出页，形成链表。这种“链表”的本质问题在于，它连接的是物理上分散、逻辑上无序的溢出页，导致随机 I/O，效率低下。

索引设计的终极目标

一个优秀的索引设计，是为了在数据库操作的各种需求之间找到最佳的平衡点：

最大化查询效率： 这是索引最直接的目的，通过快速定位数据，显著减少磁盘 I/O 次数。
保证性能的稳定性与可预测性： 无论数据如何增长或变化，查询和数据操作的性能都应该保持在一个可预测的范围内，避免突然的性能下降。
最小化存储空间： 索引本身也占用空间，应尽可能高效地利用这些空间。
支持高效的数据操作 (CRUD)： 不仅仅是查询（Read），插入（Create）、更新（Update）、删除（Delete）操作也应该高效。
支持并发访问： 在多用户环境下，索引结构需要能够有效地支持并发读写，同时保证数据的一致性。

B+ 树 - 动态平衡的优势与解决方案

是什么 (What it is)

B+ 树是现代数据库系统中最常用和最强大的索引结构。它解决了 ISAM 的核心问题，是一种自平衡的多路查找树。

为什么 (Why it's superior to ISAM)

B+ 树通过其动态性和自平衡特性，完美地解决了 ISAM 的痛点，并能更好地实现索引设计的终极目标。

动态自平衡，告别溢出链： B+ 树通过**节点分裂 (Node Split)和节点合并 (Node Merge)**来动态调整树的结构，确保从根节点到任何叶子节点的路径长度始终相同。这保证了无论查找哪个数据，所需执行的磁盘 I/O 次数都是固定的、最少的。它彻底消除了 ISAM 的溢出页问题。
所有数据在叶子节点，高效范围查询： 所有实际数据条目 (key, recordId) 都只存储在叶子节点中。非叶子节点只作为索引，用于快速导航。同时，所有叶子节点都通过双向链表连接。这使得范围查询（如 WHERE salary BETWEEN 50000 AND 80000）极为高效，只需定位到起点，然后沿链表顺序遍历即可。
高扇出，极低树高，减少 I/O ： B+ 树的每个节点通常设计为磁盘页大小（例如 16KB）。由于内部节点只存储键和指针，一个节点可以容纳大量条目，使得树的扇出因子 (Branching Factor) 非常大（通常数百到数千）。
- 结果： 即使有数十亿条记录，B+ 树的高度也通常只有 2 到 4 层。这意味着查找任何记录，通常只需要 2-4 次磁盘 I/O。
写入消耗是可接受的代价： 虽然分裂和合并会带来一些开销，但这些消耗是局部且可控的，不会像 ISAM 那样导致全局性能退化。对于读多写少的应用，B+ 树在查询上的巨大优势远超其写入时的少量开销。

怎么做 (How it works - Detailed Mechanisms)

1. 节点填充率 (Occupancy Invariant)

原则： 每个节点（除了根节点）必须至少填充到一定比例，通常是一半满 (50%)。例如，如果一个节点的容量是 2d 个条目，那么它必须至少包含 d 个条目。
目的： 保证空间效率，避免节点过于稀疏；同时为删除操作后的合并提供基础。

2. 插入 (Insertion) 操作详解

B+ 树的插入操作通过**分裂 (Split)**来保持树的平衡。我们用一个最简单的 B+ 树（d=1）来演示。

d=1 意味着：
- 每个节点最多存 2d = 2 个键。
- 每个内部节点最多有 2d + 1 = 3 个子指针。
- 每个节点（根除外）至少存 d = 1 个键。

案例一：叶子节点分裂 (Copy Up)

假设 B+ 树当前结构如下，叶子节点 [1*, 5*] 已满。

text

   [10]
   /  \
[1*,5*] [10*,15*]

目标：插入键值 3*

定位： 3* 应该插入到叶子节点 [1*, 5*] 中。
问题： 该叶子节点已满，插入 3* 后会变成 [1*, 3*, 5*]，超过 2 个键的限制。
分裂叶子节点：
- 将 [1*, 3*, 5*] 拆分为两个新节点：[1*] 和 [3*, 5*]。
复制中间键到父节点 (Copy Up)：
- 将新分裂出的右侧节点的最小键 3 复制到父节点 [10] 中。
- 注意： 键 3 同时存在于父节点（作为路由键）和叶子节点（作为数据）。
分裂后的 B+ 树： 父节点 [10] 有空间，插入 3 后变为 [3, 10]。操作完成。

text

   [3,10]
   / |   \
[1*][3*,5*][10*,15*]

案例二：插入导致父节点分裂 (Push Up)

假设当前树的根节点 [3, 10] 和叶子 [10*, 15*] 都已满。

text

   [3,10]
   / |   \
... ... [10*,15*]

目标：插入键值 20*

叶子分裂： 20* 插入 [10*, 15*]，导致其分裂为 [10*] 和 [15*, 20*]。
复制中间键： 中间键 15 被复制到父节点 [3, 10]。
问题： 父节点（也是根节点）[3, 10] 也满了，插入 15 后会变成 [3, 10, 15]，超过限制。
分裂内部节点：
- 将 [3, 10, 15] 拆分。
推高中间键到新根节点 (Push Up)：
- 中间键 10 被推高 (Push Up)，成为一个全新的根节点。
- 注意： 10 不再保留于分裂后的子节点中，它只作为上一层的路由键。
- 原根节点分裂为两个新的内部节点 [3] 和 [15]。
最终 B+ 树结构 (树高增加一层)：

text

     [10]
     /   \
  [3]   [15]
  / \    /  \
... ... [10*][15*,20*]

CS186 笔记01 ​

数据库管理系统 (DBMS) 总体架构 ​

是什么 (What it is) ​

为什么 (Why it's needed) ​

怎么做 (How it works) ​

核心抽象：页面 (Page) ​

是什么 (What it is) ​

为什么 (Why it's needed) ​

页面大小如何选择 (How to choose Page Size) ​

文件组织 (File Organization) ​

是什么 (What it is) ​

为什么 (Why it's needed) ​

怎么做 (How it works) ​

页面布局 (Page Layout) ​

是什么 (What it is) ​

为什么 (Why it's needed) ​

怎么做 (How it works) ​

A. 固定长度记录的简单布局 ​

B. 可变长度记录的通用布局：槽页 (Slotted Page) ​

记录格式 (Record Format) ​

是什么 (What it is) ​

为什么 (Why it's needed) ​

怎么做 (How it works) ​

A. 固定长度字段 ​

B. 可变长度字段 (最佳实践：带头部的记录) ​

系统目录 (System Catalogs) ​

是什么 (What it is) ​

为什么 (Why it's needed) ​

怎么做 (How it works) ​

文件组织 (File Organizations) ​

Ⅱ. 成本模型与分析 (Cost Model and Analysis) ​

Ⅲ. 操作成本分析：堆文件 vs. 排序文件 ​

1. 全文件扫描 (Scan All Records) ​

2. 相等性搜索 (Equality Search) ​

3. 范围搜索 (Range Search) ​

4. 插入 (Insert) ​

5. 删除 (Delete) ​

总结：操作成本对比 ​

索引的背景和基本概念 ​

是什么 (What it is) ​

为什么 (Why it's needed) ​

怎么做 (How it works) ​

ISAM (Indexed Sequential Access Method) - 静态索引的局限性 ​

是什么 (What it is) ​

为什么 (Why it's problematic) ​

怎么做 (How it works - Limitations) ​

索引设计的终极目标 ​

B+ 树 - 动态平衡的优势与解决方案 ​

是什么 (What it is) ​

为什么 (Why it's superior to ISAM) ​

怎么做 (How it works - Detailed Mechanisms) ​

1. 节点填充率 (Occupancy Invariant) ​

2. 插入 (Insertion) 操作详解 ​

案例一：叶子节点分裂 (Copy Up) ​

案例二：插入导致父节点分裂 (Push Up) ​

CS186 笔记01

数据库管理系统 (DBMS) 总体架构

是什么 (What it is)

为什么 (Why it's needed)

怎么做 (How it works)

核心抽象：页面 (Page)

是什么 (What it is)

为什么 (Why it's needed)

页面大小如何选择 (How to choose Page Size)

文件组织 (File Organization)

是什么 (What it is)

为什么 (Why it's needed)

怎么做 (How it works)

页面布局 (Page Layout)

是什么 (What it is)

为什么 (Why it's needed)

怎么做 (How it works)

A. 固定长度记录的简单布局

B. 可变长度记录的通用布局：槽页 (Slotted Page)

记录格式 (Record Format)

是什么 (What it is)

为什么 (Why it's needed)

怎么做 (How it works)

A. 固定长度字段

B. 可变长度字段 (最佳实践：带头部的记录)

系统目录 (System Catalogs)

是什么 (What it is)

为什么 (Why it's needed)

怎么做 (How it works)

文件组织 (File Organizations)

Ⅱ. 成本模型与分析 (Cost Model and Analysis)

Ⅲ. 操作成本分析：堆文件 vs. 排序文件

1. 全文件扫描 (Scan All Records)

2. 相等性搜索 (Equality Search)

3. 范围搜索 (Range Search)

4. 插入 (Insert)

5. 删除 (Delete)

总结：操作成本对比

索引的背景和基本概念

是什么 (What it is)

为什么 (Why it's needed)

怎么做 (How it works)

ISAM (Indexed Sequential Access Method) - 静态索引的局限性

是什么 (What it is)

为什么 (Why it's problematic)

怎么做 (How it works - Limitations)

索引设计的终极目标

B+ 树 - 动态平衡的优势与解决方案

是什么 (What it is)

为什么 (Why it's superior to ISAM)

怎么做 (How it works - Detailed Mechanisms)

1. 节点填充率 (Occupancy Invariant)

2. 插入 (Insertion) 操作详解

案例一：叶子节点分裂 (Copy Up)

案例二：插入导致父节点分裂 (Push Up)