9. 索引

1. Motivation (动机)

• 核心目的：加速对所需数据的访问。
  
• 基本原理：如果不使用索引，数据库必须进行全表扫描（Sequential Scan），效率极低。索引文件通常比原数据文件小得多，通过查找索引可以快速定位数据。

★ 重点：索引的优缺点权衡 (Pros & Cons)

这是数据库性能优化的核心矛盾，务必背熟。

维度	优点 (Pros)	缺点 (Cons)
查询性能	极大加快查找速度（Access Types），特别是点查询和范围查询。	-
更新性能	-	降低修改速度。当数据文件被插入、删除或更新时，该文件上的所有索引都必须同步更新，这带来了额外的开销 (Overhead)。
存储空间	-	索引文件本身占用存储空间 (Space overhead)。
扫描性能	主索引（聚集索引）支持高效的顺序扫描。	辅助索引（非聚集索引）的顺序扫描非常昂贵，因为每读一条记录都可能需要一次新的磁盘块访问（I/O）。

---

2. Basic Concepts (核心概念)

2.1 索引的分类

• 有序索引 (Ordered Indices)：搜索键按排序顺序存储。
  
• 哈希索引 (Hash Indices)：搜索键通过哈希函数均匀分布在“桶”中。

2.2 主索引 vs. 辅助索引 (非常重要)

区分标准是：索引顺序与物理存储顺序是否一致。

• Primary Index (主索引) / Clustering Index (聚集索引)
  • 索引的搜索键顺序决定了文件的物理顺序。
    
  • 特点：顺序扫描效率极高。一个文件只能有一个聚集索引。
    
• Secondary Index (辅助索引) / Non-clustering Index (非聚集索引)
  • 索引的顺序与文件的物理顺序不同。
    
  • 强制要求：辅助索引必须是稠密索引 (Dense Index)。

2.3 稠密索引 vs. 稀疏索引

区分标准是：索引项的数量。

• Dense Index (稠密索引)
  • 每个搜索键值都有一个对应的索引记录。
    
  • 特点：查找快，但空间大。
    
• Sparse Index (稀疏索引)
  • 只为部分搜索键值建立索引记录。
    
  • 适用条件：数据记录必须按搜索键顺序排列（通常用于主索引）。
    
  • 查找方法：找到最大的且小于目标值 的索引项，然后从那里开始顺序扫描。
    
  • 优点：空间小，插入/删除维护开销低。

---

3. Methods (具体方法)

3.1 B+ Tree Index (B+ 树索引) —— 考试核心

• 定义：一种平衡树，所有从根到叶子的路径长度相同。
  
• 结构特点：
  • 叶子节点 (Leaf Nodes)：包含指向数据的指针，且叶子节点之间通过指针链表相连 ()，支持高效的顺序访问。
    
  • 非叶子节点：仅作为多级稀疏索引使用。
    
• 性能：
  • 树的高度很低（对数级 ），即使数据量百万级，高度通常也不超过 4 层，因此磁盘 I/O 很少。
    
  • 相比二叉树（高度约 20 层），B+ 树效率极高。

3.2 Hash Indices (哈希索引)

• 原理：利用哈希函数将搜索键映射到桶 (Bucket)。
  
• 桶溢出 (Bucket Overflow)：
  • 原因：桶不够用或数据分布倾斜 (Skew)。
    
  • 处理：使用溢出链 (Overflow chaining)，即链表法。
    
• 静态哈希的缺陷：桶数量固定。数据增长会导致溢出，数据减少会浪费空间，重组代价高。

3.3 Multilevel Index (多级索引)

• 当主索引本身太大无法装入内存时，对索引再建索引（Outer Index -> Inner Index）。

3.4 复合索引与左前缀原则 (Left Prefix Rule)

针对多个属性 建立的索引。

• 原则：
  • 必须从最左列开始匹配。
    
  • 不能跳过中间列。
    
• 范围查询后失效：一旦某列使用了范围查询（, , BETWEEN），其右侧的列无法使用索引。
  
• 例子：索引 。
  • 查询 WHERE A=1 (有效)
    
  • WHERE A=1 AND B=2 (有效)
    
  • WHERE B=2 (无效)

---

4. Examples (典型例题)

例题 1：Dense & Clustering Index 的构建

• 场景：文件原序是 s_dept，要求在 student_name 上建聚集索引。
  
• 操作：
  1. 重排数据：因为是聚集索引，必须改变物理文件，使其按 student_name 排序。
     
  2. 建索引：因为是稠密索引，每个名字都要有索引项。
     
  3. 插入新数据：需要在数据文件和索引文件中同时插入，并保持两者的顺序。

例题 2：SQL 优化与 Update 代价

• 查询优化 (Select)：
  • where building='T3' -> 在 Department(building) 建索引。
    
  • A.department = B.dname -> 在 Student(department) 建索引（加速 Join）。
    
  • age > 20 -> 在 Student(age) 建索引。
    
• 更新代价 (Update)：
  • 语句：update Student set age=age+2 ...
    
  • 后果：在 age 上建立非聚集索引会减慢此操作。
    
  • 原因：除了修改数据，数据库还必须删除旧的索引项（值为 20），并插入新的索引项（值为 22），引发树结构的调整（Split/Merge）。如果是聚集索引，甚至需要搬移数据块，代价更大。

---

复习建议

1. 背诵：聚集索引 vs 非聚集索引的区别（物理顺序是否一致）。
   
2. 理解：为什么 Update 时索引会变慢（维护成本）。
   
3. 应用：看到 SQL 语句（如 WHERE A=1 AND B>2 AND C=3），能立刻判断出复合索引 中只有 A 和 B 能用到索引，C 用不到（因为 B 用了范围）。