存储与索引

一、RAID 存储系统

1.1 存储系统的架构背景

在现代云架构下，存储系统起到了非常重要的作用。主要的存储力量集中在专用存储系统上，而非每台机器各自存储。这导致了”存算分离”的架构趋势——存储和计算被分布到不同的地方，存储系统承担了大部分的存储任务，计算节点可以更专注于计算。

1.2 RAID 的基本思想

RAID（Redundant Array of Independent Disks，独立磁盘冗余阵列）实际上是将很多块硬盘放在一个较小的机柜里面，实现 PB 甚至 EB 级的存储能力。

RAID 的核心设计思想有两条：

1. 通过冗余提高可靠性：多块硬盘放在一起，故障概率大大提高，需要通过冗余来保证数据安全
2. 通过数据分散（条带化 / Striping）提高读取性能：数据被分散在多块磁盘上，读取时可以多块盘同时读，实现并行访问

数据的分布方式是同时分散在多块硬盘上，而非先把一块盘填满再去填另一块，这样才能实现并行读取。

1.3 奇偶校验与冗余

RAID 中最常用的冗余方法是奇偶校验（Parity Check）。基本做法是：

• 假设有 8 块数据盘，再放 1 块校验盘作为第 9 块盘
• 第 9 块盘上存放对应位上其他 8 块盘数据的奇偶校验值
• 一旦发现某块盘上的奇偶校验出了问题，就知道一定有盘坏了
• 磁盘控制器可以检测到哪块盘坏了，然后撤掉坏盘
• 有了奇偶校验位，还可以反推出坏掉那块盘上的数据并恢复

大部分商用场景用的是奇偶校验方法。奇偶校验本身不能确定是哪块盘出了问题，但因为磁盘控制器可以检测到，所以可以定位。

1.4 海明编码与所罗门编码

海明编码（Hamming Code）可以纠正一位差错，即它可以确定是哪块盘出了故障。如果多块盘同时出错，可以通过不同冗余位的值判断。

所罗门编码（Reed-Solomon Code）允许两块盘同时坏并恢复数据，用在数据安全性要求非常高的场合。

1.5 RAID 的各个 Level

RAID 5 是目前商用存储系统最常用的方案。它将校验信息分布在每块盘上（而非集中在单独一块校验盘），这样任何数据修改时不会在单块校验盘上形成写入瓶颈，性能最好。

RAID 4 的瓶颈问题：如果有 4 块数据盘 + 1 块校验盘，任何一块数据盘被修改，都需要同时修改校验盘的信息。四块数据盘的每一次修改操作都会导致那块校验盘也要修改，从而形成瓶颈。

RAID 5 的解决方案：把整块盘分成若干区块，第一组数据的校验信息放在某一块盘上，第二组数据的校验信息放在另一块盘上，以此类推。这样校验信息分布在每块盘上，不会形成单盘瓶颈。

二、磁盘空间管理

2.1 空闲空间管理

数据库中的数据以页（Page）为单位组织。磁盘空间管理类似于文件管理，主要包括：

• 管理空闲块：建表后插入数据会将页填满，DELETE 操作后会出现空闲位置，需要对这些空闲位置进行管理
• 两种管理方式：
  • 使用操作系统的文件管理系统来管理磁盘空间
  • 数据库自己实现磁盘管理（效率更高，因为操作系统某些功能较弱）

2.2 Table Space（表空间）

数据库下面有若干张表，表存在硬盘文件上。表空间（Table Space）定义表与文件的对应关系，每个表空间对应一个存储文件。建表时放到相应的表空间里，数据就存在相应的文件中。在实验数据库中可以直接观察表空间这一概念的实际使用。

三、缓冲区管理

3.1 为什么需要缓冲区

硬盘是用来存储的，内存是用来计算的。所有的计算全部在内存里进行，而非直接在硬盘上。

数据要在硬盘上持久化存储（一旦停电数据就丢失），但所有对数据的处理都在内存里进行。数据必须先调到内存（缓冲区），做完处理（如 select、update）后，如果有修改，还需要把内存里的数据写回硬盘，才算永久保存。

