什么是Mysql索引

思考:了解过索引吗?(什么是索引)

索引(index)帮助MySQL高效获取数据的数据结构(有序)。

在数据之外,数据库系统还维护着满足特定查找算法的数据结构(B+树),这些数据结构以某种方式引用(指向)数据, 这样就可以在这些数据结构上实现高级查找算法,这种数据结构就是索引

思考:Mysql索引的底层数据结构了解过嘛?

MySQL默认使用的索引底层数据结构是B+树

再介绍B+树之前,我们先知道二叉树(主要是二叉搜索树和红黑树)和B树

1.二叉树

二叉树: 顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只有左子节点,有的节点只有右子节点。二叉树每个节点的左子树和右子树也分别满足二叉树的定义

图片[1]-什么是Mysql索引-不念博客

常见的二叉树有:

  • 满二叉树
  • 完全二叉树
  • 二叉搜索树
  • 红黑树

1.1. 二叉搜索树

二叉搜索树(Binary Search Tree,BST): 名二叉查找树,有序二叉树或者排序二叉树,是二叉树中比较常用的一种类型

二叉查找树要求,在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值

图片[2]-什么是Mysql索引-不念博客

在极端情况下,二叉树会形成一个单向链表,结构如下

图片[3]-什么是Mysql索引-不念博客

二叉搜索树,属于最坏的情况,已经退化成了链表,左右子树极度不平衡,此时查找的时间复杂度肯定是O(n)

1.2. 二叉树作为索引结构缺点

  • 1.如果数据是有序的,则会顺序插入,形成链表,查询效率就降低
  • 2.如果数据量比较大,层级就比较深,检索效率就慢

2. 红黑树

考虑到二叉树有这些缺点后,我们可能就会考虑使用二叉树进阶版红黑树,红黑树是一个自由平衡二叉树,解决了是顺序插入数据形成单向链表的缺点,最终形成的数据结构也是一颗平衡的二叉树

红黑树(Red Black Tree):也是一种自平衡的二叉搜索树(BST),之前叫做平衡二叉B树(Symmetric Binary B-Tree)

红黑树数据结构如下:

图片[4]-什么是Mysql索引-不念博客

2.1. 红黑树的特质

  • 性质1:节点要么是红色,要么是黑色
  • 性质2:根节点是黑色
  • 性质3:红黑树中红色节点的子节点都是黑色
  • 性质4叶子节点都是黑色
  • 性质5:从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

在添加或删除节点的时候,如果不符合这些性质会发生旋转,以达到所有的性质

红黑树:保证平衡

虽然解决单向列表缺点,但是还是存在缺点:

如果数据量比较大,层级就较深,检索效率就慢

3. B树(B-Tree)

B-Tree:B树是一种多叉路衡查找树,相对于二叉树,B树每个节点可以有多个分支,即多叉

B树(B-Tree)具有一下特点:

  • 1.多叉树结构:B-Tree是一种多叉树,每个内部节点可以有多个子节点,使得B-Tree能够有效地存储和管理大量数据。
  • 2.平衡性:B-Tree具有平衡性,这意味着从根节点到叶子节点的任何路径的长度几乎相等。这确保了在平均情况下,对树的操作(插入、删除、查找)具有稳定的性能,不会出现严重的性能退化
  • 3.按序存储:B-Tree内的节点和数据通常按照键的顺序存储,这有助于范围查询和排序操作的高效执行。
  • 4.分层结构:B-Tree具有分层结构,从根节点到叶子节点有多个级别。
  • 5.高度平衡B-Tree的高度通常是相对较低,这是因为它的平衡性和多叉性质。高度平衡有助于减少查找操作所需的磁盘访问。
图片[5]-什么是Mysql索引-不念博客

对数据库而言,所有的数据都将会保存到磁盘上,磁盘 I/O 的效率又比较低,特别是在随机磁盘 I/O 的情况下效率更低

B树(B-Tree),高度决定了磁盘 I/O 的次数,磁盘 I/O 次数越少,对于性能的提升就越大,这也是为什么采用 B 树作为索引存储结构的原因

4. B+树(B+Tree)

B+Tree是在BTree基础上的一种优化,使其更适合实现外存储索引结构,MySQL 的 InnoDB 存储引擎就是用B+Tree实现其索引结构

相比较于 B-Tree结构来说,B+Tree做了两个方面的优化,如图所示:

图片[6]-什么是Mysql索引-不念博客

可以看到两部分:

  • 1.蓝色框部分,索引部分,是非叶子结点,仅仅起到索引数据的作用,不存储数据
  • 2.绿色框部分,数据存储部分,是叶子结点叶子节点中要存储具体的数据
  • 3.MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上,增加一个指向相邻叶子节点的链表指针,就形成了带有顺序指针的B+Tree,提高区间访问的性能,利于排序

B树与B+树对比

  • 磁盘读写代价B+树更低
  • 查询效率B+树更加稳定
  • B+树便于扫库和区间查询

5. Mysql索引面试题

面试官:了解过索引吗?(什么是索引)

候选人:

索引在项目中还是比较常见的,帮助MySQL高效获取数据的数据结构,主要是用来提高数据检索的效率,降低数据库的IO成本,同时通过索引列对数据进行排序,降低数据排序的成本,也能降低了CPU的消耗

面试官:索引的底层数据结构了解过嘛 ?

候选人:

MySQL的默认的存储引擎InnoDB采用的B+树的数据结构来存储索引,选择B+树的主要的原因是:

第一:阶数更多,路径更短,搜索效率高

第二:磁盘读写代价B+树更低,非叶子节点只存储指针,叶子阶段存储数据,而B-Tree,无论是叶子节点还是非叶子节点,都会保存数据,这样导致一页中存储键值减少,指针跟着减少,相对于B+树同样保存大量数据,只能增加树的高度,导致性能降低

第三:B+树便于扫库和区间查询,叶子节点是一个双向链表

面试官:B树和B+树的区别是什么呢?

候选人

第一:在B树中,非叶子节点和叶子节点都会存放数据,而B+树的所有的数据都会出现在叶子节点,在查询的时候,B+树查找效率更加稳定

第二:在进行范围查询的时候,B+树效率更高,因为B+树都在叶子节点存储,并且叶子节点是一个双向链表

© 版权声明
THE END
喜欢就支持一下吧
点赞129赞赏 分享
评论 抢沙发
头像
欢迎光临不念博客,留下您的想法和建议,祝您有愉快的一天~
提交
头像

昵称

取消
昵称代码图片

    暂无评论内容