Lecture 7：数据索引¶

本讲介绍数据库中数据的存储方式、记录与磁盘文件组织、散列文件，以及从简单索引到多级索引和 B+ 树索引的基本原理。

学习目标¶

说明记录、文件和磁盘块的关系，以及堆文件、顺序文件和散列文件的差异。
区分静态散列、可扩展散列与动态散列，并理解冲突处理。
比较稠密索引、稀疏索引和多级索引。
解释 B 树与 B+ 树的节点结构，以及 B+ 树的插入和删除过程。

1. 数据存储与数据库类型¶

存储介质（storage medium）负责保存数据并支持后续检索。存储层次（memory hierarchy）通常以更慢的访问速度换取更大的容量和更低的单位成本，因此数据库会尽量减少昂贵的磁盘 I/O（input/output，输入/输出）操作。

关系数据库管理系统（relational database management system，RDBMS）按照关系模型组织数据，并常使用结构化查询语言（Structured Query Language，SQL）查询和维护数据。NoSQL 是“Not Only SQL”的统称，覆盖不遵循传统关系数据库原则的多种数据存储模型，并不表示这些系统完全不使用 SQL。

常见 NoSQL 数据库模型包括：

模型	数据组织方式	常见场景
文档数据库（document database）	将记录保存为可嵌套的文档，常见格式包括 JSON	内容管理、应用数据、监控信息
图数据库（graph database）	以顶点（vertex）和边（edge）表示实体及其关系	路径搜索、推荐、关系网络
键值存储（key-value store）	以唯一键关联一个值，值可以是复杂对象	缓存、会话、日志和快速键查找
宽列存储（wide-column store）	按列族（column family）组织大量稀疏列	大规模分布式数据和网络服务

创建、读取、更新、删除（Create, Read, Update, Delete，CRUD）是数据管理中的基本操作。不同数据模型在读写性能、查询灵活性、扩展方式和一致性方面各有取舍。

2. 记录、文件与磁盘块¶

记录（record）由多个字段（field）组成；文件（file）是记录的集合，在关系数据库中可对应一张表。记录可以是固定长度，也可以是可变长度。

磁盘与内存之间以块（block）为单位传输数据。若一个块可以容纳多个记录，将多个记录放入同一块称为记录分块（record blocking）。合理分块能减少读取同一批记录时的磁盘访问次数，但查找单条记录仍取决于文件组织方式和可用的索引。

3. 文件组织方式¶

3.1 堆文件与顺序文件¶

**堆文件（heap file）**不按搜索字段排序，新记录通常追加到文件末尾，插入简单。若没有索引，查找通常需要线性扫描，平均约检查一半数据块，最坏需检查全部数据块。
**顺序文件（ordered/sequential file）**按指定排序字段存放记录，按该字段顺序读取较高效。插入时必须维护顺序，成本较高；一种折衷方法是先把新记录放入独立的溢出文件，再定期与主文件合并。

堆文件偏向快速插入，顺序文件偏向有序扫描；若查询经常按其他字段定位记录，通常还需要额外索引。

3.2 静态外部散列¶

磁盘散列（external hashing）将文件划分为固定数量的桶（bucket）。给定搜索键 K，散列函数 h(K) 将其映射到一个桶号，记录便存入对应桶。若桶已满，不同键映射到同一桶时就发生冲突（collision）。

常见的冲突解决方法是链接溢出桶（chaining）：为溢出记录分配额外位置，并在主桶中保存指向溢出位置的指针。查找时先定位主桶，再沿指针继续检查。散列函数应尽量均匀分布键值；溢出链越长，查找就越慢。课件建议让静态散列文件保持约 70%–80% 的占用率，以减少溢出。

静态散列桶数固定，随着数据增长可能产生大量溢出；数据缩小时也难以高效回收空间。可扩展散列和动态散列允许目录随数据增减：

**可扩展散列（extendible hashing）**使用数组目录，目录大小为 2^d，d 称为全局深度（global depth）；每个桶还可有自己的局部深度。
**动态散列（dynamic hashing）**用二叉树形式的目录逐步定位桶。

两者通常依据散列值的二进制位选择目录项。桶满时拆分桶并重新分配记录，再更新目录；目录可按需要扩展或收缩。

散列适合等值查找，例如 WHERE id = ?，但不擅长范围查询或按键顺序遍历，因为散列后的物理位置不保留键的大小顺序。

4. 索引¶

索引（index）是额外维护的辅助结构，为数据文件提供另一条访问路径。索引项通常包含 <索引字段值, 指针>，按索引字段值排序；查询可先搜索较小的索引文件，再用指针定位数据记录。索引能减少数据扫描，但会占用存储空间，并增加插入、更新和删除时的维护成本。

