数据库索引在平时的工作是必备的，怎么建索引，怎么使用索引，可以提高数据的查询效率。而且在面试过程，数据库的索引也是必问的知识点，比如：

• 索引底层结构选型，那为什么选择B+树？
• 不同存储引擎的索引的体现形式有哪些？
• 索引的类型
  • 组合索引存储方式
  • 查询方式
  • 最左前缀匹配原则
• 覆盖索引是什么？

看着这些，能说出多少，理解多少呢？因此我们需要去探究其内在原理。

那索引是什么？

索引的目的为了加速检索数据而设计的一种分散存储（索引常常很大，属于硬盘级的东西，所以是分散存储）的数据结构,其原理以空间换时间。

而快速检索的实现的本质是数据结构，通过不同数据结构的选择，实现各种数据快速检索，索引有哈希索引和B+树索引。

索引底层结构选型，那为什么选择B+树？

数据库索引底层选型归根到底就是为提高检索效率，那么就需要考虑几个问题：

• 算法时间复杂度
• 是否存在排序
• 磁盘IO与预读

NOTE： 考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。

哈希表( Hash Table,散列表 )

哈希表是根据键（Key）而直接访问在内存存储位置的数据结构。

通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。虽然查询时间复杂度为O(1)，但存在着碰撞问题，最坏情况会导致时间复杂急剧增加;

而且哈希表其只适合精准key（等于）检索，不适合范围式检索，范围检索就需要一次把所有数据找出来加载到内存，没有效率，因此不适合Mysql的底层索引的数据结构。

普通的二叉查找树

为了优化高效范围查询，且时间复杂度小，引入二叉查找树

二叉查找树的时间复杂度是 O(lgn)，由于数据已排序好了，所以范围查询是可以高效查询，

但会存在的问题：左右子节点的深度可能相差很大，最极端的情况只有左子树或者右子树，此时查找的效率为O(n)，检索性能急剧下降，因此也不适合Mysql的底层索引的数据结构。

平衡二叉树（AVL树）

为了优化二叉树左右子树深度相差太大的问题，我们引入了平衡二叉树，即左右子节点的深度差不超过1 平衡二叉树看来好像适合，可以实现：

• 可以实现范围查找、数据排序
• 查询性能良好O(logn)

NOTE: 上图中一个磁盘块，代表硬盘上的一个存储位置

但是我们还有一个最重要因素需要考虑，磁盘IO与预读，且数据库查询数据的瓶颈在于磁盘 IO,使用平衡二叉树根据索引进行查找时，每读一个磁盘块就进行一次IO，这样没有实现计算机的预读，导致检索效率，总结出平衡二叉树作为索引的问题（上图中一个磁盘块，代表硬盘上的一个存储位置）：

• 太深了（即它只有二条路），深度越大进行的IO操作也就越多
• 太小了，每一次IO才查询磁盘块这么一点数据，太浪费IO了。操作系统规定一次IO最小4K，Mysql一次IO 16K，而图上的磁盘块能明显达不到4K

B+树

为了优化磁盘IO和预读，减少IO操作，条路太少了，那么换成多条路，那么会想到使用B树和B+树，但B树每个节点限制最多存储两个 key，也会造成IO操作过于频繁，因此优化思路为：尽可能在一次磁盘 IO 中多读一点数据到内存，那么B+树也该出场：

• B+树一个节点能存很多索引，且只有B+树叶子节点存储数据

• 相邻节点之间有一些前驱后继关系

• 叶子节点是顺序排列的

相对于B树，B+树的优势有：

• B+树扫库扫表的能力更强

  • B树的数据是存放在每一个节点中的，节点所在的物理地址又是随机的，所以扫表的话，进行的是随机IO
  • B+树的数据是存放在叶子节点的，且在一个叶子节点中的数据是连续的，所以扫表的话，进行的相对的顺序IO

• B+树的磁盘读写能力更强，枝节点不保存数据，而保存更多的关键字。一次IO就能读出更多的关键字

• B+树的排序能力更强，B+树的叶子节点存储的数据是已经排好序的

索引的体现形式

索引在不同的存储引擎中体现形式步一样， 最常见的是：

