深入理解Mysql索引底层数据结构与算法
索引是 MySQL 用来加速查询的有序数据结构,通过 B+Tree(或哈希)可把全表扫描降为几次磁盘 I/O。文章概述了二叉树、红黑树、哈希、B‑Tree 与 B+Tree 的特性,重点说明 B+Tree 只在叶节点存数据、非叶节点仅存键并采用双向链指针,从而提升区间访问效率。随后比较 InnoDB(聚集索引,表数据本身即 B+Tree)和 MyISAM(非聚集索引分离)的文件布局,阐述主键应为整型自增以保持索引稳定。进一步解释二级索引、联合索引的回表过程及左前缀原则,指出冗余索引的产生。最后说明 B 树与 B+Tree 的区别,并论证 MySQL 选用 B+Tree 能降低树高、减少 I/O,从而实现高效查询。