考虑大规模数据处理时，不能只考虑数据的计算算法，还需要考虑数据在不同存储器之间的交互——数据什么时候调到内存、在内存里做什么样的运算、什么时候写回硬盘。这些是数据库存储管理和查询中最重要的概念。

3.2 缓冲区的结构

缓冲区也是按块（frame）来管理的。硬盘上的数据按块存取（通常 4KB），存储系统因为网络传输代价更高，块可能更大（以 MB 为单位）。

缓冲区中的每个 frame 可以分为几种状态：

1. 空闲（Free）：空着不用
2. 正在访问（Pinned）：数据已经从硬盘读到内存，正在做操作（如选择操作），这时不能轻易释放
3. 已处理未修改：数据调上来执行了 select 命令，处理完了但数据没被修改
4. 脏页（Dirty）：数据调上来执行了 update 操作，修改了但还没写回硬盘

如果需要释放一块 dirty 的内存，必须先把它写到硬盘里，否则一旦宕机，内存里的数据就丢失了。

3.3 缓冲区替换策略

数据和程序访问通常有一定的时间局部性——刚被访问过的数据再次被访问的概率更大（如银行柜台的多次操作都涉及同一个账户）。因此数据处理完后尽可能留在内存中，后续访问就不需要再从硬盘读取。

但缓冲区有限（如 buffer 只有 10 页，表有 100 页），当缓冲区满了就需要决定替换哪一块出去。两种常用的替换策略：

LRU（Least Recently Used，最近最少使用）：

• 每次挑选空闲时间最长的内存块清理掉
• 需要记录每个内存块最后被使用的时间，并从中挑出最小的，计算量较大

Clock 策略：

• 把所有的内存块排在一个环上（用循环链表组织）
• 有一个指针指向这些内存块
• 每次需要清除一块时，指针沿环移动检查
• 如果发现一个内存块刚被使用过，第一次不清理，只做标记
• 如果碰到已经标记过的，说明它已经有一段时间没被访问了，就把它清除
• 数据结构比较简单，效率接近 LRU

3.4 单缓冲区 vs 多缓冲区

3.5 预取（Prefetching）与 I/O Agent

查询数据时先到缓冲区找，找不到再到硬盘里读，效率较低。

预取的思路是：根据读取模式，提前把后面可能要读的页读到内存。

• 如果对一张表做遍历（全表扫描），读第一块时可以判断后面会跟着读第二块、第三块，于是自动提前把它们读到内存
• 数据库中有I/O Agent——一个自主运行的程序，专门监控从硬盘往内存读数据的请求，发现访问模式后就提前预取
• 部分 AI 应用在数据库中被用于预测后面要读的数据并提前读入

四、文件组织方式

4.1 记录标识符（Record ID, RID）

数据库中的每条记录（元组）都有一个唯一的标识符 RID。很多系统中就用该元组所在的地址作为 RID，因为地址是唯一的，而且知道地址就可以直接访问到数据。

4.2 堆文件（Heap File）

数据完全无序存放。每条元组来了直接往文件里插（可能查到末尾或前面的空位）。不考虑元组的顺序。数据页的管理比较简单——记录每个物理块的空闲空间等。

4.3 顺序文件（Sequential / Sorted File）

数据按照某个属性排序存放。如果数据访问方式与排序方式一致，效率较高。

但在实际运行中很难保持时刻有序，因为存在插入和删除操作：

• 如果保持完全排序，中间插入一条数据会导致后面所有数据后移——代价不能接受
• 实际做法：新增数据放在追加区域，等一段时间数据比较乱了再做一次整理（reorganization）

4.4 聚集文件（Clustered File）

两张表（如学生信息和选课信息）放在同一个空间里。因为经常一起被访问，放在一起时它们出现在同一物理块的概率更大，一次 I/O 就能读取到，效率更高。

这种思路在数据库中通过表空间（特别是 DMS 表空间）来实现。

五、代价模型

5.1 查询优化的核心逻辑

一条 SQL 语句可以用多种不同的关系代数表达式来实现，每种实现方法的代价不同。查询优化的基本思路很直接：穷举所有可能的实现方案，计算每种方案的代价，从中选出代价最小的。

