一、基本概念

1. 索引条目（Index Entries）的基本内容

1. 索引的基本类型
   • 顺序索引（Ordered Index）：search-key 按顺序存储
   • 散列索引（Hash Index）：借助 hash function，search-key 在若干个 数据桶（bucket）之间均匀分布
2. 索引性能的衡量
   • Access / Insertion / Deletion Time
   • Space Overhead（空间开销）

二、顺序索引

1. 在顺序索引中，索引条目按 search-key 的排序顺序存储
2. 顺序排序文件（Sequentially Ordered File）：文件中的记录按 search-key 的排序顺序存储
3. 索引顺序文件（Indexed Sequential File）：包含主索引的顺序排序文件

1. 主索引与辅助索引

1. **主索引（Primary Index）：**与对应的数据文件本身的排列顺序相同的索引

   • 别名：聚集索引（Clustering Index）
   • 主索引的 search-key 通常是主键，但不一定是主键

2. **辅助索引（Secondary Index）：**与对应的数据文件本身的排列顺序不同的索引

   • 别名：非聚集索引（Non-Clustering Index）
   • 意义：当对非主键的其它属性进行查询时，辅助索引可以避免全表扫描
   • 辅助索引不能使用稀疏索引，每条记录都必须有指针指向
   • 为解决重复项的问题，使用 bucket 结构：每个 search-key 都指向一个 bucket，该 bucket 包含指向具有该特定 search-key 值的所有实际记录的指针
   • bucket 结构的替代方案：在 search-key 中加入一个 record-identifier，从而使 search-key 唯一

   **示例：**为 balance 建立辅助索引，使用 bucket 结构解决重复项问题

   

3. 多级索引（Multilevel Index）

   • 意义：解决主索引太大，无法在 Memory 中被容纳的问题

   • 分为内层（Inner Index）和外层（Outer Index），其中外层索引是内层索引的稀疏索引

     

2. 稠密索引与稀疏索引

1. **稠密索引（Dence Index）：**为 search-key 的每个值都建立对应的索引条目

   示例：

   • 下图为 id 的每个值都建立对应的索引条目，故为稠密索引

     

   • 下图为 department 的每个值都建立了对应的索引条目，虽然并未对每个元组都建立对应的索引条目，但它符合稠密索引的定义，故为稠密索引

     

2. **稀疏索引（Sparse Index）：**只为 search-key 的部分值建立对应的索引条目

   • 通常，为每个数据块（block）建立一条索引
   • 稀疏索引依赖于数据的有序性，只能用于顺序文件；而稠密索引可以用于顺序和非顺序文件

   示例：

   

3. B+ 树索引

1. B+ 树基本知识

   • B+ 树是平衡树，从根到叶子的所有路径等长
   • 每个既非根又非叶子的节点具有 $\lceil n/2\rceil$ 至 $n$ 个儿子
   • 若叶子节点不是根节点，则叶子节点具有 $\lceil (n-1)/2\rceil$ 至 $(n-1)$ 个值
   • 若叶子节点是根节点，则该节点具有 0 至 $(n-1)$ 个值
   • 设 B+ 树的度为 $n$，包含 $K$ 个 search-key 值，则树高不大于 $\lceil log_{\lceil n/2\rceil}(K)\rceil$
   • 通常令 B+ 树的节点与磁盘上的数据块（block）等大，即 4K 字节；令每条记录占据 40 字节，则 n 约为 100

   

   在上图的 B+ 树中，n = 4，叶子节点具有 2 或 3 个值

2. B+ 树索引的记录查询