Database System （二）
2025-4-5
| 2025-4-11
Words 3751Read Time≈ 10 min
type
status
date
slug
summary
tags
category
icon
password

介绍

在之前的笔记中，我们介绍了用于数据存储的不同文件和记录表示方法。本周，我们将介绍索引，这是一种构建在数据文件之上的数据结构，用于加快对特定键值的读取速度。
你可以把数据文件想象成一本书的实际内容，把索引想象成目录，用于快速查找。我们使用索引来加快查询速度，尤其是那些频繁执行的查询。
举个例子，假设有一个 Web 应用程序，在用户登录时需要根据用户名去用户表（Users 表）中查找记录。如果在用户名这一列上建立索引，就可以快速找到尝试登录的用户所在的那一行，从而加快登录过程。
在本课程笔记中，我们将学习B+ 树，这是一种特定类型的索引结构。下面是一个 B+ 树的示例：
（图中展示了一个 B+ 树的结构）
notion image

插入操作（Insertion）

将一个键值插入 B+ 树时，请遵循以下步骤：

1️⃣ 找到要插入值的叶子节点 L：

  • 可通过遍历树结构查找。
  • 将键和值按顺序插入该叶子节点。

2️⃣ 如果叶子节点 L 溢出（即含有超过 2d 个键）：

假设阶数为 d，最多允许 2d 个键。

a. 分裂节点：

  • 将 L 分为两个节点：L1 和 L2。
  • L1 保留前 d 个键，L2 保留后 d+1 个键。

b. 插入父节点：

  • 如果 L 是叶子节点：
    • 复制 L2 的第一个键到父节点。
  • 如果 L 是内部节点（非叶子）：
    • 移动 L2 的第一个键到父节点。

c. 调整指针。

3️⃣ 如果父节点也溢出了，则对其递归执行步骤 2。

只有此时才会导致树的高度增加

注意事项：

  • 我们在将键从叶子节点插入到父节点时，是进行“复制”而非“移动”，以保证叶子节点中保留了实际数据。
  • 对于内部节点，可以“移动”键到父节点，因为这些节点不存实际数据，只起索引作用。

示例：插入操作演示（阶数 d = 1）

初始树如下：
notion image

插入 19：

插入后，17 对应的叶子节点有空间：
notion image

插入 21：

溢出，叶子节点 [17 19 21] 分裂为两个节点：
  • L1 = [17]
  • L2 = [19 21]
  • 将 19 复制到父节点：
L_1 is the leaf node with 17, and L_2 is the leaf node with 19 and 21.
L_1 is the leaf node with 17, and L_2 is the leaf node with 19 and 21.
Since we split a leaf node, we will COPY L_2’s first entry up to the parent and adjust pointers. We also sort the entries of the parent to get:
notion image

插入 36：

再次导致溢出，叶子 [27 32 36] 分裂：
  • L1 = [27]
  • L2 = [32 36]
  • 将 32 复制到父节点：
此时父节点 [19 27 32] 也溢出，进行父节点分裂：
  • L1 = [19]，L2 = [32]，将 27 移动到根节点：
notion image
Notice that now the parent node overflowed, so now we must recurse. We will split the parent node to get:
L_1 is the inner node with 19, and L_2 is inner the node with 27 and 32.*
L_1 is the inner node with 19, and L_2 is inner the node with 27 and 32.*
Since it was an inner node that overflowed, we will MOVE L_2’s first entry up to the parent and adjust pointers to get:
notion image
Lastly, here are a couple clarifying notes about insertion into B+ Trees:
  • Generally, B+ tree nodes have a minimum of d entries and a maximum of 2d entries. In other words, if the nodes in the tree satisfy this invariant before insertion (which they generally will), then after insertion, they will continue to satisfy it.
  • Insertion overflow of the node occurs when it contains more than 2d entries.

总结说明：

  • B+ 树中的每个节点通常含有 d ~ 2d 个键；
  • 插入时如果节点包含超过 2d 个键就会溢出并触发分裂；
  • 只有父节点溢出时才可能导致树高度增加；
  • 实际记录只保存在叶子节点中，内部节点仅用于索引导航。

删除操作（Deletion）

删除一个键值的过程非常简单：

基本操作：

  • 找到对应的叶子节点，然后
  • 将目标值从叶子节点中删除。
就这样

技术细节补充：

  • 是的，这种做法可能会暂时违反 B+ 树的一些结构性不变式，例如叶子节点中键的数量可能少于下限 d。
  • 但这在实际中并不严重，原因是：
      • 实际应用中插入操作远多于删除操作，所以很快就会有新的键值插入，重新恢复结构平衡。

注意事项：

  • 我们从不直接删除内部节点（非叶子节点）中的键值。
  • 这是因为内部节点中的键仅作为索引导航使用，不包含实际数据。

存储记录（Storing Records）