5.2 代价计算的基本符号

在数据库的代价模型中，最主要考虑的是数据交换的代价（即 $D$）。因为 $C$ 和 $H$ 都是内存操作，速度快得多。后续讨论的很多算法，基本上只看读写的代价（对硬盘或存储系统的读写）。

5.3 三种基本文件类型的组织形式

1. 堆文件：数据无序存放
2. 排序文件：数据按某属性排序存放
3. 哈希文件：数据经过哈希函数后，按哈希值分到不同的桶（Bucket）中存放

聚集文件（多张表放一起）可以归为前两类（要么排序要么不排序）。

5.4 基本数据访问操作

5.5 各文件类型的操作代价

堆文件（Heap File）

排序文件（Sorted File）

这也解释了为什么排序文件在数据库里不会让每次插入都实时调整顺序——全表扫描的代价太大了。

哈希文件（Hash File）

• 哈希文件中数据经过哈希函数分配到不同的桶中
• 每个桶不能太满，通常会留一定空间（所以总大小约为数据的 1.25 倍，这是一个经验系数）

哈希文件对区间查询不友好。因为哈希函数把数据分散了（23 岁可能在桶 0，24 岁在桶 1，25 岁在桶 2），区间小还好（查三次），区间大就等同于全表扫描。

六、页内记录的存储

6.1 定长记录（Fixed-Length Records）

每条元组的长度固定（如表中没有 VARCHAR 类型）。页大小固定，元组像数组一样一个接一个存放，访问某个属性时比较好定位。

数据库执行删除操作时，通常不会真正抹掉数据，而是在那个位置做一个标记（如置 0），新数据来时直接填进去——为了减少磁盘操作次数，提升效率。

6.2 变长记录（Variable-Length Records）

表中有 VARCHAR 类型时，每条记录的长度不固定，可能从 100 字节变成 102 字节。所以元组没法固定在某个位置——如果第一条记录长度变大了，就会挤到第二条的位置。

变长记录通过指针（slot directory）来管理，指针存储在页的后面部分，指向每条记录的实际位置。

6.3 记录长度的限制

不同系统略有差别。有的系统会限制每条记录的长度不能超过一个块的大小（如 DB2），但同时会提供大对象（Large Object）数据类型来处理特别长的属性值。

七、表空间（Table Space）

7.1 基本概念

每张表存在硬盘文件上，表空间定义了表与文件的对应关系。建表时放入某个表空间，数据就存入对应的文件。

两种类型的表空间：

DMS 就是前面讲的那种”聚集文件”形式——几张表的数据放在一起。数据库管理员（DBA）的职责之一就是规划数据在硬盘上怎么存放。

7.2 Container 与条带化

类似于 RAID 中的条带化概念。因为一台机器上可能有多块硬盘，DMS 表空间下可以建多个 Container，每个 Container 对应一个文件，分别放在不同的硬盘上。这样读的时候可以从多块硬盘同时往外读，效率更高。

SMS 表空间下也可以定义多个目录，分别在不同的硬盘上。

表空间还可以直接对应到裸设备（raw device）上，这是更底层的方式。

八、索引基础

8.1 为什么需要索引

以一个大型银行系统为例：工商银行可能有几十亿条元组（每人几张卡），但在 ATM 机上插卡输密码后，系统能在几百毫秒内返回验证结果。这主要靠的就是索引——有了索引才能非常快速地查找到对应数据。

索引是提高数据库查询效率最重要的辅助文件结构。

8.2 索引的基本结构

一个典型的索引结构分为三层：

1
2
3
[Index 层（树结构或哈希表）]
    -> [Data Entry 层] -> 指针指向实际数据
        -> [数据文件（关系表）]

Data Entry 建立了索引找到的键值和实际元组之间的对应关系，有三种形式：

1. 直接包含所有记录（索引就是数据的存储方式）
2. 键值 + 对应的元组 RID（通过指针指向实际元组）
3. 键值 + 对应的 RID 列表（一个键对应多条记录时）

8.3 聚簇索引 vs 非聚簇索引

