MySQL B+树索引：原理、优势及优化实践

mysql索引的数据结构，为什么用b+树

说到索引，大家都不陌生。
索引本身是一种数据结构，其主要目的是缩短数据检索时间，最小化磁盘IO。

几乎每个有数据的场景都有一个索引，比如手机通讯录、文件系统(ext4\xfs\ntfs)和数据库系统(MySQL\Oracle)。
数据库系统和文件系统一般都使用B+树来存储B+索引信息，同时兼顾读写性能。
logN代表磁盘IO扫描。

MySQL支持四种索引结构：B+树、​​R树、HASH和FULLTEXT。

B树是一种有很多分叉的AVL树。
B-Tree降低了AVL数的高度并增加了每个节点的KEY数量。

树B的特点：（m为阶数：节点最大子节点数）

3如果根节点不是叶节点，她至少有两个Children

特殊情况：根节点没有孩子，即根节点有。
一个叶子节点，整个Tree只有一个根节点

4．P0,K1,P1,K2,P2,...,Kn,Pn)其中：

Ki(i=1...n)是关键字，关键字按升序排列OrderK(i-1)

Pi是指向子节点的指针，指针P(i-1)指向子节点中所有小于Ki但大于Ki的关键字K(i-1)

关键字数量n必须满足：[ceiling(m/2)-1]<=n<=m-1

如果一个节点有n个关键字，则该节点有n+1个分支。
这n+1个关键字按升序排序

所有叶子节点都出现在同一级别，也就是所有遍历的结束位置

MySQL系列（二）—索引分类

上一节介绍了索引的底层数据结构以及MySQL为什么使用B+Tree作为底层结构。
接下来我们深入探讨不同MySQL存储引擎（InnoDB和MyISAM）下的索引分类以及它们之间的区别。

在InnoDB引擎下，表数据文件本身构成B+Tree索引结构，叶子节点包含完整的数据记录，形成聚集索引。
除主键索引外的所有索引都称为辅助索引，辅助索引的叶子节点存储主键值。

InnoDB引擎的数据组织方式是聚集索引，数据和索引存储在同一个文件中。
主键索引查询流程如下：

辅助索引说明了InnoDB引擎下叶子节点存储主键值的特性。
等值查询和范围查询的过程涉及多次磁盘读取和表查询，通过主键值来访问主键索引。

MyISAM索引文件与数据文件分开存储。
索引存储在“.MYI”文件中，数据存储在“.MYD”文件中。
主键索引的叶子节点存储了数据对应的磁盘地址。

查询数据过程涉及多次磁盘读取，但索引与数据的紧密关系仍然可以提高性能。

联合索引是基于多个字段创建的，索引树按照字段的顺序排序。
联合索引查询过程涉及多次磁盘读取。

覆盖索引可以直接从辅助索引中获取需要的数据，避免了返表操作，提高了性能。
创建索引时应考虑覆盖索引的使用。

InnoDB和MyISAM引擎下的索引分类总结，以及联合索引和覆盖索引的概念。
下面将重点介绍SQL优化和索引策略，以提高查询性能。

如有疑问，请指正！