mysql b 树 叶子_常见问题:MySQL/B+树-程序员宅基地

技术标签: mysql b 树 叶子  

平衡二叉树

此前讲红黑树时也提到了平衡二叉树,红黑树和AVL树都是能保证树不退化的平衡二叉树,平衡二叉树采用二分思想组织数据,能大大提高单点查找数据的效率,其组装过程略。

作为对比,此处也列出平衡二叉树规则

节点最多有两个子节点。

节点大于其左子节点小于其右子节点。

树的左右两边层级最多相差不大于1。

但平衡二叉树的性能和层级成反比,如果层级过多,则影响效率。因此数据库使用平衡二叉树组织数据过于低效,产生了B树。

B树

结构

B树即多路平衡查找树,也叫多叉树,其规则如下:

递增排序,左小右大。

一个节点的子节点数在(1,m]且m>=2。

一个节点的关键字数量为[(m-1)/2,m)。

所有叶子节点在同层。

7d55a0fd6f25becdb1ccf96489f3a0ec.png

查询

由于B树采用左小右大的原则,可以快速定位数据所在的区间,能够快速定位到单点。

插入

根据区间正常插入到叶子节点。

所在节点元素数超过m-1时,拆分,中间元素提到父节点,左边元素构成一个叶子节点,右边元素构成一个叶子节点。若引起父节点溢出,则递归拆分。

删除

根据区间正常定位到关键字,删除。

所在节点元素数小于(m-1)/2,从子节点取点补缺,若子节点没有可取点,则从父节点取点补缺,若引起父节点元素数不足,递归此问题。

除了有效减少数据的层数时,B树可以把块大小设置为4k,这样和磁盘块大小相同,可以快速将一个节点的数据全部取出,提高了性能。

B+树

相对于B树,B+树将所有元素都存储到叶子节点,非叶子节点保存的是叶子节点首条数据的引用,用于检索,因此B+树的叶子节点数=关键字数。此外,B+树的每个叶子节点,都包含着指向相邻叶子节点的指针。

B+树的插入和B树几乎一致,只是拆分时不会将元素提到叶子节点,而是将元素的引用提到叶子节点(左节点包含m/2个元素),并递归拆分。

删除时,若删除后节点元素不足,优先从兄弟节点借一个元素,并更新父节点的引用。若兄弟节点不能借出节点,则将两节点合并为同一节点,并更新父节点引用。引起父节点元素不足时,递归操作,当根节点只有一个子节点时则进行降级,引用下移并删除节点。

B+树有以下好处:

B+树非叶子节点仅存储引用,相对很小,一次性读入内存的关键字多(类似KV分离的好处)。

B+树所有元素都在叶子节点,查询效率稳定。

叶子节点指向相邻兄弟节点,可以快速scan。

B*树

B树在B+树基础上,将非叶子节点也加上指向兄弟节点的指针,并定义非叶子节点关键字个数至少为(2/3)m,进而获取了更高的空间利用率。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_36048031/article/details/113423805

智能推荐

Aubo机械臂初学(愁)——1、gazebo和Rviz联合仿真_aubo机械臂仿真-程序员宅基地

文章浏览阅读1.7k次,点赞5次,收藏33次。auboi5机械臂初学者遇到的各种问题合集_aubo机械臂仿真

POJ_1064_Cable master【二分】_poj - 1064 二分枚举答案 floor向下取整函数 原创-程序员宅基地

