Skip to content

2 、存储与索引

一、基础🧀

1、DBMS结构与存储🧀

DBMS设计

从这里可以看出数据库的设计是基于磁盘的，所以要考虑到磁盘的各种特性

flowchart TD

A[SQL Client]

B[Query Parsing & Optimization]

C[Relational Operators]

D[Files & Index Management]

E[Buffer Management]

F[Disk Space Management]

G[(Disk / SSD)]

H[Concurrency Control<br/>并发控制]

I[Recovery<br/>崩溃恢复]

A --> B
B --> C
C --> D
D --> E
E --> F
F --> G

H --- B
H --- C
H --- D

I --- E
I --- F

%% 定义样式
classDef cross fill:#EEF6FF,stroke:#2E86C1,stroke-width:2px,color:#000;

%% 应用样式
class H,I cross;

数据库读取数据：一次读一个 page，不是一次读一条记录。

磁盘特点：非常慢，必须减少 I/O；且顺序读写比随机读写快👍，因此数据库设计原则尽量顺序读取

2、存储结构🧀

表在磁盘上存成 file，file 由很多 page 组成，每个 page 里有很多 record

flowchart TD
    A[Table / Relation] --> B[DB File]
    B --> C[Page 1]
    B --> D[Page 2]
    B --> E[Page 3]

    C --> C1[Record 1]
    C --> C2[Record 2]
    C --> C3[Record 3]

    D --> D1[Record 4]
    D --> D2[Record 5]

    E --> E1[Record 6]
    E --> E2[Record 7]

Pages 在磁盘上由 Disk Space Manager 管理，在内存中由 Buffer Manager 管理。

flowchart TD
    A[Table / Relation] --> B[Logical File]
    B --> C[Pages]
    C --> D[Records]

    E[Disk Space Manager] --> C
    F[Buffer Manager] --> C

3、文件组织方式🧀

数据库中文件可以有多种存储方式：

方式 途径
堆文件 / 无序文件（Heap File） 记录没有顺序
聚簇堆文件（Clustered Heap File） 按某种规则把相关记录放在一起
排序文件（Sorted File） 按某个 key 排序存储
索引文件（Index File） 通过索引结构访问数据
❌堆文件链表实现 🌟堆文件的页目录实现（Page Directory）
heap-as-list.svg heap-page-directory.svg
问题：如果要插入一个20bytes的record，如果是链表必须一个一个page找，效率很低。 建立一个 目录页（Directory / Header Page），记录 每个 page 剩余多少空间。找一个空间够的page，直接读取Page插入记录。因为header page经常访问通常会被缓存，所以IO 更少

二、页内部结构🧀

设计页结构时需要解决几个问题

  • 使用紧密/非紧密排列

  • 使用定长/变长来记录数据

1、排列方式🧀

紧密排列 非紧密排列
packed.svg unpacked.svg
优点 空间利用率高，没有空洞 不移动记录的位置，而是使用 bitmap 或 slot 标记记录是否存在。
缺点 当删除记录时，需要把后面的记录整体向前移动。Record ID（RID）改变，如果其他数据结构（例如 索引）引用了这个记录，就会产生问题。

2、槽式页（slotted page）🧀

删除 插入
slot-delete.svg slot-insert.svg
删除槽的指针，中间空间即空缺 插入时中间空缺先不去管他，因为slotted page本来就允许 page内部记录不连续。直到总空闲空间不够或者系统整理页面时才会进行文件碎片调整

槽结构

槽目录位于 page 的底部，并且会随着记录数量增加而向上增长。记录从 page 的顶部开始向下存放，因此 page 中间会形成一块空闲空间。两者相遇的时候说明磁盘满了

当插入一条新的 record 时：

  1. 将 record 写入当前的 free space 区域；
  2. 在 slot directory 中新增一个 slot entry，该 entry 记录该 record 的位置和长度。

三、记录内部结构🧀

目标：

  • 节省空间
  • 快速访问字段

1、固定长度字段🧀

如果字段都是固定长度，例如：

1
2
3
INT
FLOAT
DATE

记录可以直接顺序存储：

1
| id | age | score |

那么 record 的布局是：

1
2
3
offset 0   -> id
offset 4   -> age
offset 8   -> score

访问第 i 个字段只需要：

1
offset = base + i × field_size

固定长度的一个问题：NULL

如果字段是 NULL：

1
2
Student(id, name, age)
(1001, NULL, 20)

如果仍然给 name 分配空间，会浪费空间。

所以数据库通常会加 NULL bitmap 表示 NULL

2、变长字段🧀

1
2
name VARCHAR
description TEXT

记录：

1
2
(1001, "Alice")
(1002, "Christopher")

长度不同：

1
2
Alice        = 5 bytes
Christopher  = 11 bytes

所以字段位置不固定，数据库无法通过公式计算 offset。

方法 优缺点
填充（Padding）❌ 把 VARCHAR 固定长度。给出冗余空间保证变量可以被存储。缺点就是空间利用率低下
分隔符（Delimiter / CSV）❌ 使用逗号分割变量。问题一是如果文本里有逗号会混乱；二是找第 i 个字段需要扫描
头指针 / 偏移表（Record Header）✅ record-header.svgRecord Header 记录每个字段的 offset以及 NULL bitmap。

