mysql索引原理面试如何回答（关于MYSQL索引数据结构面试题剖析）

首先我们先看几个问题：（答案在文章尾）

1、存储引擎是基于数据库还是表的？

2、聚集（簇）索引和非聚集（簇）索引的区别是什么？

3、为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？

4、为什么非主键索引结构叶子节点存储的是主键值？

索引的本质是什么？

索引是帮助MySQL高效获取数据的、排好序的数据结构。

数据结构

这里推荐一个网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

网址样式

1、二叉树：索引有序时会产生链表。

二叉树-索引有序时会产生链表

2、红黑树：高度不可控，使用时多次磁盘IO （从根节点找到9，进行4次磁盘IO）

3、Hash：

1）、对索引key进行一次hash运算就可以定位出数据存储的位置

2）、很多时候Hash索引比B 树效率更高

3）、仅能满足“=”，“IN”，无法支持范围查询。所以99.9%都不是Hash索引

4）、会产生Hash冲突

4、B Tree：

1）、叶节点具有相同的深度，叶节点的指针为空

2）、所有索引元素不重复

3）、节点中的数据索引从左到右递增排列（有序）

5、B Tree：MySQL使用B Tree作为索引的数据结构。（从根节点找到9，进行3次磁盘IO）

1）、非叶节点不存储data，只存储索引，可以放更多的索引。

2）、叶节点包含所有索引字段。

3）、叶子节点用指针链接，提高区间访问的性能。

4）、数据索引递增。

B Tree

• B Tree的一个节点大小为“1页”，默认大小是16k（不建议修改，SHOW GLOBAL STATUS LIKE 'InnoDB page_size），对于大部分业务，一页足够。
• 在B Tree中，非叶子节点存的是key 指针；叶子节点存的是数据行 指针。
• 对于叶子节点，假设一行数据 指针大小为1k，那么一页可以存放16条数据；对于非叶子节点，如果key使用的是bigint，则为8字节，指针在mysql中为6字节，一共是14字节，则16k能存放 16 * 1024 / 14 = 1170 个索引指针。对于高度为3的B Tree，可以存放 1170 x 1170 x 16 = 21902400 条数据，也就是对于两千多万条的数据，我们只需要高度为3的B 树就可以完成，通过主键查询只需要3次IO操作就能查到对应数据。所以在B Tree高度一般为3层时，就能满足千万级的数据存储。
• 如是使用B Tree，在存放2000万数据时，树的高度会远大于3，因为B Tree的非页节点包含数据data，每一层只能容纳16条数据。
• B Tree和B Tree的区别在于B Tree的非叶节点不包含data数据，B Tree的叶节点之间有指针。

熟悉完数据结构，下面看一下存储引擎

MyISAM存储引擎索引实现

MyISAM的索引文件和数据文件是分离的 – 非聚集（簇）索引

MyISAM存储引擎

叶子节点保存的data是数据所在行的磁盘文件地址，查找时，经过索引找到磁盘文件地址，根据地址可以直接去数据文件取出数据（回表）。

InnoDB存储引擎索引实现

表数据文件本身就是按B Tree组织的一个索引结构文件 --聚集（簇）索引

主键索引的数据结构：

叶子节点保存的data即是表中的数据，查找时，找到目标索引后可直接取出数据。

二级索引的数据结构：

叶子节点保存的data的主键id,通过二级索引定位主键id，如果索引列包含查询列，可以直接取出数据。否则通过主键id在主键索引中取出数据（回表）。

联合索引：

联合索引是二级索引的一种，按照索引顺序排序。

问题：

1、存储引擎是基于数据库还是表的？

基于数据库表的，在我们创建表时，可指定存储引擎。

2、聚集（簇）索引和非聚集（簇）索引的区别是什么？

只需要记住一点，聚集（簇）索引的页节点包含完整的数据记录。

3、为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？

如果设置了主键，那么InnoDB会选择主键作为聚集索引。如果没有显式定义主键，则InnoDB会选择第一个不包含有NULL值的唯一索引作为主键索引。如果也没有这样的唯一索引，则InnoDB会选择内置6字节长的ROWID（递增）作为隐含的聚集索引。（我们能做的，就不麻烦MySQL）

使用自增主键的好处是每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，主键的顺序按照数据记录的插入顺序排列，自动有序。当一页写满，就会自动开辟一个新的页。如果无序的话要频繁地调整数据接口。

4、为什么非主键索引结构叶子节点存储的是主键值？

节省内存空间、一致性。

,