1 B树
在介绍B+树之前, 先简单的介绍一下B树,这两种数据结构既有相似之处,也有他们的区别,最后,我们也会对比一下这两种数据结构的区别。
1.1 B树概念
B树也称B-树,它是一颗多路平衡查找树。二叉树我想大家都不陌生,其实,B树和后面讲到的B+树也是从最简单的二叉树变换而来的,并没有什么神秘的地方,下面我们来看看B树的定义。
-
每个节点最多有m-1个关键字(可以存有的键值对)。
-
根节点最少可以只有1个关键字。
-
非根节点至少有m/2个关键字。
-
每个节点中的关键字都按照从小到大的顺序排列,每个关键字的左子树中的所有关键字都小于它,而右子树中的所有关键字都大于它。
-
所有叶子节点都位于同一层,或者说根节点到每个叶子节点的长度都相同。
-
每个节点都存有索引和数据,也就是对应的key和value。
所以,根节点的关键字数量范围:1 <= k <= m-1
,非根节点的关键字数量范围:m/2 <= k <= m-1
。
另外,我们需要注意一个概念,描述一颗B树时需要指定它的阶数,阶数表示了一个节点最多有多少个孩子节点,一般用字母m表示阶数。
我们再举个例子来说明一下上面的概念,比如这里有一个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了,所以需要进行分裂,分裂的规则在上面已经讲了,分裂之后,如下。
- 接着插入23,25,39
分裂,得到下面的。
更过的插入的过程就不多介绍了,相信有这个例子你已经知道怎么进行插入操作了。
1.3 B树的删除操作
B树的删除操作相对于插入操作是相对复杂一些的,但是,你知道记住几种情况,一样可以很轻松的掌握的。
- 现在有一个初始状态是下面这样的B树,然后进行删除操作。
- 删除15,这种情况是删除叶子节点的元素,如果删除之后,节点数还是大于
m/2
,这种情况只要直接删除即可。
- 接着,我们把22删除,这种情况的规则:22是非叶子节点,对于非叶子节点的删除,我们需要用后继key(元素)覆盖要删除的key,然后在后继key所在的子支中删除该后继key。对于删除22,需要将后继元素24移到被删除的22所在的节点。
此时发现26所在的节点只有一个元素,小于2个(m/2),这个节点不符合要求,这时候的规则(向兄弟节点借元素):如果删除叶子节点,如果删除元素后元素个数少于(m/2),并且它的兄弟节点的元素大于(m/2),也就是说兄弟节点的元素比最少值m/2还多,将先将父节点的元素移到该节点,然后将兄弟节点的元素再移动到父节点。这样就满足要求了。
我们看看操作过程就更加明白了。
- 接着删除28,删除叶子节点,删除后不满足要求,所以,我们需要考虑向兄弟节点借元素,但是,兄弟节点也没有多的节点(2个),借不了,怎么办呢?如果遇到这种情况,首先,还是将先将父节点的元素移到该节点,然后,将当前节点及它的兄弟节点中的key合并,形成一个新的节点。
移动之后,跟兄弟节点合并。
删除就只有上面的几种情况,根据不同的情况进行删除即可。
上面的这些介绍,相信对于B树已经有一定的了解了,接下来的一部分,我们接着讲解B+树,我相信加上B+树的对比,就更加清晰明了了。
2 B+树
2.1 B+树概述
B+树其实和B树是非常相似的,我们首先看看相同点。
- 根节点至少一个元素
- 非根节点元素范围:m/2 <= k <= m-1
不同点。
- B+树有两种类型的节点:内部结点(也称索引结点)和叶子结点。内部节点就是非叶子节点,内部节点不存储数据,只存储索引,数据都存储在叶子节点。
- 内部结点中的key都按照从小到大的顺序排列,对于内部结点中的一个key,左树中的所有key都小于它,右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
- 每个叶子结点都存有相邻叶子结点的指针,叶子结点本身依关键字的大小自小而大顺序链接。
- 父节点存有右孩子的第一个元素的索引。
下面我们看一个B+树的例子,感受感受它吧!
2.2 插入操作
对于插入操作很简单,只需要记住一个技巧即可:当节点元素数量大于m-1的时候,按中间元素分裂成左右两部分,中间元素分裂到父节点当做索引存储,但是,本身中间元素还是分裂右边这一部分的。
下面以一颗5阶B+树的插入过程为例,5阶B+树的节点最少2个元素,最多4个元素。
- 插入5,10,15,20
- 插入25,此时元素数量大于4个了,分裂
- 接着插入26,30,继续分裂
有了这几个例子,相信插入操作没什么问题了,下面接着看看删除操作。
2.3 删除操作
对于删除操作是比B树简单一些的,因为叶子节点有指针的存在,向兄弟节点借元素时,不需要通过父节点了,而是可以直接通过兄弟节移动即可(前提是兄弟节点的元素大于m/2),然后更新父节点的索引;如果兄弟节点的元素不大于m/2(兄弟节点也没有多余的元素),则将当前节点和兄弟节点合并,并且删除父节点中的key,下面我们看看具体的实例。
- 初始状态
- 删除10,删除后,不满足要求,发现左边兄弟节点有多余的元素,所以去借元素,最后,修改父节点索引
- 删除元素5,发现不满足要求,并且发现左右兄弟节点都没有多余的元素,所以,可以选择和兄弟节点合并,最后修改父节点索引
- 发现父节点索引也不满足条件,所以,需要做跟上面一步一样的操作
这样,B+树的删除操作也就完成了,是不是看完之后,觉得非常简单!
3 B树和B+树总结
B+树相对于B树有一些自己的优势,可以归结为下面几点。
- 单一节点存储的元素更多,使得查询的IO次数更少,所以也就使得它更适合做为数据库MySQL的底层数据结构了。
- 所有的查询都要查找到叶子节点,查询性能是稳定的,而B树,每个节点都可以查找到数据,所以不稳定。
- 所有的叶子节点形成了一个有序链表,更加便于查找。
相关推荐
2. 【漫画】以后在有面试官问你AVL树,你就把这篇文章扔给他。 3. 记一道字节跳动的算法面试题 4. 关于三次握手与四次挥手面试官想考我们什么?--- 不看后悔系列 5. 腾讯面试题:有了二叉查找树、平衡树为啥还...
面试官问作者需要换一位面试官还是想在他这试一试,作者当然选择了换一个 windows 的面试官。 在第一次面试中,面试官问作者“你自己感觉你算法强一点还是 Coder 强”,作者回答说编码。然后,面试官让作者写了一个...
本篇文章将分享三个实用的面试技巧,帮助你在面试中脱颖而出,甚至“秒杀”面试官。 首先,了解并背诵一些与面试公司或行业相关的数字。这不仅能展示你对职位的认真态度,还能体现你的细心和专业。例如,如果是市场...
高清完整版112道运营面试问题...本篇干货文章的所有面试脑图和所有内容,全部来源于我亲自制作的《运营斩获 offer 宝典》, 基于我 11 年大厂面试官和 8 年运营经验,从面试官的角度去整理,耗时 200 天时间才完成 的。
在面试环节,面试官往往会针对你做过的具体项目,问非常细致的问题。 3. 介绍自己做过的项目时,最好挑应聘职位相关的项目,因为对于技术主管来说,他关心的是你做过的项目跟他们有没有相关性,以及你的专业特长跟...
面试官:数据库有几千万的数据,查询又很慢我们怎么办? 面试者:加索引。 面试官:那索引有哪些数据类型?索引是怎么样的一种结构?哪些字段又适合索引呢?B+的优点?聚合索引和非聚合索引的区别?为什么说索引会...
在面试中,面试官可能会询问你如何处理项目中的重大挑战。这需要你详细阐述项目背景、遇到的问题以及解决方法。例如,你可能需要解释如何通过优化算法、重构代码或引入新的技术来提升系统的性能和稳定性。 2. **...
2. **索引**:理解B树和B+树,了解索引的类型(唯一,非唯一,全文索引),如何创建和优化索引,以及索引对查询性能的影响。 3. **事务处理**:ACID属性(原子性,一致性,隔离性,持久性),事务的四种隔离级别,...
总结:这篇文章是作者 Eric 对如何成功进入投行行业,特别是Sales & Trading、Research和Assets Management职位的面试攻略。他强调了学校背景、人脉关系、简历质量和面试技巧的重要性,并提供了实用的建议。对于想要...
本篇文章将针对“数据库面试和笔试常见题”进行深入解析,帮助大家在求职过程中更好地准备。 一、数据库基础概念 1. 数据库(Database):是一种有组织地存储数据的系统,能够提供数据的创建、查询、更新和删除等...
在C#面试中,面试官可能会考察一系列关于语言特性和编程技巧的问题。以下是对给定的C#面试题目的详细解答: 1. **斐波那契数列**:题目要求使用递归算法计算斐波那契数列的第30位数。递归函数`Foo`通过检查输入的...
在这篇文章中,我们将总结了 Java 面试中的 200 多个问题,涵盖了 Java 基础、容器、多线程、反射、对象拷贝、Java Web 、异常、网络、设计模式、Spring/Spring MVC、Spring Boot/Spring Cloud、Hibernate、MyBatis...
此外,面试官可能会询问关于触发器、视图、游标和存储过程的应用场景,以及如何处理大数据量的表和确保数据的一致性。 接着,我们转向多线程,这是Java编程中的重要概念,尤其是在高并发系统中。面试题可能涵盖线程...
本篇文章将深入探讨一些经典Python面试题中的基础知识。 1. 为什么学习Python? Python因其易读性强、代码量小、丰富的库支持以及跨平台特性而受到青睐。它在Web开发、数据分析、人工智能、自动化脚本等多个领域都...
b某提到的英语口语能力和发表的文章就是实例证明。 5. **个性展示**:除了专业能力,个人特质也是面试官关注的部分。比如,a某提到的性格活泼和做事认真,这些都能反映出一个人的工作态度和团队适应性。 6. **询问...
<canvas> 比如来自一个外部的新闻提供者的一篇新的文章... 解释:标签用于绘制图形,而不是展示文本内容。 8) CSS属性position的属性值错误描述 答案:b. fixed:生成绝对定位的元素,相对于父元素进行定位 解释:...
面试中,面试官可能会考察候选人的HTML和CSS基础知识,包括语法规则、布局技巧以及最新的HTML5特性等。 1. `input`元素是HTML窗体(form)元素之一,它的层级(z-index)通常高于Flash和其他非固定定位元素。这个...
在Python的面试过程中,面试官通常会关注求职者的基础知识、编程能力、问题解决技巧以及对Python生态的理解。本篇文章将深入探讨一些常见的Python面试题,并提供相应的代码实现,帮助你更好地准备面试。 1. **...
front-end-interview(持续更新中...) 介绍 ...问:a、b、c三个请求,希望c在a、b获取数据后再发请求,要是你你会怎么做? 答:axios.all 先请求 a、b,再在 then 的第一个回调中请求 c ,巴拉巴拉...