文章浏览阅读1.7k次。/*Cable masterTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 43878 Accepted: 9409DescriptionInhabitants of the Wonderland have decided to hold a regional programmi_poj - 1064 二分枚举答案 floor向下取整函数 原创

【前端学习】HTML学习笔记-table_table前端心得-程序员宅基地

文章浏览阅读88次。<table><colgroup><col bgcolor='red' width=200></colgroup><thead><tr><th></th></tr><tbody><tr><td></td></t..._table前端心得

CSS 之 line-height 实现单行文字垂直居中的原理_css height=line-height 可以垂直居中-程序员宅基地

文章浏览阅读1.5k次,点赞3次,收藏12次。基础知识line-height 与 font-size 的计算值之差(在 CSS 中成为“行间距”)分为两半,分别加到一个文本行内容的顶部和底部。我们暂且称之为顶部距离和底部距离,就是上图中的蓝色区域。也就是说: line-height = 顶部距离 + 内容高度(顶线和底线之间的距离) + 底部距离;顶部距离 = 底部距离;示例一: 当line-height 等于 height 时,文字垂直居中文本默认大小16px。结果:文字垂直居中。顶部距离 = 底部距离 = (line-heig_css height=line-height 可以垂直居中

uniapp实战——实现详情其他部分的结构_uniapp 实现关系图谱-程序员宅基地

文章浏览阅读241次。QQ 1274510382Wechat JNZ_aming商业联盟 QQ群538250800技术搞事 QQ群599020441解决方案 QQ群152889761加入我们 QQ群649347320共享学习 QQ群674240731纪年科技aming网络安全 ,深度学习,嵌入式,机器强化,生物智能,生命科学。叮叮叮:产品已上线 —>关注 官方认证-微信公众号——济南纪年信息科技有限公司民生项目:商城加盟/娱乐交友/创业商圈/外包兼职开发-项目发布/安全项目:态.._uniapp 实现关系图谱

如何查看其他人的ABAP authorization check log_查看authorization-程序员宅基地

文章浏览阅读375次。Created by Jerry Wang on Jul 29, 2014 Go to start of metadata在做middleware相关的scenario操作时,有时候需要evaluate其他user的authorization check log,例如在CRM tcode SMW01里发现BDoc state为validation error,点击show error butto..._查看authorization

随便推点

I.MX6 eMMC分区挂载-程序员宅基地

文章浏览阅读244次。/********************************************************************* * I.MX6 eMMC分区挂载 * 说明: * 如果想要修改分区的挂载情况,可以修改fstab.freescale文件。 * * ..._imx6 分区挂载

【opencv-python】霍夫圆检测_霍夫圆圆心检测python-程序员宅基地

文章浏览阅读6.7k次,点赞10次,收藏55次。霍夫变换检测直线的原理是利用累加器找到最大的(ρ,θ)(ρ,θ)(ρ,θ)数对,如文章所述。圆形的数学表达式为(x−xcenter)2+(y−ycenter)2=r2(x-x_{center})^2+(y-y_{center})^2=r^2(x−xcenter​)2+(y−ycenter​)2=r2,其中(xcenter,ycenter)(x_{center},y_{center})(xcenter​,ycenter​)为圆心坐标,rrr为圆的直径。因此可知一个圆需要xcenter,ycenter,rx_{_霍夫圆圆心检测python

码仔精选,Android面试题-程序员宅基地

文章浏览阅读171次。码个蛋(codeegg) 第 822次推文码妞看世界1.Java创建对象的几种方式使用new关键字使用Class类的newInstance方法使用Constructor类的newIn..._码个蛋 《每日一道面试题》 第一期

Milking Time (poj 3616 简单DP)_poj milking time-程序员宅基地

文章浏览阅读2.5k次,点赞3次,收藏5次。题意:给个时间长度n,m个工作时间段和每个时间段能完成的工作量,一次只能做一个工作并且一旦开始做就要把它做完,要求选择的两个工作时间段之间至少相差r时间(中间需要休息嘛)求选择那些工作n时间内能完成的最大工作量。输出最大值。思路:先按工作的结束时间从小到大排序,再动态规划。dp[i]表示从头开始取到第i段所获得的最大值。二重循环,如果第i段之前的某个段的结束时间加上r小于等于第i段的开始时间,则更新dp[i]。_poj milking time

GDCM:gdcm::Global的测试程序_gbcm main show main screen-程序员宅基地

文章浏览阅读333次。GDCM:gdcm::Global的测试程序GDCM:gdcm::Global的测试程序GDCM:gdcm::Global的测试程序#include "gdcmGlobal.h"#include "gdcmDicts.h"#include "gdcmDict.h"#include "gdcmDefs.h"int TestGlobal(int, char *[]){ // case 1 // Get the global singleton: gdcm::Trace::DebugOn_gbcm main show main screen

理解 OAuth 2.0_shanks user-agent-程序员宅基地

文章浏览阅读278次。转载自http://www.ruanyifeng.com/blog/2014/05/oauth_2_0.html作者:阮一峰日期:2014年5月12日OAuth是一个关于授权(authorization)的开放网络标准,在全世界得到广泛应用,目前的版本是2.0版。本文对OAuth 2.0的设计思路和运行流程,做一个简明通俗的解释,主要参考材料为RFC 6749。更新:我后来又写了一组三篇的《OAuth 2.0 教程》,更加通俗,并带有代码实例,欢迎阅读。一、应用场景..._shanks user-agent