mysql中普遍使用BTree做索引但在实现上又根据聚簇索引和非聚簇索引而不同。1、聚簇索引所谓聚簇索引就是指主索引文件和数据文件为同一份文件聚簇索引主要用在Innodb存储引擎中。在该索引实现方式中BTree的叶子节点上的data就是数据本身key为主键如果是一般索引的话data便会指向对应的主索引如下图所示在BTree的每个叶子节点增加一个指向相邻叶子节点的指针就形成了带有顺序访问指针的BTree。做这个优化的目的是为了提高区间访问的性能例如上图中如果要查询key为从18到49的所有数据记录当找到18后只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点极大提到了区间查询效率。2、非聚簇索引非聚簇索引就是指BTree的叶子节点上的data并不是数据本身而是数据存放的地址。主索引和辅助索引没啥区别只是主索引中的key一定得是唯一的。主要用在MyISAM存储引擎中如下图非聚簇索引比聚簇索引多了一次读取数据的IO操作所以查找性能上会差。3、B 树查询全过程3.1 等值查询 where id 5001.内存读取根节点比对索引 key找到500对应的下层分支页指针2.磁盘IO读取中层分支页再次比对 key定位对应叶子页3.磁盘IO读取叶子页遍历页内有序数据找到 id500完整行返回3.2 范围查询 where id between 100 and 5001.先通过上层索引定位到 key100所在的叶子页2.直接顺着叶子节点的链表向后遍历直到 key500停止3.全程不再访问上层非叶子节点区间查询效率极高。4、InnoDB 聚簇索引 vs MyISAM 非聚簇索引 B 树差异两者底层都是 B 树但叶子存储内容完全不同。InnoDB 主键聚簇索引B 树叶子节点存储完整一行数据所有字段数据表本身就是一棵 B 树数据和索引绑定二级索引普通索引B 树叶子不存完整数据只存主键值查询普通索引后需要回表拿到主键再去主键 B 树查完整数据。MyISAM 索引 B 树非聚簇数据表文件和索引文件分离主键 / 普通索引 B 树叶子节点只存数据行的磁盘物理地址查询到地址后再去数据文件读取行数据没有聚簇概念所有索引结构完全一致。5、 B 树对比 B 树五大核心优势1.非叶子节点无数据单页容纳更多索引 key树更低磁盘IO更少B树节点存数据一页只能放少量 key分支少树更高B树目录页极度精简分叉多树高度稳定2~3层2.所有查询IO次数稳定性能均衡B树可能在中层节点命中数据IO少也可能要走到叶子IO多性能波动大。B树任何查询都必须走到叶子IO次数固定数据库性能可控。3.范围查询、排序、limit、分组极强 叶子有序链表区间遍历无需回溯上层连续读取磁盘页即可B树区间查询需要反复搜索整棵树。4.全表扫描效率极高 全表扫描只需遍历叶子链表顺序读取磁盘B树需要逐层遍历整棵树随机IO多。5.缓存友好内存利用率高 非叶子节点纯索引体积小数据库缓冲池可以缓存大量目录页减少磁盘读取B树节点混存数据能缓存的索引目录极少。