3.2.1 按数据结构划分

MySQL 支持多种底层数据结构的索引，以满足不同查询场景的需求。从数据结构的角度划分，索引主要分为B+ 树索引、哈希索引、全文索引（倒排索引）和空间索引（R 树）四种类型。它们是决定索引行为、性能和适用场景的根本所在。🌲 一、B+ 树索引 —— 关系型数据库的默认之选B+ 树是 MySQL 中最重要、使用最广泛的索引结构，InnoDB 和 MyISAM 引擎的常规索引都建立在 B+ 树上。1. 数据结构本质多路平衡搜索树：每个节点可以包含多个键和子指针（扇出大），所有叶子节点在同一层，保证绝对平衡。内部节点仅存键：用于导航，不保存完整数据，使一个节点能容纳更多键，进一步降低树高。叶子节点存完整数据：聚簇索引存整行，二级索引存索引键 + 主键值。叶子节点形成有序双向链表：支持高效的范围扫描和正/反序遍历。2. 与磁盘 I/O 的适配节点大小等于一个磁盘页（默认 16KB），一次 I/O 恰好读取或写入一个节点。树高极低（通常 2~4 层），百万行数据仅需 2~4 次 I/O 即可完成定位。内部节点的高扇出（可达数百）使得树形“矮胖”，最小化随机 I/O。3. 核心操作与性能等值查找：O(log N)，路径固定，稳定快速。范围查找：找到起始叶子节点后，沿双向链表顺序扫描，I/O 主要是顺序读，性能极高。排序：由于叶子有序，ORDER BY索引列可直接利用索引顺序，无需额外排序。插入/删除：可能触发页分裂或页合并，自增主键可最大程度减少分裂，保持空间利用率。4. 在 InnoDB 中的具体体现聚簇索引：以主键构建的 B+ 树，叶子节点存放行数据。二级索引：以非主键列构建的 B+ 树，叶子节点存放主键值，需回表。