登录
首页 >  数据库 >  MySQL

MySQL B-tree与B+tree索引数据结构剖析

来源:脚本之家

时间:2022-12-29 16:36:10 244浏览 收藏

IT行业相对于一般传统行业,发展更新速度更快,一旦停止了学习,很快就会被行业所淘汰。所以我们需要踏踏实实的不断学习,精进自己的技术,尤其是初学者。今天golang学习网给大家整理了《MySQL B-tree与B+tree索引数据结构剖析》,聊聊索引、B+Tree、MySQLB-tree,我们一起来看看吧!

一、产生的背景

二叉查找树的查找时间复杂度是O(logN),整体的查询效率已经足够高了,那么为什么还会有B树和B+树的进化演进呢? 主要的原因是:二叉树可能会退化成一个线性树,造成磁盘IO次数增高的问题,当有大量的数据存储的时候,二叉查找树查询不能将所有的数据加载到内存中,只能逐一加载磁盘页,每个磁盘对应树的节点,造成大量的磁盘IO操作(最坏的情况IO次数为树的高度),平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁,进而导致效率低下。所以,为了减少磁的IO的次数,必须降低树的深度,将瘦高的树变得矮胖

1.1 进化要求

  • 每个结点能存储多个元素
  • 摒弃二叉树结构,采用多叉树

二、B-tree

B-Tree是一种多叉的平衡搜索树(并不一定是二叉的),以一个三阶B-tree为例子来分析,每个储存块都包含:关键字和指向孩子结点的指针,最多有M个孩子,M的大小主要取决于每个存储块的容量和数据库的配置M表示M阶数的意思。

image.png

2.1 B-tree特性

  • 根节点至少包括两个孩子,范围是[2,M];
  • 树中每个节点最多包含M阶数个孩子(M是阶数,3阶,即:每个节点最多包含3个孩子);
  • 除了根节点和叶子结点以外,其他每个节点至少有ceil(M/2)个孩子节点,ceil是取上限函数(M是阶数,3阶,即:每个节点至少有2个孩子);
  • 所有的叶子结点都位于同一层。

假设每个非叶子节点包含n个关键字信息,其中:

  • Ki(i=1,2..,n)为关键字,且关键字按顺序升序排序K(i-1);
  • 关键字的个数n必须满足:[ceil(m/2)-1](非叶子结点的关键字 = 指向孩子的指针个数-1);
  • 非叶子结点的指针:P[1],P[2],...,P[M];其中P[1]指向关键字小于K[1]的子树(即:3和5均小于8),P[M]指向关键字大于K[M-1]的子树(即:13和15均大于12),其他P[i]指向关键字属于(K[i-1],K[i])的子树,是开区间(即:9和10都处于8-12区间);

假设需要查询数据15,查询步骤:

  • 首先从根部开始找,15
  • 由于15比8和12都大,因此会找到P3;
  • P3指向了13和15,13
  • 查找的时间复杂度为O(logN)。

三、B+tree

image.png

3.1 B+tree特性

B+树是B树的变体,其定义基本上与B树相同,除了:

  • 非叶子结点的子树指针与关键字的个数相同;
  • 非叶子结点的子树指针P[i],指向关键字值 [K[i],K[i+1])的子树,左闭右开区间
  • 非叶子结点仅用于索引,数据都保存在叶子结点中;
  • 所有的叶子结点均有一个链指针指向下一个叶子结点;
  • B+树非叶子结点仅用来存放索引,能存储更多的关键字,使得B+树相对于B树来说更矮壮,能存储更多数据。
  • 所有的数据都存储在叶子结点。

四、结论

B+tree相比B-tree更适合用来存储索引,原因如下:

  • B+树的磁盘读写代价更低,B+树内部节点不存放数据,只存放索引信息,因此其内部节点相对B-tree会更小,所以同一个盘快就能存储更多的关键字,一次性读入内存中需要查找的关键字也就越多,因此IO次数也就越低。
  • B+树的查询效率更加稳定,由于B+树内部节点并不是指向文件内容的节点,而只是叶子节点关键字的索引,索引任何一个数据的查询都必须是:任何关键字查询都是从根节点到叶子节点的查询路线,因此每个数据的查询效率都是稳定一致的
  • B+树跟有利于对数据的扫描,B-tree在解决磁盘IO性能同时并没有解决元素遍历效率低下问题,而B+树只需要遍历叶子节点就可以实现对所有关键字的扫描,所有对数据库频繁的范围查询是有着更高的查询性能。

理论要掌握,实操不能落!以上关于《MySQL B-tree与B+tree索引数据结构剖析》的详细介绍,大家都掌握了吧!如果想要继续提升自己的能力,那么就来关注golang学习网公众号吧!

声明:本文转载于:脚本之家 如有侵犯,请联系study_golang@163.com删除
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>
评论列表