mysql索引底层采用b+tree而非b-tree、红黑树或哈希，因其所有数据存于叶子节点且叶子间用链表连接，非叶节点仅存键和指针，树更矮胖、i/o更少，天然支持范围查询和顺序遍历；innodb中主键索引叶子存整行数据，二级索引叶子只存主键值，需回表；联合索引遵循最左前缀原则；b+tree每页可存多键，树高仅3~4层，远优于红黑树的磁盘访问次数，也支持范围查询而非哈希仅等值；主键越小、自增越利于减少页分裂，覆盖索引可避免回表。
MySQL 的索引底层主要使用 B+Tree，而不是简单的二叉树或 B-Tree，这是为了在磁盘 I/O、查询效率和范围扫描之间取得最佳平衡。
为什么选 B+Tree 而不是 B-Tree？
B+Tree 是 B-Tree 的改进变种，核心差异在于：
- 所有数据（即叶子节点）都存储在最底层，且叶子节点之间用双向链表连接；
- 非叶子节点只存索引键值和指向子节点的指针，不存实际数据；
- 因此树更“矮胖”，相同数据量下层级更少，意味着更少的磁盘 I/O 次数；
- 叶子节点链表结构天然支持高效范围查询（如 WHERE id BETWEEN 100 AND 200）和顺序遍历。
B+Tree 在 InnoDB 中的具体实现
InnoDB 的主键索引（聚簇索引）直接将整行数据存于叶子节点，而二级索引（非主键索引）的叶子节点只存主键值。这意味着：
- 通过主键查数据：一次 B+Tree 查找即可定位完整记录；
- 通过二级索引查数据：先查二级索引树拿到主键，再回表查聚簇索引（称为“回表”），共两次 B+Tree 查找；
- 联合索引遵循最左前缀原则，其 B+Tree 的排序按字段定义顺序逐列比较，例如 (a,b,c) 索引中，先按 a 排序，a 相同时按 b，b 也相同时再按 c。
为什么 B+Tree 比红黑树、哈希更适合数据库索引？
数据库索引面对的是海量数据 + 磁盘存储，而非内存小数据集：
- 红黑树是二叉结构，数据量大时树高显著增加（O(log₂N)），一次查询可能要访问十几次磁盘；
- 哈希索引仅支持等值查询，无法做范围查找、排序、模糊前缀匹配（如 LIKE 'abc%'）；
- B+Tree 的每个节点可容纳多个键（通常 1KB~16KB，取决于页大小），大幅降低树高（常见千万级数据仅 3~4 层），单次磁盘读取就能加载整个节点，I/O 效率高。
几个关键细节影响实际性能
真正用好 B+Tree，需关注这些底层行为：
- InnoDB 默认页大小为 16KB，一个节点（页）能存多少索引项，取决于键长度 —— 主键越小（如 BIGINT 比 VARCHAR(255) 好），非叶子节点能容纳更多指针，树更扁平；
- 插入/更新可能导致页分裂（Page Split），尤其是自增主键写入时基本顺序追加，分裂少；而随机 UUID 主键易造成频繁分裂和空间碎片；
- 覆盖索引（SELECT 的字段全部命中索引）可避免回表，本质上就是让查询完全在 B+Tree 的叶子节点完成，无需访问聚簇索引。
