MySQL索引底层数据结构与算法_能说说mysql索引底层b+树结构与算法吗

什么是索引？

索引，其实就是帮助MySQL高效获取数据的排好序的数据结构。索引最形象的比喻就是图书的目录。注意只有在大量数据中查询时索引才显得有意义。

在MySQL中，存在多种不同的索引，常见的索引分类如下：

按数据结构分类：B+tree索引、Hash索引、Full-text索引。
按物理存储分类：聚集索引、非聚集索引（也叫二级索引、辅助索引）。
按字段特性分类：主键索引(PRIMARY KEY)、唯一索引(UNIQUE)、普通索引(INDEX)、全文索引(FULLTEXT)。
按字段个数分类：单列索引、联合索引（也叫复合索引、组合索引）。

MySQL 的索引类型，在不同存储引擎和存储场景中，使用的索引结构和类型是不一样的，如图：

索引介绍和联系

接下来将按照 B树、B+树、Hash结构、聚集索引、非聚集索引和联合索引的顺序，介绍每一种类型索引的区别和联系。

1.B树结构

B树跟传统二叉树的区别：

• B树一个节点可以存储多个元素，从左到右按从小到大排列
• B树每个元素都包含索引列和实际数据，找到索引列，可以直接访问到该元素实际的数据
• B树的叶子节点的指针全部都为空
• B树所有的索引元素不会重复

2.B+树结构

MySQL的索引，当使用的索引方法是 BTREE 时，使用的索引结构就是B+树，而非B树。

相比于B树，B+树有以下特点：

• B+树每个非叶子节点索引元素只记录索引列，不记录实际数据（索引会冗余）
• B+树叶子节点之间，组成双向链表，链表从左到右按照从小到大排列，可以进行范围查询和访问
• B+树的冗余索引+双向链表特性，导致B+树叶子节点包含所有索引字段
  

3.Hash结构

Hash结构的特点：

• 只需对索引进行一次哈希，就能找到数据对应的位置
• 很多时候 Hash 索引比 B+ 树索引高效
• Hash 索引只能处理 =，IN 查询，不支持范围查询
• 存在 Hash 冲突问题

4.聚集索引

聚集索引使用的是B+树结构，存储数据的特点，是叶子节点会存储所有该索引列对应的所有数据，也就是MySQL表中一行所有的字段值。

这就代表着，索引列和该列对应的所有数据，在物理磁盘上，存放在相同一块地方，找到索引列就能找到该数据行所有字段信息。

InnoDB 的数据表如果有主键，MySQL 会自动构建一个主键索引结构，用于通过主键快速查找。

5.非聚集索引

非聚集索引和聚集索引的区别，就是非聚集索引的叶子节点存放的不是所有数据，而是指向数据行的指针，找到索引后，还需要根据该指针，访问真实存放数据的地址。

这一特点，就代表着非聚集索引需要回表查询，势必会对MySQL的查询性能造成一定的影响，没有聚集索引的效率高。

InnoDB 的非主键索引和 MyISAM 的索引，都是非聚集索引，然而这两种非聚集索引还些不同的。

①.InnoDB 非聚集索引

如下图所示，InnoDB 的非聚集索引，如普通索引，叶子节点的数据存放的是索引列+主键值，普通索引查找到主键值之后，还需要去聚集索引查询该主键值对应的所有数据（传说中的回表查询）。

②.MyISAM

MyISAM 的索引都是非聚集索引，原因是 MyISAM 的索引存放文件和表真实数据存放文件，是两个文件，也就是说，索引和数据放在不同文件中。

这就造成 MyISAM 每次通过索引查找到数据地址之后，必须通过访问该地址获取到真实数据。

6.联合索引

以联合索引 （a，b，c）为例，索引的每个节点，都分别包含 a，b，c 三列对应的值，且从上到下依次排列，根据最左匹配原则，匹配优先级从左到右依次是 a、b、c，匹配到叶子节点时，获取到该索引所在数据行的主键 id，然后再根据主键 id，到聚集索引中查询对应的实际数据（回表查询）。