写点什么

深入理解 MySQL 索引

  • 2021 年 11 月 12 日
  • 本文字数:1032 字

    阅读完需:约 3 分钟

那索引为啥要用 B+Tree 的数据结构呢?


====================


如果我们简单地想的话,想要快速地查找到数据,感觉 hash 表是最快的,根据 key,hash 到某个槽位上,直接一次查找就可以准确的找到数据的位置,这多快呀。但是我们在做业务时,往往只需要一条的数据需求很少,大部分的需求都是根据一定的条件查询一部分的数据,这个时候 hash 显示不是很合适。


我们再考虑树,比如二叉树,平衡二叉树,红黑树,B 树等,他们都是二


【一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


分查找,找数也快,但是不管是平衡二叉树还是优化后的红黑树,说到底他们都是二叉树,当节点多了的时候,它们的高度就会高呀,我找一个数据。根节点不是,那就找下一层,下一层还没有我就再去找下一层,这样造成的后果就是我找一个数据可能要找好几次,而每一次都是执行了一次磁盘的 io,而我们的索引的目的就是要减少磁盘 io 呀,这样设计可不行。那我们是不是把高度变矮就可以了呢?


所以我们再考虑下 B 树。首先简单介绍下 B 树的数据结构:


B 树的定义:


======


  • 每个节点最多有 m-1 个关键字(可以存有的键值对)。

  • 根节点最少可以只有 1 个关键字。

  • 非根节点至少有 m/2 关键字。

  • 每个节点中的关键字都按照从小到大的顺序排列,每个关键字的左子树中的所有关键字都小于它,而右子树中的所有关键字都大于它。

  • 所有叶子节点都位于同一层,或者说根节点到每个叶子节点的长度都相同。

  • 每个节点都存有索引和数据,也就是对应的 key 和 value。


所以,根节点的 关键字 数量范围: 1 <= k <= m-1 ,非根节点的 关键字 数量范围: m/2 <= k <= m-1 。


这里的 m 表示阶数,阶数表示了一个节点最多有多少个孩子节点,所以描述一颗 B 树时需要指定它的阶数。


我们再举个例子来说明一下上面的概念,比如这里有一个 5 阶的 B 树,根节点数量范围:1 <= k <= 4,非根节点数量范围:2 <= k <= 4。


下面,我们通过一个插入的例子,讲解一下 B 树的插入过程,接着,再讲解一下删除关键字的过程。


1.2 B 树插入


插入的时候,我们需要记住一个规则: 判断当前结点 key 的个数是否小于等于 m-1,如果满足,直接插入即可,如果不满足,将节点的中间的 key 将这个节点分为左右两部分,中间的节点放到父节点中即可。


例子:在 5 阶 B 树中,结点最多有 4 个 key,最少有 2 个 key(注意:下面的节点统一 用一个节点表示 key 和 value )。


  • 插入 18,70,50,40



  • 插入 22



插入 22 时,发现这个节点的关键字已经大于 4 了,所以需要进行分裂,分裂的规则在上面已经讲了,分裂之后,如下。

评论

发布
暂无评论
深入理解MySQL索引