到目前为止，我们还没有讨论记录究竟是如何存储在叶子节点中的。
现在我们来看看。在 B+ 树的叶子节点中存储记录的方式有三种，这里介绍的是：

方案一：按值存储（Alternative 1: By Value）

在方案一中，叶子节点本身就是数据页。
也就是说，叶子节点直接存储完整记录，而不是只存储指向记录的指针。

示例数据表：

分数（Points）
名称（Name）
2
MEM
3
LAK
5
BOS
7
MIL
20
BKL
24
GSW

树结构如下：

notion image
  • 根节点：包含键 17
  • 中间节点：例如 5 和 24
  • 叶子节点：直接存储了数据对，如 (2, MEM)、(5, BOS) 等

局限性：

虽然方案一实现起来最简单，但也存在明显缺点：
  • 无法支持多个索引同时建立在同一文件上。
    • 例如：如果你已经对 Points 建立了索引，
    • 就无法再对 Name 建立二级索引，除非你复制一份文件，再基于这份新文件建立另一个索引。

存储记录方案二：按引用存储（By Reference）

在方案二中，叶子节点中不再直接存储记录本身，而是存储指向记录的指针。

示例数据表：

分数（Points）
名称（Name）
2
MEM
3
LAK
5
BOS
7
MIL
20
BKL
24
GSW
notion image