4.1 稠密索引与稀疏索引¶

**稠密索引（dense index）**为每个搜索键值（通常对应每条记录）保存索引项，查找路径直接，但索引较大。
**稀疏索引（sparse index）**只为部分搜索键值保存索引项，空间更小。定位到相邻索引项后，还需在对应的数据块或区间内继续搜索。

稀疏索引一般依赖数据文件已经按索引字段排序；若数据未排序，单个稀疏索引项无法代表连续的键值区间。

4.2 多级索引¶

索引文件本身也是有序文件，因此可以为索引再建立索引。原索引称为第一级，指向它的索引称为第二级；如此递归构建，直到最高层能放入一个磁盘块。查找从顶层逐级向下，缩小需要读取的索引范围。多级索引的每一层都会带来维护开销，但能降低大索引文件的查找 I/O。

5. 树索引¶

树（tree）由多层节点组成。根节点没有父节点；内部节点（internal node）有子节点；叶节点（leaf node）没有子节点。若叶节点处于不同深度，树称为不平衡树（unbalanced tree）。索引常使用平衡树结构，使查找路径长度受控。

5.1 B 树¶

B 树（B-tree）节点可同时包含键值、子树指针和数据指针。对阶数为 p 的节点，最多有 p 个子树指针；非根内部节点至少有 ceil(p/2) 个子树指针。每个节点内的键有序，子树指针所覆盖的键值范围由相邻分隔键决定。B 树所有叶节点位于同一层，因此查找路径长度均衡。

5.2 B+ 树¶

多数动态多级索引使用 B+ 树（B+ tree），它将数据指针集中保存在叶节点：

内部节点保存分隔键和子树指针，用于决定下一步沿哪条路径查找。
叶节点保存搜索键和数据指针，并通常通过 Pnext 指针串接相邻叶节点。
所有叶节点在同一层，且键值有序；叶节点链使范围查询和顺序扫描可以连续向前访问。

由于内部节点不存数据指针，同样大小的节点可以容纳更多分隔键和子树指针，树的分支因子更大，通常可以减少层数。若阶数为 p，内部节点最多 p 个子树指针；非根内部节点至少 ceil(p/2) 个。课件的叶节点结构以键和数据指针组成，并另存指向下一叶节点的指针；除根等特殊情况外，叶节点至少容纳 ceil((p-1)/2) 个键值。

5.3 B+ 树插入¶

从根节点开始，按分隔键选择子树，直到找到目标叶节点。
若叶节点有空位，将新键和数据指针按序插入。
若节点已满，将键值分配到两个节点，使两边尽量均衡。
叶节点分裂时，将右侧新叶节点的最小键复制到父节点作为新的分隔键；记录仍保留在叶节点中，并更新叶节点链。
若父节点也满，则继续向上分裂。若根节点分裂，则创建新的根节点，树高增加一层。

内节点分裂时，分隔键会向父节点提升；具体分裂位置和边界键细节取决于实现采用的阶数定义。无论实现如何，分裂后都必须保持键值范围、节点占用约束和叶节点链正确。

5.4 B+ 树删除¶

从根节点定位包含目标键的叶节点，并删除键及其数据指针。
若节点仍满足最低占用要求，只需在必要时更新父节点中的分隔键。
若节点低于最低占用，优先尝试从相邻兄弟节点重新分配键值，并同步修正父节点的分隔键。
若兄弟节点也没有多余键值，则合并节点，并从父节点删除不再需要的分隔键和子树指针。
若父节点因删除而低于最低占用，则继续向上修复；根节点只剩一个子节点时，可将该子节点提升为新根，树高降低。

删除的修复过程与插入相反：插入可能造成节点过满，需要分裂；删除可能造成节点过空，需要重分配或合并。

6. 选择合适的组织方式¶

访问需求	常见结构	主要权衡
简单追加写入，允许扫描	堆文件	写入轻量；未建索引的查找较慢
按字段排序读取或范围扫描	顺序文件或 B+ 树	有序访问高效；维护顺序或索引会增加写入成本
精确等值查找	散列文件或散列索引	平均定位快；不支持有效的键值范围顺序访问
多字段查询、动态插入和范围查询	一个或多个 B+ 树索引	查询路径稳定；索引占空间且每次写入都要维护

索引优化应从实际查询模式出发：索引能减少读取量，但不一定让所有查询更快。字段基数、过滤选择性、数据规模、写入频率和查询计划都会影响效果。