MySQL索引底层数据结构详情-木庄网络博客

本文整理自网络，侵删。

一、索引类型

1.B+树

为什么是B+树而不是B树？

首先看看B树和B+树在结构上的区别

B树结构：

B+树：

可以看到：

B树在每个节点上都有卫星数据(数据表中的一行数据)，而B+树只在叶子节点上有卫星数据。这意味着相同大小的磁盘扇区，B+树可以存储的叶子节点更多，磁盘IO次数更少；同样也意味着B+树的查找效率更稳定，而B树数据查询的最快时间复杂度是O(1)。
B树的每个节点只出现一次，B+树的所有节点都会出现在叶子节点中。B+树的所有叶子节点形成一个升序链表，适合区间范围查找，而B树则不适合。

2.MyISAM和InnoDB的B+树索引实现方式的区别(聚簇索引和非聚簇索引)？

首先需要了解聚簇索引和非聚簇索引。

聚簇索引：

在聚簇索引中，叶子页包含了行的全部数据，节点页值包含索引列。InnoDB通过主键聚集数据，如果没有定义主键则选择一个唯一的非空索引列代替；如果没有这样的索引，InnoDB会隐式定义一个主键来作为聚簇索引。

聚簇索引的数据分布：

?在聚簇索引中，除了主键索引，还有二级索引。二级索引中的叶子节点存储的不是“行指针”，而是主键值，并以此作为指向行的“指针”。这意味着通过二级索引查找行，存储引擎需要找到二级索引的叶子节点获得对应的主键值，然后根据这个值去聚簇索引中查找对应的行，也称为“回表”。当然，可以通过覆盖索引避免回表或者InnoDB的自适应索引能够减少这样的重复工作。