越致力，越侥幸，
本文已珍藏在GitHub中JavaCommunity, 外面有面试分享、源码剖析系列文章，欢送珍藏，点赞
https://github.com/Ccww-lx/JavaCommunity

数据库索引在平时的工作是必备的，怎么建索引，怎么应用索引，能够进步数据的查问效率。而且在面试过程，数据库的索引也是必问的知识点，比方：

  • 索引底层构造选型，那为什么抉择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 :用于搜寻很长一篇文章的时候，成果最好。

其中，次要了解一下联结索引的问题，存储构造，查问形式。

联结索引

联结索引，多个列组成的索引叫做联结索引，单列索引是非凡的联结索引。其存储构造如下：

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

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

<font color='red'>联结索引查问形式，存储引擎首先从根节点（个别常驻内存）开始查找，而后再顺次在其余列中查问，直到找到该索引下的data元素即ID值，再从主键索引树上找到最终数据。</font>

而且联结索引其抉择的准则：

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

最左前缀匹配准则和联结索引的索引构建形式及存储构造是有关系的。根据上述了解剖析，能够得出联结索引只能从多列索引的第一列开始查找索引才会失效，比方:

假如表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的索引有很多知识点要把握，已学习了索引的底层存储构造，不同存储引擎中的索引体现，以及索引类型的根底原理常识剖析，能够为后续的数据库优化提供理论知识的撑持，也会更好的了解优化计划。后续会有优化篇章

谢谢各位点赞，没点赞的点个赞反对反对
最初，微信搜《Ccww技术博客》观看更多文章，也欢送关注一波。