数据库索引的分类和底层数据结构直接决定了它在不同场景下的性能和适用性。以下是数据库索引的主要分类及其底层数据结构的详细分析：
一、数据库索引的分类
1. 主键索引（Primary Key Index）
- 分类：唯一性索引的一种特殊形式。
- 特点：对主键列创建的索引，保证唯一性且不能为空。
- 底层结构：B+树。
2. 唯一索引（Unique Index）
- 分类：确保列中的值唯一，但可以包含空值。
- 特点：每个表可以有多个唯一索引，用于对独立列进行唯一性约束。
- 底层结构：B+树。
3. 普通索引（Non-Unique Index）
- 分类：不对列的唯一性做要求，最常见的索引类型。
- 特点：支持常规的查询加速，允许重复值。
- 底层结构：B+树。
4. 复合索引（Composite Index）
- 分类：在多个列上创建的索引。
- 特点：按指定列顺序建立，遵循“最左前缀原则”。
- 底层结构：B+树。
5. 全文索引（Full-Text Index）
- 分类：专门用于大文本字段搜索的索引。
- 特点：基于分词进行全文检索，支持复杂的文本查询。
- 底层结构：倒排索引（Inverted Index）。
6. 空间索引（Spatial Index）
- 分类：用于地理空间数据（如坐标、地图位置）的索引。
- 特点：支持多维数据的范围查询。
- 底层结构：R树（R-Tree）。
7. 聚集索引（Clustered Index）
- 分类：索引顺序与物理存储顺序一致的索引。
- 特点：通常用于主键索引，每个表只能有一个聚集索引。
- 底层结构：B+树。
8. 非聚集索引（Non-Clustered Index）
- 分类：索引顺序与物理存储顺序无关的索引。
- 特点：每个表可以有多个非聚集索引，独立于数据存储。
- 底层结构：B+树。
9. 哈希索引（Hash Index）
- 分类：基于哈希函数的索引。
- 特点：等值查询效率极高，但不支持范围查询。
- 底层结构：哈希表。
10. 位图索引（Bitmap Index）
- 分类：通过位图表示数据的索引。
- 特点：适合低基数列，适用于组合查询，但不适合频繁更新的场景。
- 底层结构：位图（Bitmap）。
二、数据库索引的底层数据结构
1. B+树（B+ Tree）
- 用途：最常用于主键索引、唯一索引、普通索引和复合索引。
- 结构特点：
- 多路平衡树：节点包含多个键值，树高度低，磁盘I/O次数少。
- 叶子节点链表：所有数据存储在叶子节点，并通过链表连接，支持范围查询。
- 顺序访问效率高：适合范围查询和排序操作。
2. 哈希表（Hash Table）
- 用途：用于哈希索引，主要针对等值查询场景。
- 结构特点：
- 哈希函数映射：通过哈希函数将键值映射到哈希表中的桶（bucket）。
- 不支持范围查询：哈希表只能快速处理等值查询，对于范围查询无效。
3. 倒排索引（Inverted Index）
- 用途：主要用于全文索引。
- 结构特点：
- 关键词映射：倒排索引将每个关键词映射到包含该关键词的文档或记录列表中。
- 分词处理：适用于大文本数据，通过词语的匹配加速查询。
- 高效全文搜索：特别适合搜索引擎和文本数据中的关键词查找。
4. R树（R-Tree）
- 用途：用于空间索引，主要处理二维或多维的空间数据。
- 结构特点：
- 范围查询：通过最小边界矩形（MBR，Minimum Bounding Rectangle）来划分空间数据，支持多维空间范围查询。
- 分层结构：R树的节点存储空间范围信息，非叶子节点存储矩形的边界范围，叶子节点存储数据位置。
5. 位图（Bitmap）
- 用途：主要用于位图索引，适用于低基数（如性别、状态等）的列。
- 结构特点：
- 位数组表示：使用位数组来表示数据的位置，适合数据重复较多的场景。
- 组合查询高效：多个位图可以进行按位操作（如 AND、OR 等），快速计算组合查询结果。
- 不适合频繁更新：因为每次修改需要更新整个位图，频繁更新时效率较低。
6. 跳表（Skip List）
- 用途：Redis等轻量级存储中常用的索引结构。
- 结构特点：
- 多层链表结构：通过引入多层级指针，跳表能够实现接近于平衡树的查询效率。
- 范围查询：跳表支持快速的范围查找，且实现简单。
三、总结
- 常见索引结构：B+树结构是大多数关系型数据库索引的主要实现方式，广泛应用于主键索引、唯一索引和普通索引。它支持快速的查找、插入、删除操作，且能够高效处理范围查询。
- 其他结构：哈希索引适用于等值查询，倒排索引适合全文搜索，R树则处理空间数据查询，而位图索引擅长组合查询但不适合频繁更新。
- 性能权衡：每种索引结构都有其特定的应用场景，合理选择合适的索引类型和结构可以显著提升数据库的查询性能，同时也要平衡插入、更新操作的开销。