• Innodb 引擎中体现为聚集索引方式 （索引和数据是存放在同一个文件的）
• Myisam引擎中体现为非聚集索引方式 （索引和数据是存放在两个文件中的）

聚集索引方式（InnoDB存储引擎）

InnoDB存储引擎中，索引和数据是存放在同一个文件的，属于聚集索引 。而且InnoDB会自动建立好主键 ID 索引树, 因此建表时要求必须指定主键的原因。

其中，主键索引（聚集索引）的叶子节点记录了数据，而不是数据的物理地址。辅助索引的叶子节点存放的是主键key。所以当利用辅助索引查找数据时，实际上查了两遍索引（辅助索引和主键索引）:

• 先查询辅助索引树找出主键
• 然后在主键索引树中根据主键查询数据

非聚集索引方式（Myisam存储引擎）

Myisam存储引擎中，索引和数据是存放在两个文件中的，属于非聚集索引 。不管是主键索引还是辅助索引，其叶子节点都是记录了数据的物理地址。

MySQL的索引类型

MySQL索引可以分为：

• 普通索引(index): 加速查找

• 唯一索引：

  • 主键索引：primary key ：加速查找+约束（不为空且唯一）
  • 唯一索引：unique：加速查找+约束 （唯一）

• 联合索引：

  • primary key(id,name):联合主键索引
  • unique(id,name):联合唯一索引
  • index(id,name):联合普通索引

• 全文索引full text :用于搜索很长一篇文章的时候，效果最好。

其中，主要理解一下联合索引的问题，存储结构，查询方式。

联合索引

联合索引，多个列组成的索引叫做联合索引，单列索引是特殊的联合索引。其存储结构如下：

对于联合索引来说其存储结构只不过比单值索引多了几列，组合索引列数据都记录在索引树上，（不同的组合索引，B+树也是不同的），且存储引擎会首先根据第一个索引列排序后，其他列再依次将相等值的进行排序。

**NOTE:**叶节点第一排，按顺序排序好，第二列，会基于第一列排序好的，将第一列相等的再下一列再排序，依次类推。

联合索引查询方式，存储引擎首先从根节点（一般常驻内存）开始查找，然后再依次在其他列中查询，直到找到该索引下的data元素即ID值，再从主键索引树上找到最终数据。

而且联合索引其选择的原则：

• 最左前缀匹配原则（经常使用的列优先）
• 离散度高的列优先
• 宽度小的列优先

最左前缀匹配原则

最左前缀匹配原则和联合索引的索引构建方式及存储结构是有关系的。根据上述理解分析，可以得出联合索引只能从多列索引的第一列开始查找索引才会生效，比如:

假设表user上有个联合索引(a,b,c)，那么 select * from user where b = 1 and c = 2将不会命中索引

原因是联合索引的是存储引擎先按第一个字段排序，再按第二个字段排序，依次排序。

离散度

当索引中的一列离散度过低时，优化器可能直接不走索引，离散度计算方法：

离散度 = 列中不重复的数据量 / 这一列的总数据量

?

覆盖索引

如果一个索引包含(或覆盖)所有需要查询的字段的值，称为覆盖索，即只需扫描索引而无须回表查询 。覆盖索引可减少数据库IO，将随机IO变为顺序IO，可提高查询性能。

对于InnoDB辅助索引在叶子节点中保存了行的主键值，所以如果辅助索引(包括联合索引)能够覆盖查询，则可以避免对主键索引的二次查询。比如：

--创建联合索引
create index name_phone_idx on user(name,phoneNum);
--此时是覆盖索引，原因是根据name来查，命中索引name_phone_idx，
--其关键字为name,phoneNum，本身就已经包含了查询的列。
select name,phoneNum where name = "张三";  
--如果id为主键的话，此时也称作覆盖索引，原因：辅助索引的叶子节点存的就是主键
select id,name,phoneNum where name = "张三"; 
复制代码

总结

MySQL的索引有很多知识点要掌握，已学习了索引的底层存储结构，不同存储引擎中的索引体现，以及索引类型的基础原理知识分析，可以为后续的数据库优化提供理论知识的支撑，也会更好的理解优化方案。后续会有优化篇章