四、成本模型🧀

符号 含义
\(B\) 数据块数量
\(R\) 每个 block 的记录数
\(D\) 读取一个 block 时间
操作 堆文件（Heap File） 排序文件（Sorted File）
扫描（Scan） 扫描整张表 \(B\times D\) \(B\times D\)
等值查询（Equality Search） 查某个具体值 \((B\times D)/2\) \((\log_2 B)\times D\)
二分查找
范围查询（Range Search） 查某个区间 \(B\times D\) \((\log_2 B + pages)\times D\)
插入（Insert） \(2\times D\)
（读最后 page+写 page）		 \((\log_2 B + B)\times D\)
必须移动后面所有记录所以 \(+B\)
删除（Delete） \((B/2+1)\times D\)
\(+1\) 是因为要写入		 \((\log_2 B + B)\times D\)

五、索引和B+树🧀

为什么不用二分查找直接找？

但问题是数据库是磁盘结构。

如果树是二叉的会非常深 \(\log_2(B)\)

例如：\(\log_2(1000000) ≈ 20\) ，意味着20次I/O，太慢。

用排序的 key→(PageID, RecordID) 作为索引可以加速查找，但由于 fan-out 小、维护成本高、I/O 多，因此不适合作为高效索引结构。

通过对 key lookup pages 递归建立索引，将线性结构转化为多层高扇出树结构，从而显著降低查找深度和 I/O 成本，这是 B+ 树的基本思想雏形。

1、B+树🧀

  • 高 fan-out → 降低高度 → 降低 I/O
  • 平衡 → 查询稳定
  • 高效插入删除 → 当树变高时新的一层加在“上面”

B-plus-tree.svg

中间是左闭右开

※占用不变量

  • 每个节点至少一半满，最多装满 \(d ≤ entries ≤ 2d\)
  • 指针数量 \(\#pointers = entries + 1\)
  • 用至少50%填充保证树始终矮胖，从而降低磁盘I/O
  • 根节点不需要满足这个要求

Tip

高度为 \(3\) ，\(d = 2\) ，可存记录 \(2d\times (2d+1)^h = 4\times 5^3\)

为什么实用

Page size = 128KB，每个 (key, pointer) ≈ 40B，因此 \(128KB / 40B ≈ 3200\)，一个节点大约能放约 3200 个 key。由于 B+ 树中 \(max(entries) = 2d\)，所以 2d ≈ 3200，得到 d ≈ 1600，对应 fan-out = 2d + 1 ≈ 3201。

实际中节点不会完全填满，若假设填充率约为 67%，则平均 \(average fan-out ≈ 2144\)。

在这种情况下，树的容量增长非常快：当 \(Height = 1\) 时，约为 \(2144² ≈ 4,596,736\) 条记录；当 \(Height = 2\) 时，约为 \(2144³ ≈ 9,855,401,984\) 条记录

2、操作🧀

（1）查找🧀

  • 从 root 开始
  • 在当前节点里用二分查找，确定 key 落在哪个区间
  • 顺着对应指针往下一层走
  • 重复这个过程直到到达叶子节点
  • 在叶子节点找到 key，对应得到 recordId

时复 \(O(log_F N)\)

（2）插入🧀

flowchart TD

    A[开始插入 key] --> B[像查找一样<br/>从 root 一路定位到目标叶子节点]

    B --> C{叶子节点是否有空间?}

    C -- 有 --> D[直接插入 key]
    D --> E[保持叶子内部 key 有序]
    E --> F[结束]

    C -- 没有 --> G[叶子分裂 Split Leaf]

    G --> G1[把原来 2d+1 个条目<br/>分成 d 和 d+1]
    G1 --> G2[修复叶子节点之间的 next/prev 指针]
    G2 --> G3[把右侧新叶子的最小 key<br/>复制到父节点]
    G3 --> H[把新叶子的信息插入父节点]

    H --> I{父节点是否有空间?}

    I -- 有 --> J[父节点直接插入新索引项]
    J --> F

    I -- 没有 --> K[父节点继续分裂]
    K --> L[将分裂产生的信息继续向上递归插入]
    L --> M{是否传播到更高层?}

    M -- 是 --> I
    M -- 否 --> F
普通插入 批量加载
一条一条插 一次性建
每次都走 root 不走
随机 I/O 顺序 I/O
频繁 split 很少 split
慢 快

3、索引🧀

B+树既支持等值，也支持范围

1
2
3
Age = 31 AND Salary = 400   ✔
Age = 55 AND Salary > 200   ✔
Age > 31 AND Salary = 400   ❌

B+树只能高效处理“前缀连续”的查询

1
<Age, Salary>

排序：字典序

  1. 先按 Age 排
  2. Age 相同 → 按 Salary 排

（1）索引存什么🧀

byValue.svg

存数据：key → 整条记录

byRef.svg

存指针：key → recordId

byListRef.svg

一个 key 对应多个记录：key → [rid1, rid2, rid3]

（2）索引怎么存🧀