参考：https://javaguide.cn/database/mysql/mysql-index.html#非聚簇索引介绍

不同引擎有不同的实现，在InnoDB引擎中，MySQL 索引的底层是B+树实现的。

b树：多路平衡树

b+树：b树基础上的变种

红黑树：自平衡二叉搜索树

b+树是什么，优缺点是什么？

b+树是一棵平衡N叉树，它是b树的一种变体，它跟b树有几个方面的不同：

• 首先，是b树的数据是所有节点都有的，而b+只存放在叶子节点，并且，b+树的叶子节点类似链表一样连接起来；这样做有几个好处，
  • 第一是整棵b+树更加矮胖，那么一次查询需要的I/O次数会更少，而磁盘I/O比较耗时，这样可以提升查询效率；
  • 第二是b+树对范围查询（顺序查询）更加友好，叶子节点连接在一起，我们只要找到头结点，就是顺着链表查下去，而b树就麻烦许多，得用中序遍历的方式去查询。

为什么不使用哈希表呢？

因为哈希表不支持顺序查询和范围查询，当然，MySQL 中存在自适应哈希表，作为内存索引，加速查询。

Active Hash Index：https://mp.weixin.qq.com/s/ra4v1XR5pzSWc-qtGO-dBg

聚簇索引和非聚簇索引

「聚簇索引」：即索引结构和数据一起存放的索引，并不是一种单独的索引类型。InnoDB 中的主键索引就属于聚簇索引。

「非聚簇索引」：即索引结构和数据分开存放的索引，比如二级索引（辅助索引）就是非聚簇索引，叶子节点只记录了主键，需要根据主键回表，查出数据。

为什么非聚簇索引的叶子节点不存放指向数据的指针？

• 数据一致性维护简单：
  • 如果非聚簇索引存储的是物理指针，当表数据发生变动（例如，数据行被移动到磁盘的其他位置以维持 B+ 树平衡，即 页分裂）时，所有指向该行的非聚簇索引的物理指针都需要更新。这是一个巨大的开销。
  • 而存储主键值则非常稳定。无论数据行在聚簇索引中如何移动，它的主键值是不变的。非聚簇索引不需要做任何修改，因为它们指向的是逻辑上的主键，而不是物理上的位置。