排序文件主要就是对应聚簇索引。对经常做区间查找的属性，应该建聚簇索引，让数据的物理存储顺序跟索引顺序一致，这样区间查找时连续把几块数据读上来就行。

8.4 稠密索引 vs 稀疏索引

• 稠密索引（Dense Index）：每个 data entry 都有一个指针指向数据
• 稀疏索引（Sparse Index）：只在每一页的第一个元素上建指针（当索引顺序和数据排序一致时，只需要每块指一次即可）

8.5 主索引 vs 辅助索引

• 主索引（Primary Index）：在 primary key 上自动建的索引
• 辅助索引（Secondary Index / 二级索引）：用户在其他属性上自己建的索引

8.6 复合索引（Composite Index）

可以在多个属性上建索引（如 age + salary）。做法是先按第一个属性排序，再按第二个属性排序。两个属性的地位不一样——优先按第一个属性。因此查询时如果只用第二个属性作为条件，这个复合索引用不上。

8.7 SQL 中创建索引

1
CREATE INDEX idx_name ON table_name (column1, column2) USING BTREE;

九、索引设计的指导思想

9.1 基本原则

1. 了解数据的检索方式：平时做什么样的查询，对哪些属性做筛选
2. 分析数据的特点：
   • 数据的聚集性和生成模式（如社交网络有社团结构）
   • 数据之间的语义关系
   • 相似的数据尽量放在一起（但”相似”的定义因数据类型而异）
3. 考虑存储结构：
   • 索引存在硬盘上，所以索引结构必须与硬盘的物理特性匹配
   • 硬盘以块为单位组织数据，索引的每个节点也应以块为单位、每个节点存放大量数据

二叉搜索树可以作内存索引结构，但不能作硬盘索引——因为每个节点只有一个值和两个指针，数据量太少，放在硬盘的一整块里极不划算。

9.2 提高效率的核心思路：减少搜索空间

全表扫描的代价很大（$B \cdot D$）。如果数据排序了就能折半查找，每次砍掉一半搜索空间。索引结构的设计核心就是尽可能快地裁剪搜索空间——把搜索上相近的数据集中在一个空间/区间里，裁剪起来就方便。

效果好不好，本质上取决于与查询数据相关的数据距离它有多远。把这个距离控制得非常小，效率就一定非常高。

十、ISAM 索引

10.1 基本思想

ISAM（Indexed Sequential Access Method）是一种静态的树形索引结构。其核心思想是在排序文件的基础上一层层地建二级索引：

• 在原始数据文件之上建一层二级索引（每页抽取第一条记录的值和页指针）
• 二级索引比原文件小得多（每个数据页只抽一个属性值 + 一个指针），查找很快
• 如果二级索引还嫌大，就再往上建一层，形成多级索引树

10.2 结构特点

• 最底层使用溢出链表（Overflow Chain）：因为结构是静态的，当插入数据时，如果对应的页满了，就在后面挂一个溢出页
• 每个节点大小与一个物理页大小一致（适配硬盘以页/块为单位的特点）
• 所有数据都存放在叶子节点上

10.3 搜索

从根节点往下逐层定位，类似于在 B 树中查找。在每层节点内部做二分查找，确定下一层的位置。

搜索代价约等于 $\log_F N$（其中 $F$ 是每个节点的扇出数，$N$ 是数据页数）。因为 $F$ 很大（每个节点里可以放很多 key-pointer 对），所以树高很低。

10.4 插入与删除

• 插入：找到对应的叶子页，如果满了就在后面加溢出页
• 删除：找到位置删除，如果溢出页删空了就回收

10.5 主要问题与解决

问题：溢出链表太长会导致在链表上只能线性搜索，代价变大。

解决方法：数据库会定期重新整理（reorganize），避免溢出链表过长。

10.6 ISAM 的优点

由于树的上面部分是静态的（不变的），所以查询和修改操作不会相互影响。在后续的锁机制中可以看到，ISAM 结构下查询和修改之间不会形成锁等待，效率较好。

如果数据比较静态（很少插入删除），可以用 ISAM；如果数据比较动态，就要用 B+ 树。B+ 树上面是动态的，会有锁的问题。

