15445-08-IndexesFilters（I）
发布于 • 作者: Ethan
Mindmap
一、索引（Indexes）
数据库管理系统（DBMS）中存在多种数据结构，应用于内部元数据、核心数据存储、临时结构或索引等目的。 本讲主要关注索引。
索引是表中部分属性的副本，通过组织和排序实现高效的数据定位。相比顺序扫描，DBMS 可以通过索引快速定位目标元组。
然而，索引数量存在权衡：
- 索引越多，查询越快，但占用更多存储并增加维护开销。
- 多索引还会带来并发一致性问题。
DBMS 的任务是选择最优索引组合以加速查询。
二、B+树（B+ Tree）
B+树是一种自平衡树结构，支持排序、搜索、顺序访问、插入与删除，时间复杂度为 O(log n)。 它针对磁盘数据库优化，将潜在的随机 I/O 转换为顺序 I/O。
几乎所有现代支持有序索引的 DBMS 都采用 B+树。
（一）结构特性
B+树是一个 m 路搜索树（m 为扇出）：
- 每个叶节点深度一致（完全平衡）。
- 除根节点外的内部节点至少半满。
- 含 k 个键的内部节点拥有 k+1 个非空子节点。
节点内部通常保存键/值对数组。
- 叶节点键：由索引属性派生，可存储记录 ID 或元组数据。
- 内部节点值：指向子节点的指针；键仅作为“路标”，不代表实际数据。
（二）插入操作
-
找到正确叶节点 L；
-
将新条目插入并保持排序：
- 若空间足够，结束；
- 若已满，拆分为 L₁ 和 L₂，平均分配并上移中间键。
-
若内部节点也需拆分，重复上述过程。
（三）删除操作
-
找到正确叶节点 L；
-
删除对应条目：
- 若仍半满，结束；
- 否则尝试从兄弟节点借；
- 若借失败，则与兄弟节点合并；
-
若发生合并，需删除父节点中对应指针。
三、复合索引（Composite Index）
索引键可由多个属性组成：
CREATE INDEX abc_index ON table (a, b DESC, c NULLS FIRST);
查询示例：
SELECT a, b, c FROM table
WHERE a = 1 AND b = 2 AND c = 3;
注意：B+树索引通常仅支持
AND条件，不支持OR。
四、B+树的其他应用与性质
（一）选择条件
B+树按键排序，可高效支持部分键匹配。 与哈希索引不同，B+树不要求匹配所有搜索键属性。
（二）重复键
处理重复键的两种方式：
- 将记录 ID附加到键后以保证唯一性；
- 允许叶节点溢出至overflow 节点存储重复键。
（三）聚集索引（Clustered Index）
表数据按主键排序存储，可为堆组织或索引组织。 部分 DBMS 若无显式主键，会自动生成隐藏行 ID。
（四）索引扫描页面排序
对于非聚集索引，DBMS 可先获取所有目标元组并按页 ID 排序，以减少页面读取次数。
五、B+树设计选择（B+Tree Design Choices）
（一）节点大小
- 硬盘型 DBMS：节点较大（MB 级）以减少寻道；
- 内存型 DBMS：节点较小（512B 级）以匹配 CPU 缓存。
选择取决于工作负载类型：
- 点查询倾向小页；
- 顺序扫描倾向大页。
（二）合并阈值
删除操作时可延迟合并，以减少频繁的分裂与合并。 部分系统（如 PostgreSQL）允许暂时不平衡的树结构。
（三）可变长度键
实现方式包括：
- 指针引用键位置；
- 可变长度节点（不常用）；
- 填充至固定长度（浪费空间）；
- 键映射/间接引用：通过字典索引节省空间（PostgreSQL 支持）。
（四）节点内搜索策略
- 线性扫描：简单但慢，O(n)。
- 二分搜索：O(log n)，但插入开销高。
- 插值搜索：利用元数据估算位置，仅适用于特定键类型（如整数）。
六、优化技术（Optimizations）
（一）前缀压缩（Prefix Compression）
若同一节点的键共享相同前缀，只需存储一次前缀，提高空间利用率。
（二）去重（Deduplication）
对于非唯一索引，可仅存储一次键，后接多个值。
（三）后缀截断（Suffix Truncation）
内部节点仅需保存最小前缀即可正确引导查询路径。
（四）指针混洗（Pointer Swizzling）
用内存地址替代页 ID，避免缓冲池查找开销； 当页被释放时需恢复原 ID。
（五）批量插入（Bulk Insert）
初次建树时，可先构造排序好的叶节点链表，再自底向上建立索引。 可选择紧密存储或预留空间以便后续插入。
（六）写优化 B+树（Write-Optimized B+ Tree）
分裂与合并代价高，某些变体（如 Bω树）采用延迟传播方式： 先记录内部节点的更新日志，再异步写入叶节点。
Notes
