目录
概述
索引的底层数据结构
二叉树
B树
B+树
B树与B+树对比:
面试回答
大纲
回答
概述
索引(index)是帮助MySQL高效获取数据的数据结构(有序)。
在数据之外,数据库系统还维护着满足特定查找算法的数据结构(B+树),这些数据结构以某种方式引用(指向)数据, 这样就可以在这些数据结构上实现高级查找算法,这种数据结构就是索引。
如果要查找年龄为33的人,左图从上到下遍历,遍历到第一个33依然会向下遍历,效率低
而如果是二叉树,左小右大,就会方便很多,每一次都可以说是二分查询
索引的底层数据结构
MySQL索引使用的是B+树,在这里我们要与二叉树,红黑树,B树做对比
二叉树
二叉搜索树在极端情况下,会退化为链表
红黑树是平衡的,比较稳定,但是因为红黑树也是二叉树,一个节点只有两个儿子,在大数据量的情况下,红黑树会变得特别特别高
B树
B-Tree,B树是一种多叉路衡查找树,相对于二叉树,B树每个节点可以有多个分支,即多叉。
以一颗最大度数(max-degree)为5(5阶)的b-tree为例,那这个B树每个节点最多存储4个key
树的高度肉眼可见比二叉树低得多
B+树
B+Tree是在BTree基础上的一种优化,使其更适合实现外存储索引结构,InnoDB存储引擎就是用B+Tree实现其索引结构
其中,非叶子节点,只存储指针,不存储数据,数据则统一在叶子节点存储
B树与B+树对比:
①:磁盘读写代价B+树更低;
②:查询效率B+树更加稳定;
③:B+树便于扫库和区间查询
面试回答
大纲
了解过索引吗?(什么是索引)?
索引(index)是帮助MySQL高效获取数据的数据结构(有序)
提高数据检索的效率,降低数据库的IO成本(不需要全表扫描)
通过索引列对数据进行排序,降低数据排序的成本,降低了CPU的消耗
索引的底层数据结构了解过嘛 ?
MySQL的InnoDB引擎采用的B+树的数据结构来存储索引
阶数更多,路径更短
磁盘读写代价B+树更低,非叶子节点只存储指针,叶子阶段存储数据
B+树便于扫库和区间查询,叶子节点是一个双向链表
回答
面试官:了解过索引吗?(什么是索引)
候选人:嗯,索引在项目中还是比较常见的,它是帮助MySQL高效获取数据 的数据结构,主要是用来提高数据检索的效率,降低数据库的IO成本,同时 通过索引列对数据进行排序,降低数据排序的成本,也能降低了CPU的消耗
面试官:索引的底层数据结构了解过嘛 ?
候选人:MySQL的默认的存储引擎InnoDB采用的B+树的数据结构来存储索 引,选择B+树的主要的原因是:第一阶数更多,路径更短,第二个磁盘读写 代价B+树更低,非叶子节点只存储指针,叶子阶段存储数据,第三是B+树便 于扫库和区间查询,叶子节点是一个双向链表
面试官:B树和B+树的区别是什么呢?文章来源:https://www.toymoban.com/news/detail-501238.html
候选人:第一:在B树中,非叶子节点和叶子节点都会存放数据,而B+树的 所有的数据都会出现在叶子节点,在查询的时候,B+树查找效率更加稳定 第二:在进行范围查询的时候,B+树效率更高,因为B+树都在叶子节点存 储,并且叶子节点是一个双向链表文章来源地址https://www.toymoban.com/news/detail-501238.html
到了这里,关于MySQL面试题--索引概念以及底层的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!