数据库索引
**索引(index)**是数据库最核心的性能技术:以额外的空间与写代价,换取按某个搜索码定位记录的效率。没有索引,任何"WHERE 列 = 值"都必须全表扫描;有了索引,同样的查询往往只需要 3 – 5 次页面 I/O。本章按索引家族依次讨论:顺序索引与 B+ 树、散列索引、多码访问、写优化索引(LSM)、位图索引、以及针对时空数据的专用索引。
14.1 基本概念
搜索码(search key):用于组织索引的一列或几列的组合。索引提供的功能是:给定搜索码值 ,快速找出所有具有该搜索码的记录(或其位置)。
按不同维度可分类:
| 维度 | 类别 | 说明 |
|---|---|---|
| 存储组织 | 顺序索引 vs 散列索引 | 前者按码有序,支持范围;后者靠哈希函数 |
| 与数据关系 | 聚簇索引 clustering vs 非聚簇/辅助索引 secondary | 聚簇:数据物理顺序 = 索引顺序,一表一份;辅助:数据顺序无关 |
| 覆盖度 | 稠密索引 dense vs 稀疏索引 sparse | 每条记录一个索引项 / 每页一个索引项 |
| 唯一性 | 唯一索引 vs 非唯一索引 | 是否允许同一搜索码值出现多次 |
| 结构 | B+ 树、B 树、哈希、位图、LSM、R 树、GiST … |
评估一个索引的常用指标:
- 查找时间(access time):一次点查或范围起点定位的时间/I/O 次数。
- 插入时间、删除时间:维护成本。
- 空间开销(space overhead)。
- 对何种查询有帮助:等值?范围?前缀?多码?
14.2 顺序索引
顺序索引(ordered index)按搜索码值排好序,通常存成 <搜索码值 K, 指向记录的指针 P> 的有序数组或树。它天然支持等值查找与范围查询。
14.2.1 稠密索引和稀疏索引
稠密索引(dense index):对每条记录都建立一个索引项。
稀疏索引(sparse index):只对每个"数据块"的第一条记录建立索引项,块内其余记录靠顺序扫找到。前提是数据文件本身按码有序(即索引是聚簇的)。
对比:
| 特性 | 稠密索引 | 稀疏索引 |
|---|---|---|
| 索引项数 | = 记录数 | ≈ 页数 |
| 空间 | 大 | 小 |
| 点查 | 一步定位 | 定位到页后需页内二分 |
| 范围查询 | 支持 | 支持(数据必须有序) |
| 插入维护 | 每次插入都要更新 | 只在跨页时更新 |
| 与数据的关系 | 可聚簇也可辅助 | 只能聚簇 |
| 支持非聚簇场景 | 是 | 否 |
图示(稀疏索引):