存储结构说明：

  • 叶子节点中存储的是形如 (Key, RecordID) 的对。
    • 例如：(2, [1,1]) 表示键值为 2 的记录在磁盘的第 1 页第 1 条记录。
    • RecordID = [页号, 记录号]
  • 叶子节点（Data Entries） 存储的是：
    • 磁盘中的实际记录（Pages in Disk）

      优势

      使用引用的方式（即仅存指针）有一个很大的好处：
      允许在同一个数据文件上构建多个不同的索引结构。
      例如：
      • 可以同时根据 Points 构建索引，
      • 也可以再根据 Name 构建另一个索引，
      • 因为索引文件中不存实际数据，数据的物理顺序无关紧要。

      存储记录方案三：使用引用列表（By List of References）

      在方案三中，叶子节点存储的是指向记录的列表。
      这相比方案二更加紧凑，特别是在有多个记录拥有相同键值的情况下。

      关键点：

      • 每个叶子节点中包含的内容是形如：
        • 例如：(2, {[1,1], [1,2], [2,1]}) 表示值为 2 的数据存在于：
          • 第 1 页第 1 条记录
          • 第 1 页第 2 条记录
          • 第 2 页第 1 条记录

        示例数据表：

        分数（Points）
        名称（Name）
        2
        MEM
        2
        LAK
        2
        BOS
        7
        MIL
        7
        BKL
        50
        GSW

        存储结构示意图：

        notion image
        Index File 中的叶子节点包含：
        • (2, {[1,1], [1,2], [2,1]})
        • (7, {[2,2], [3,1]})
        • (50, {[3,2]})
        而这些索引指向的实际数据存储在 Pages in Disk 中：
        • [1] 页：MEM、LAK
        • [2] 页：BOS、MIL
        • [3] 页：BKL、GSW

        优势：

        相比方案二（每个键值都要单独存储一次），方案三能在多个记录拥有相同键值的情况下显著节省空间。

        总结对比三种方式：

        方案
        存储内容
        特点
        方案一
        叶子中直接存储记录
        实现最简单，但无法建多个索引
        方案二
        叶子中存储记录指针 (key, RecordID)
        可支持多个索引，灵活度高
        方案三
        叶子中存储指针列表 (key, [IDs])
        紧凑高效，适用于同键值对应多个记录的情况

        聚簇（Clustering）

        在介绍了叶子节点如何存储记录之后，现在我们来了解一下数据页（Data Pages）如何组织的问题。

        什么是 Clustered / Unclustered？

        • 指的是数据页在磁盘上的物理存储结构。
        • 用于方案二和方案三（因为它们的叶子节点只保存指针，数据存在其他页中）。
        • 方案一的叶子节点本身就是数据页，因此天然是 Clustered（聚簇的）。

        Unclustered Index（非聚簇索引）

        在 非聚簇索引 中：
        • 数据页几乎是无序的，也就是说你需要单独访问多个数据页来获取你需要的多个记录。

        举例说明（图解）：

        树结构：
        叶子节点指向的数据页分布如下：
        notion image
        如图中蓝线所示：
        • 假如你需要读取键为 12 和 24 的记录，
        • 它们可能分别指向多个不同的数据页，
        • 那你就必须把这些页一页一页地读出来，性能会受到影响。

        总结：

        类型
        数据页结构
        优点
        缺点
        Clustered
        有序/顺序存储
        顺序读取效率高
        每张表只能有一个聚簇索引
        Unclustered
        无序/分散存储
        可支持多个索引
        查询一个范围的数据时较慢

        聚簇索引（Clustered）

        在 聚簇索引 中：
        • 数据页按照建立 B+ 树所使用的索引字段进行排序。
        • 这并不意味着物理上严格排序，而是大致上相同/相近键值的记录会在相同的数据页中。

        为什么聚簇更高效？

        • 如果两个记录的键值接近，它们极有可能位于同一页。
        • 第二条记录可能可以直接从缓存中读取（因为 I/O 是按页读取的）。
        • 所以：
          • 查找连续键或范围查询时，只需要读一页就能拿到多个结果。

        图示说明：

        树结构示意：
        notion image
        蓝色箭头说明了叶子节点如何映射到数据页（Data Pages）：
        • 例如键值为 7 和 12 的记录，很可能就在连续的两个数据页中。
        • 所以只需读取两个数据页就能获得它们的全部记录。

        I/O 成本对比总结：

        索引类型
        平均 I/O 次数
        Unclustered
        每条记录 ≈ 1 次 I/O
        Clustered
        每页 ≈ 1 次 I/O（包含多条记录）

        聚簇 vs 非聚簇索引对比：

        比较项
        聚簇索引（Clustered）
        非聚簇索引（Unclustered）
        数据页是否排序
        是（大致按照索引字段顺序）
        否，数据页混乱
        范围查询效率
        高，读取一页可得多个记录
        低，需多次访问不同页
        建立多个索引
        不行（每个表最多一个聚簇索引）
        可以支持多个索引
        维护成本
        较高，插入数据会破坏排序，需定期整理
        较低

        如何计算 I/O 次数？

        以下是数据库操作中常见的 I/O 操作流程（建议写进你的备考笔记）：

        一般步骤：

        1. 读取从根节点到叶子节点的路径（即索引页路径）。
        1. 读取目标记录所在的数据页。
            • 如果记录分布在多个页中，每页都需要单独一次读操作。
            • 如果使用方案二或三（引用或引用列表），还要考虑是否是聚簇或非聚簇结构。
        1. 写数据页（如果要修改数据，如删除或插入）。
        1. 更新索引页（如果必要）。

        示例分析：Alternative 2 + Unclustered

        notion image
        如下图所示是一个 B+ 树结构（方案二 + 非聚簇）：
        我们想从数据库中删除唯一一个 age = 11 的记录，需要几次 I/O？

        分析如下：

        • 第一步：读取两层索引页（根节点 12 和中间节点 [7, 11]）：
            • → 2 次 I/O
        • 第二步：读取记录 11 所在的数据页（从磁盘读入内存）：
            • → 1 次 I/O
        • 第三步：将数据页写回磁盘（已删除记录）：
            • → 1 次 I/O
        • 第四步：因为这条记录是唯一一个 key=11 的记录，现在整个树中也没有 11 了，
            • 所以我们要从 B+ 树的叶子节点中删除键 11，并将这个页也写回磁盘：
            → 1 次 I/O

        总结：总共 5 次 I/O

        操作
        次数
        读取索引页
        2
        读取数据页
        1
        写数据页（删除记录）
        1
        写索引页（删除 key=11）
        1
        合计
        5 次 I/O

        批量加载（Bulk Loading）

        为什么要用批量加载？

        之前我们讲的插入方式适合向已有 B+ 树中插入新值。
        但如果你是从头构建一棵 B+ 树（如建立索引），那么逐个插入会：
        • 每次都要遍历整棵树 → 效率低
        • 叶子页利用率低（一般插入时只有半满）
        • 随机写导致缓存利用率差
        因此更推荐使用：Bulkloading 批量加载方式。

        批量加载步骤：

        1. 根据索引键对数据排序（准备数据）。
        1. 填充叶子节点，直到达到填充因子 ff（如 f=3/4f = 3/4）。
            • 填充因子只适用于叶子节点。
        1. 为每个叶子页添加父节点指针。如果父节点溢出，就像普通插入一样处理：
            • 将父节点拆分成两个节点：
              • 左节点保留 d 个键
              • 把右节点的第一个键 移动（move） 到上一级父节点中
        1. 调整指针

        示例：插入 1 到 20 到一个阶为 d=2d = 2 的 B+ 树

        • 填充因子为 34\frac{3}{4}

        第一步：填满一个叶子页（1, 2, 3）

        notion image

        继续插入直到溢出，构建出如下结构：

        notion image
        你可以看到，每个叶子节点都被填到 3/4 满，并且内节点已经开始引导搜索。

        最后当内节点也溢出时，会继续向上分裂并建立新根节点：

        notion image

        总结：

        • 使用 批量加载构建的索引，天然就是聚簇的（Clustered），因为数据本身是按键排序的。
        • 想保持聚簇特性，可通过合理设置填充因子，预留未来插入空间。
         
         
        Relate Posts :
        数据库
      • database
        • Database System（三）DS1.1 DiskSpaceManager 设计
        Loading...
        Catalog
        0%