共计 3508 个字符，预计需要花费 9 分钟才能阅读完成。
越致力，越侥幸，
本文已珍藏在 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 一次 IO16K，而图上的磁盘块能显著达不到 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 技术博客》观看更多文章，也欢送关注一波。
