MySql数据库索引原理

沙海
沙海
沙海
1017
文章
2
评论
2021年4月9日04:48:57
评论
1 1899字阅读6分19秒
摘要

速读摘要

速读摘要

从数据结构和算法理论方面讨论MySQL数据库索引的数学基础。数据库通过将页面加载到存储器中来检索存储器中的数据,最后检索数据。集合索引是从各表的主键制作B+树,在叶节点中存储有表整体的行记录数据,因此索引聚集的叶节点也成为数据页。在许多情况下,查询优化器倾向于采用集中索引,因为它可以在索引的叶节点处直接找到数据。用辅助索引检索数据时,InnoDB存储引擎创建循环辅助索引,用叶电平指针取得箭头键索引的键,用主键索引找到完整的行记录。

原文约 1400 | 图片 7 | 建议阅读 3 分钟 | 评价反馈

MySql数据库索引原理

青青 架构师学习路线

这篇文章希望数据库索引的原理对大家有帮助。

第一部分从数据结构和算法理论方面讨论MySQL数据库索引的数学基础。

第二部分结合MySQL数据库的InnoDB数据存储引擎中的索引的构建,实现了讨论集成索引、非聚合索引、覆盖索引等话题。

一、数据结构及算法理论

Innodb存储引擎实现索引数据结构的是B+树,下面介绍几个数据结构。一步一步地说明为什么应该使用B+树。

1.1 B+树索引

B+树索引的结构与二叉树很类似。键值快速找到数据。但是,B+树种的B不是二叉,它表示平衡。注意:只有索引行。数据库通过将页面加载到存储器中来检索存储器中的数据,最后检索数据。

介绍二分搜索法。按排序(递增或减少)的顺序记录,在搜索过程中通过跳转查找。例如,示出了5、10、19、21、31、37、42、48、50、52的10个数量。

可以以三次搜索速度找到48。逐次搜索需要8次。对于上述10个数,依次检索的平均检索次数是5.5次,二分检索法是2.9次,最坏的情况是按顺序检索的次数是10次,二分检索的次数是4次。两点搜索将innodb页面Directory的插槽按主关键字的顺序保存,对于每个具体记录的查询将页面Directory分成两部分进行检索。

MySql数据库索引原理

1.2 二叉查找树

数字表示各节点的键的值。在树里找。左子树的键值总是小于跟的键值,右子树的键值总是大于跟的键值。通过中序遍历得到键值:2、3、5、6、7、8。

查找树的平均查找次数为2.3次,但是查找树是可以任意构建。和这样调查顺序是一样的。因此,引用了取得二叉树平衡的想法,AVL树。

1.3 定义

符合查找树的定义,其次必须满足任何节点的左右两个子树的高度最大差为1。

二叉树的平衡非常快,但是为了维持二叉树的平衡,通常需要一次以上的左转和右转插入或更新后树木的平衡。

1.4 B+树特性

全部记录在叶节点中,按顺序保存,各叶节点(以页为单位)在逻辑上连续保存,是双向循环链表。

B+树插入必须确认插入后的叶节点中的记录还被排序,因此在插入时必须考虑以下三种情况。

数据库中的一个特征是B。因此,在数据库中,B+树的高度通常在2~3层,也就是说,正在寻找某个键行的记录。最多可以进行2~3次IO。普通盘每秒至少可以进行100次IO。

MySql数据库索引原理

二、索引摘要和非编译索引

集合索引和非集合索引的区别在于页节点是否保存整个行的记录。

2.1 聚集索引

InnoDB存储引擎表是索引组织表,表格数据按主关键字顺序保存。集合索引是从各表的主键制作B+树,在叶节点中存储有表整体的行记录数据,因此索引聚集的叶节点也成为数据页。此特性用于收集索引,索引表中的数据也被确定为索引的一部分。同时B+树的数据结构相同。每个数据页面通过双向链接链接链接。

实际数据只由一个B+树排列。因此,每个表格只有一个链接索引。在许多情况下,查询优化器倾向于采用集中索引,因为它可以在索引的叶节点处直接找到数据。此外,由于定义了数据的逻辑顺序,所以可以快速访问对象范围的查询。查询优化器可以很快地发现需要扫描某范围的数据。注意各页的记录也用双向链保持。

MySql数据库索引原理

2.2 非聚集索引

也叫辅助索引。数据行中没有全部数据。页面节点除了关键字之外,每个页面级别的索引都包含书签。InnoDB记忆引擎告诉我们索引对应的行数据在哪里。因为InnoDB存储引擎表是索引组织表,因此InnoDB存储引擎的辅助索引书签是该行的数据的集合索引键。图是索引和辅助索引的关系。

用辅助索引检索数据时,InnoDB存储引擎创建循环辅助索引,用叶电平指针取得箭头键索引的键,用主键索引找到完整的行记录。例如,要在三个高度的辅助索引树中查找数据,必须找到辅助索引的主关键字。期间是3次。如果索引树的高度为3,则会检索3次组合索引。要搜索有完整行数据的页面,6次逻辑Io必须访问最终数据页面。

MySql数据库索引原理

MySql数据库索引原理

MySql数据库索引原理

MySql数据库索引原理

想要获取学习实战、高并发、架构 、笔试面试资料

请关注架构师学习路线图

*声明:本文于网络整理,版权归原作者所有,如来源信息有误或侵犯权益,请联系我们删除或授权事宜

继续阅读
weinxin
资源分享QQ群
本站是一个IT技术分享社区, 会经常分享资源和教程; 分享的时代, 请别再沉默!
沙海
  • 版权声明:本站是Java秀团队的技术分享社区,我们会经常分享资源和教程。
  • 转载请注明:MySql数据库索引原理 - Java秀 ☜(ˆ▽ˆ)
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: