在数据库系统中，聚簇索引和非聚簇索引通常都基于 B+ 树 实现（例如 MySQL 的 InnoDB 引擎）。尽管它们的数据存储方式有所不同，但其底层结构和 B+ 树 的特性相辅相成，适合于高效的查询操作。以下是聚簇索引、非聚簇索引和 B+ 树的详细区别和联系。
1. B+ 树的结构和特点
概念
B+ 树是一种多路平衡树，是数据库和文件系统中常用的数据结构。每个节点存储多个元素，并且 B+ 树具有严格的平衡结构，确保从根节点到每个叶子节点的路径长度相同。B+ 树可以快速定位数据，大幅减少磁盘 I/O 次数。
特点
- 非叶子节点只存储索引值：B+ 树的非叶子节点仅用于存储索引值，而数据存储在叶子节点。
- 叶子节点链表：叶子节点包含指向相邻叶子的链表指针，方便范围查询。
- 平衡性：每次插入或删除操作都保持树的平衡，使得从根到叶子的路径长度相等，确保查询性能稳定。
- 范围查找高效：在 B+ 树的叶子节点中，数据按照索引顺序链接，这使得范围查询效率高。
2. 聚簇索引和 B+ 树的关系
聚簇索引基于 B+ 树来存储数据和索引。在 B+ 树中的叶子节点不仅包含索引值，还包含实际的数据行。
特点
- B+ 树结构：聚簇索引使用 B+ 树的结构，叶子节点存储表的实际数据。
- 物理排序：聚簇索引将数据按索引列的顺序存储在一起，这样数据和索引一体化。
- 快速查询：聚簇索引直接将查询命中在叶子节点上，减少了数据访问的跳转和查找成本。
总结
在 InnoDB 中，聚簇索引的 B+ 树的每个叶子节点存储了完整的行数据，因此查询主键值可以直接通过聚簇索引找到数据，不需要二次查找。
3. 非聚簇索引和 B+ 树的关系
非聚簇索引同样是基于 B+ 树实现的，但其叶子节点只存储索引列值及对应数据位置的指针（或主键值，而不存储完整的数据行）。
特点
- 独立的 B+ 树：非聚簇索引是独立的 B+ 树结构，叶子节点存储索引值和指向数据位置的指针。
- 指向数据行：非聚簇索引的叶子节点不包含实际数据行，因此在查询时需要一次额外的查找来获取数据行。
- 多列索引：非聚簇索引支持多列组合索引，每个组合列都会生成一棵独立的 B+ 树。
总结
非聚簇索引的 B+ 树在查询时需要通过指针或主键再次定位实际数据，通常会有二次查找的开销。
4. 聚簇索引、非聚簇索引与 B+ 树的对比
| 特性 | B+ 树 | 聚簇索引 | 非聚簇索引 |
|---|---|---|---|
| 结构 | 多层平衡树，叶子节点存数据或指针 | 基于 B+ 树，叶子节点存储数据 | 基于 B+ 树，叶子节点存储指针 |
| 叶子节点存储 | 索引值及数据或指针 | 索引值和实际数据行 | 索引值和指向数据的指针 |
| 查询效率 | 高效的范围查询和查找 | 查询主键效率高 | 查询非主键列时有二次查找 |
| 数据物理顺序 | 与索引顺序无关 | 数据和索引顺序一致 | 数据顺序与索引顺序无关 |
| 数据插入影响 | 插入、删除可能引起树重平衡 | 插入、删除影响数据物理顺序 | 插入、删除不影响数据物理顺序 |
总结
- 聚簇索引 使用 B+ 树的叶子节点直接存储实际数据行，表中的数据按照聚簇索引列排序存储。
- 非聚簇索引 使用独立的 B+ 树，叶子节点存储索引值和指向数据行的指针。
- B+ 树 本质是多路平衡树，聚簇索引和非聚簇索引都依赖 B+ 树的结构来提升查询效率。