MySQL面试系列：索引数据结构为什么不用B树、二叉树、哈希表？（四）数据库Oooomumuxi的博客-

前言

面试官：MySQL索引的存储结构是什么？
面试者：是B+树。
面试官：为什么不是B树、二叉树、哈希表？
面试者：%……&（&……（懵逼中）

面试官：MySQL有哪几种索引？
面试者：主键索引、唯一索引、联合索引、普通索引。
面试官：什么是聚簇索引、非聚簇索引、覆盖索引、索引下推、最左原则？
面试者：%……&（&……（懵逼中）

接下来我们就通过了解B+树去全面解决这几个问题。

一、B+树的数据结构

树的概念我的就赘述了，其他文章都写的非常清楚了。
我们要注意的一个点：InnoDB和MyIsam在存储的区别。

InnoDB
主键索引的存储结构是：叶子节点存储了主键值和其他字段数据值
其他索引的存储结构是：叶子节点存储了索引值和主键索引值

区别是其他索引存的是主键索引值

MyIsam
索引的存储结构是：叶子节点存储了主键值和数据记录的地址

主键索引和其他索引存储结构是一样的

说B+树之前先说说B树，B+树是在B树基础上优化来的。

B树索引格式

B树的缺点：会因为树的深度过深而造成IO次数变多，从而影响查询效率。

再来看看B+树索引格式

B+树跟B树区别：B+树数据只存在叶子节点，这样每个节点存储的数据会变多，从而存储大量数据时树的深度会比B树少很多很多，基本三层B+树就能存储千万级别的数据。所以MySQL才会选择B+树，减少磁盘IO，提高读取效率。不选二叉树或红黑树都是同样的道理。

那为什么不选哈希表呢？

• 哈希索引没办法利用索引完成排序。
• 不能进行多字段查询。
• 在有大量重复键值的情况下，哈希索引的效率也是极低的（出现哈希碰撞问题）。
• 不支持范围查询。

回表是什么
二级索引存储的是主键ID，所以通过二级所以查询的过程是：先去查主键ID，再通过主键ID去查询数据，这个过程称为回表。

二、索引相关

聚簇索引：InnoDB的主键索引是聚簇索引。一个表中只能拥有一个聚集索引。

非聚簇索引：InnoDB的普通索引是非聚簇索引。MyIsam的索引就是非聚簇索引。

覆盖索引：select的数据列只用从索引中就能够取得，不必从数据表中读取，即查询列要被所使用的索引覆盖。

不建议使用select * 查询也是有这个部分这个原因。
还有优化 limit 90000,10这种SQL语句核心也是使用覆盖索引提高效率。

索引下推：只能用于二级索引。

mysql>select * from user where name like '张%' and age > 10 假设创建了联合索引（name,age） 

这条SQL语句会怎么执行呢？

a. 根据（name,age）联合索引查询所有满足名称以“张”开头的索引，然后回表查询出相应的全行数据，然后再筛选出满足年龄小于等于10的用户数据
b. 根据（name,age）联合索引查询所有满足名称以“张”开头的索引，然后直接再筛选出年龄小于等于10的索引，之后再回表查询全行数据

很明显，b的查询方式回表查询的全行数据比较少，这个过程就是索引下推。

MySQL默认启用索引下推

最左原则
大家可能都知道的是一个联合索引（a, b , c），如果查询条件是

1. where a = x
2. where a = x and b = x
3. where b = x and c = x and a = x

这样是能用到索引的。但是下面2种情况就不能完全使用索引：

1. where a = x and c = x
   索引覆盖a， c列不能走索引
2. where a = x and b > x and c = x
   索引覆盖a和b，因b列是范围查询，因此c列不能走索引

IN 在 where 中，也属于准确查询，不会使后面索引失效。
遇到范围查询（>、<、between、like ）就会停止匹配。

联合索引怎么存储：把主键ID(3)的值替换成功联合索引的值(“张三”,30)，叶子节点存放主键ID值。

总结

MySQL的索引还是比较简单的，很多都是概念性问题比较简单。掌握了B+树的索引格式基本其他问题都迎刃而解了。

最后给大家推荐一个学习数据结构的好网站：数据结构