乐趣区

关于mysql索引:MySQL查询性能优化前必须先掌握MySQL索引理论

越致力,越侥幸,
本文已珍藏在 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 技术博客》观看更多文章,也欢送关注一波。

退出移动版