IBM DB2索引结构详解 | AI生成和翻译
IBM DB2 索引工作原理
IBM DB2 使用 B+ 树 作为其索引的主要数据结构。这是一种平衡树变体，针对基于磁盘的存储和关系数据库中常见的范围查询进行了优化。B+ 树确保了高效的搜索、插入和删除操作，具有对数时间复杂度（O(log n)），使其非常适合大型数据集。下面，我将解析其结构、关键操作以及 DB2 特有的注意事项。
DB2 中的 B+ 树结构
DB2 中的 B+ 树被组织成一个由 页（也称为节点）构成的层次结构，每个页在磁盘上通常为 4KB 大小。该树是自平衡的，意味着所有叶节点都位于同一深度，并且它会随着数据变化动态增长或收缩。具体结构如下：
-
根页：树的顶层入口点。它包含排序后的键值以及指向其下方子页的指针。对于小型索引，根页可能直接指向叶页。
- 内部（非叶）页：这些中间层充当目录。每个页包含：
- 一个排序的 索引键 列表（来自索引列的值，例如员工 ID）。
- 指向子页的指针（指针数量比键多一个，用于分隔范围）。
- 具体来说，每个条目是其下方子树中的 最高键值，与一个 记录标识符（RID） 配对——RID 是一个指向表中实际数据行所在页和槽位的唯一指针。
非叶页不存储实际的数据指针；它们仅用于引导遍历。
- 叶页：最底层，通过双向链接（向前和向后）以实现高效的范围扫描。每个叶页包含：
- 来自索引列的完整排序 键值。
- 关联的 RID，直接指向表行。
- 指向相邻叶页的指针，支持顺序访问（例如，用于
WHERE column BETWEEN x AND y）。
该树至少从 2 层开始（根页 + 叶页），对于海量表（数百万行）可以增长到 3–5+ 层。层数（NLEVELS）可通过 SYSCAT.INDEXES 查询，并影响性能——层数越少，遍历越快，但 DB2 会自动管理这一点。
索引与表分开存储在自己的表空间中，消耗的磁盘空间与索引数据量成正比（例如，一个包含 100 万行表的唯一索引可能占用约表大小的 10–20%）。
搜索工作原理
- 从 根页 开始，并将其加载到内存中。
- 将搜索键（例如
WHERE id = 123）与当前页中的排序键进行比较。 - 选择合适的子指针（例如，如果搜索键 > 当前键，则向右）。
- 沿着树向下重复（通常为 1–5 次 I/O 操作），直到到达 叶页。
- 在叶页中，扫描排序键以查找匹配项，然后使用 RID 从表中获取确切的行（再进行一次 I/O）。
这种路径压缩保持了遍历的浅层性。对于范围查询，一旦到达起始叶页，就可以跟随兄弟链接顺序扫描，无需跳回树的上层。
插入与删除
- 插入：
- 遍历到正确的叶页（如同搜索）。
- 将新的键 + RID 插入到排序后的叶页中。
- 如果页溢出（超过最大条目数，约 200–500 个，取决于键大小），则将其拆分为两个页，并将一个分隔键插入到父（内部）页中。
- 如果父页溢出，则向上拆分（可能创建新的根页）。DB2 会短暂锁定页以实现并发。
- 删除：
- 遍历到叶页并移除键 + RID。
- 如果页下溢（条目过少），则从兄弟页借用条目或与其合并，并从父页中移除分隔键。
- 如果需要，向上传播合并操作。DB2 可能会延迟重组以批量处理更改，提高效率。
这些操作自动保持平衡，页拆分/合并的发生频率极低（约占总操作的 1%）。
DB2 特有功能
- 优化型 B+ 树（在 DB2 for z/OS 中）：针对大型机并发性进行了增强，具有分形预取功能，可预测并预加载页，减少 I/O。
- 聚簇：索引可以设置为“聚簇”（数据按索引顺序物理排序），以提高范围查询性能。
- 类型：支持唯一索引、复合（多列）索引和位图索引，均基于 B+ 树。无原生哈希索引。
- 维护：批量更改后运行
RUNSTATS以更新优化器的统计信息。使用INSPECT等工具检查问题。
B+ 树在 DB2 中表现出色，因为它们最大限度地减少了随机 I/O（对于磁盘密集型系统至关重要），并支持无需全表扫描的排序访问。
索引结构 - IBM
DB2 LUW 索引：B-树详解
深入 Db2 for z/OS：优化型 B+ 树如何驱动高速索引
如何快速理解 DB2 B-树索引
Db2 索引概述