10.7 代价示例

假设 100 万条记录，每页 10 条（共 10 万个数据页），每个节点可存放 100 个 data entry：

用树结构的代价远低于直接二分查找，这就是为什么数据库普遍使用树形索引。

十一、B+ 树索引

11.1 B+ 树的动机

B+ 树（B+ Tree）是一种动态的索引结构，结构上与 ISAM 非常相似。但 B+ 树在设计上需要满足两件事：

1. 树的高度必须是对数级的（保持平衡，否则效率无法保证）
2. 插入和删除的代价也要保持在树高度级别，同时操作后仍要保持树的平衡

11.2 B+ 树的结构特点

• 是一棵多叉搜索树（可以看作二叉搜索树的推广）
• 每个节点的子节点数量要求在 $[M/2, M]$ 之间（$M$ 为节点最大容量），这保证了一定程度的平衡
• 根节点和叶子节点至少有两棵子树
• 所有叶子节点在同一层
• 叶子节点之间用双向链表连接（方便区间查找和节点间借数据）
• 每个节点大小与物理页大小一致

11.3 搜索

和 ISAM 一样，从根节点往下找，每层定位一个子节点，复杂度为树的高度 $O(\log_F N)$。

11.4 插入操作（核心）

B+ 树插入操作的巧妙之处在于它是从下往上处理的：

1. 从根往下找到应插入的叶子节点
2. 将数据插入该叶子节点
3. 如果叶子节点满了（超过 $M$ 个条目），则将该节点一分为二（split）
4. 分裂意味着要在父节点中增加一个指针（相当于在父节点中插入一个值）
5. 如果父节点也满了，继续一分为二，递归向上
6. 如果一直分裂到根节点也满了，则根节点也一分为二，树的高度 +1

B+ 树用了非常巧妙的方法来保持平衡。它不像红黑树或 AVL 树那样需要复杂的旋转操作。B+ 树的平衡策略很简单——插入导致树变深时，是所有节点同时变深一层（因为只有根节点分裂时树才增高）。删除导致树变浅时，也是所有节点同时变浅一层。这样就始终保证了平衡性。

优化：如果插入前发现兄弟节点有空位，可以先”借”给兄弟节点，避免分裂。

11.5 删除操作

删除操作是插入的反向过程：

1. 找到要删除的值所在的叶子节点
2. 删除该值
3. 如果删除后节点中的条目数 小于 $M/2$，则与旁边的兄弟节点合并（merge）
4. 合并后父节点中的指针减少一个（相当于父节点删了一个值）
5. 如果父节点也小于 $M/2$，继续递归向上合并
6. 如果递归到根节点子节点数少到可以合并，树的高度 -1

11.6 重复数据的处理

当索引键有重复值时，可以用以下几种方式：

• 每个 key 跟一个指针
• 一个 key 后面跟多个指针（重复值共享同一个 key，后跟多个 RID）

11.7 字符串前缀压缩

对于字符串类型的索引键，为了在一个节点中存放更多条目、增加扇出、降低树高，可以采用前缀压缩：

• 只需存放足够区分前后节点的前缀，不需要存全名
• 例如 “David Smith” 只需要存到 “Davi” 就足以起到分割作用（因为 “Davi” 之前的所有值都小于它）
• 四个字符比十一个字符省得多，一个节点中可以存放更多的 key

11.8 删除操作的实现细节

在实际数据库中，删除操作很多时候只是加标签（mark deleted），不会真正去调整 B+ 树结构——这也是为了减少磁盘操作。

11.9 批量建索引（Bulk Loading）

当需要一次性往表中导入大量数据时（如数据迁移），一条条 INSERT + 维护索引太慢。更好的做法是：

1. 先把数据文件 load 到数据库中（不做索引维护）
2. 对数据进行排序
3. 按排序顺序逐条插入 B+ 树

因为排序后每次插入都在最后面的位置（最右侧路径上），分裂也总是发生在最右侧，调整路径上只需记录一条路径即可——比随机插入高效得多。

十二、各类索引结构对比总结

• Previous
  乱序执行
• Next
  Cayley定理