文章详情

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

请输入下面的图形验证码

提交验证

短信预约提醒成功

InnoDB原理篇:为什么使用索引会变快?

2024-12-02 06:18

关注

本文就接上一篇文章【​​InnoDB原理篇:聊聊数据页变成索引这件事​​】来聊聊索引。

建议看完上篇文章再看本篇,食用效果最佳。

索引

假设给你一本非常厚的《Java编程思想》阅读,没有目录,你想快速找到某一个章节的知识点,那估计得找一会了,如果有目录就不一样。

索引其实就是为了提高数据查询的效率,就像书的目录一样,对于数据库的表而言,索引其实就是它的目录。

二叉搜索树

索引的实现种类繁多,比如常见的有序数组、哈希表、树等,不同的结构都有自己的适用场景和局限性,在数据库领域中,树结构是被广泛使用。

我们先从最基本的二叉搜索树说起。

二叉搜索树的特点是:父节点左子树所有结点的值小于父节点的值,右子树所有结点的值大于父节点的值,如下图所示:

如果要查id=4的数据,按照图中的搜索顺序是索引页A -> 索引页B -> 索引页D -> 数据页0,时间复杂度是O(log(N))。

也就是说,搜索速度与高度有关,树越高,性能越差,假设100万行的表,使用二叉树来存储,树高20,磁盘每次随机读一个数据块需要10ms左右,单独访问一个行可能需要20个10ms的时间,这个查询可真够慢的。

N叉搜索树

为了减少磁盘随机读IO,就必须控制好树的高度,那就不应该使用二叉树,而是使用N叉树,这里的N代表数据块的大小。

也就说,你一个索引页存储的数据越多,树会越矮,InnoDB中就使用了B+树来实现索引。

以InnoDB的整数字段建立索引为例。

一个页默认16kb,整数(bigint)字段的长度为8B,另外还跟着6B的指向其子树的指针,这意味着一个索引页可以存储接近1200条数据(16kb/14B ≈ 1170)。

如果这颗B+树高度为4,就可以存1200的3次方的值,差不多17亿条数据。

考虑到树根节点总是在内存中的,树的第二层很大概率也在内存中,所以一次搜索最多只需要访问2次磁盘IO。

可能小伙伴会有疑问,为什么树的根节点与树的第二层会在内存,第三层、第四层却没在?

道理很简单,看下数据大小就清楚了。

最后再感受下索引搜索的流程。

假设1亿数据量的表,根据主键id建立了B+树索引,现在搜索id=2699的数据,流程如下:


来源:程序猿阿星内容投诉

免责声明:

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

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

软考中级精品资料免费领

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

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

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

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

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

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

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