文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

MySQL查询性能优化前,必须先掌握MySQL索引理论

2024-12-03 16:37

关注

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

不同存储引擎的索引的体现形式有哪些?

索引的类型

覆盖索引是什么?

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

那索引是什么?

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

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

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

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

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

哈希表( Hash Table,散列表 )

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

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

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

普通的二叉查找树

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

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

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

 

平衡二叉树(AVL树)

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

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

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

B+树

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

相对于B树,B+树的优势有:

索引的体现形式

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

聚集索引方式(InnoDB存储引擎)

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

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

非聚集索引方式(Myisam存储引擎)

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

MySQL的索引类型

MySQL索引可以分为:

唯一索引:

联合索引:

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

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

联合索引

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

 

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

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

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

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

最左前缀匹配原则

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

离散度

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

覆盖索引

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

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

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

总结

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

来源:Ccww技术博客内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