B+Tree详解-程序员宅基地

技术标签： Java B+Tree 数据结构 b树

二叉查找树：

二叉树具有以下性质：左子树的键值小于根的键值，右子树的键值大于根的键值。

但是当二叉查找树在极端情况下如果编程这样：

查询效率就低了

所谓查询效率：由树的深度决定，每深入一层，都需要进行寻址，而寻址的过程就是磁盘随机度，磁盘随机读的速度很慢。

平衡二叉树（AVL树）：

平衡二叉树（AVL树）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1，就达到了所谓的平衡。需要通过一系列复杂的旋转达到平衡。

B-Tree（平衡多叉查找树）：

B-Tree是为磁盘等外存储设备设计的一种平衡查找树。

上图中的每走一次箭头，都意味着一次磁盘随机IO，意味着磁臂去寻址，很慢。

每一个节点，意味着一个页空间，一个页空间默认大小为16KB，可设置。

B-Tree就是为了磁盘等外设存储设备的机理设计的一种平衡查找树，利用了磁盘块空间，把磁盘块空间充分利用，多存储几个键值、指针，通过这样的方式，可以减少树的深度，也就意味着减少磁盘的随机IO次数，加快访问速度。

B+Tree：

在B-Tree的基础上优化了：

1、节点上只存储键值，不存储数据，这样一来，在有限的节点空间（页空间）内就可以存放更多的键值、指针；

2、所有数据都放在叶子节点中，所有叶子节点之间有链指针（双向循环列表），便于范围查找，也便于排序。

InnoDB的索引使用的是B+Tree结构，那么为什么InnoDB的主键最好要搞成有序的？

InnoDB中主键索引是聚集索引，所有数据都存在主键索引所在的聚集索引的B+Tree结构的叶子节点中。如果每次插入的主键是大小随机的话，每次数据进来找到的叶子节点的位置是随机的，这样的话，有些叶子节点所在页本来就排满了，结果又来了一条数据，就势必要引起页分裂，所以导致性能下降；但是如果主键是有序的话，每次进行都找到当前叶子前面的位置，一个一个叶子按顺序排满一个页再排一个页，就不会又页分裂的问题了。所以自增主键对于InnoDB这种使用B+Tree索引的存储引擎来说，性能更好。

本文链接：https://blog.csdn.net/weixin_35794878/article/details/122609218

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Simplygon软件之SimplygonUI 编辑器界面-程序员宅基地

文章浏览阅读2.8k次。Simplygon UISimplygonUI 默认布局Simplygon 安装完成后，可以双击快捷图标启动软件，软件启动后需要登入，登陆方式有两种1.Grid：在安装有 Simplygon Grid Server 功能的其他本地服务器上处理工作选择 Grid 选项卡输入登陆凭证和服务器 IP 地址进行登陆，用户管理和凭证通过 Simplygon Grid管理实用程序进行管理 Si..._simplygon

如何写出高转化率文案_如何写出高转化率文案 pdf-程序员宅基地

文章浏览阅读465次。解剖1个案例，解锁8种文案写法！ 1、以小写大。关键在于有多大？只小不大无价值，只大不小无效果。照顾树木、工人违规、修改设计是小事，却放大了土地价值：别墅的核心价值。 2、以具象写抽象。以小写大，就是以细节写整体，也是以具象写抽象。稀缺、珍惜、用心是抽象概念，直接写出来是瞎吆喝，要通过具象的行为和过程，让消费者感受到。为保护这片原生林，开发商自掏腰包养了一个护林队，这才是消费者可以感受到的珍惜和用心。 3、以形象写具象只具象，不够，还要形象。人是通过形象来记忆、来联想的。这几个标题和内文是具_如何写出高转化率文案 pdf

spring boot mybatis-generator 使用tk.mybatis.mapper通用mapper自动生成代码_tk.mybatis.mapper.generator.mapperplugin-程序员宅基地

文章浏览阅读1.3w次，点赞2次，收藏17次。前言这次的项目，使用spring boot 多模块开发。其中，数据库集成了data Jpa 和 Mybatis。最先引入的data jpa，但是后面涉及到多表关联多条件查询的时候，就显得很麻烦。然后就把mybatis也引入了进来。这里重点记录一下如何使用通用mapper逆向生成代码。提高我们的工作效率。环境开发工具：IntelliJ IDEA 2018项目框架：基于Spring B..._tk.mybatis.mapper.generator.mapperplugin

量化投资之工具篇一：Backtrader从入门到精通（7）-Indicator类源代码解读（2）_dst[i] = math.fsum(src[i - period + 1:i + 1]) / pe-程序员宅基地

文章浏览阅读6.4k次，点赞20次，收藏54次。接上一篇继续。系统内置Indicator的介绍Backtrader提供了很多内置的Indicator，了解这些Indicator对我们自定义指标、理解现有指标以及制定策略具有重要作用。基本操作类Backtrader提供了很多基本操作类，作为定义其他指标的基准。先看PeriodN，这个类是所有需要使用周期进行计算指标（例如移动平均）的基类：class PeriodN(Indicator): ''' Base class for indicators which take a per_dst[i] = math.fsum(src[i - period + 1:i + 1]) / period indexerror: array ass

N76E003使用syn6288_n76e003 开发环境-程序员宅基地

转载：Ubuntu16.04安装视觉SLAM环境（g2o）-程序员宅基地

文章浏览阅读102次。原文链接https://www.cnblogs.com/ambition921009/p/10551959.html1、首先在github上下载g2o图优化库git clone https://github.com/RainerKuemmerle/g2o.git2、运行安装以下依赖库sudo apt-get install libcholmod3.0.6sudo apt-get ...

随便推点

西瓜书《机器学习》课后答案——Chapter6_6.3_实验二、自主选择两个uci数据集,分别用高斯核训练svm分类器以及bp神经网络进行分-程序员宅基地

文章浏览阅读8.2k次，点赞5次，收藏45次。6.3 选择两个UCI数据集，分别用线性核和高斯核训练一个SVM，并与BP神经网络和C4.5决策树进行实验比较。解答：（1）准备libsvm的训练数据与测试数据从UCI网站上选择了Iris数据集，这个数据集总共分为3类，每类50个样本，每个实例有四个属性。数据保存在bezdekIris.txt文件中，举一个样本为例：5.1,3.5,1.4,0.2,Iris-setosa书中也没有介绍解决多_实验二、自主选择两个uci数据集,分别用高斯核训练svm分类器以及bp神经网络进行分

HBase-2.4.6安装教程附常见错误解决_hbase2.4.6-程序员宅基地

文章浏览阅读741次。我这里采用了jdk1.8.0_301+hadoop-3.3.1+zookeeper-3.6.3+hbase-2.4.6的版本不同版本可能不能兼容，兼容性问题可以去官网查看http://hbase.apache.org/book.html#_preface我这里有三台虚拟机，hadoop102,hadoop103,hadoop1041、zookeeper正常部署首先保证三台机器的zookeeper正常启动[user@hadoop102 zookeeper-3.6.3]$ bin/zkServer.s_hbase2.4.6

技术合同填写说明_本合同履行完毕后,上述技术资料按以下方式处理-程序员宅基地

文章浏览阅读6.1k次，点赞4次，收藏7次。技术合同填写说明所属类别：办事指南发布时间：2009年6月12日合同编号：技术开发（委托）合同项目名称：用简明、准确的文字表达合同的标的和名称委托方（甲方）：用《企业法人营业执照》规定的法定名称（买方）_本合同履行完毕后,上述技术资料按以下方式处理

Exynos4412异步串口通信及实验_异步串行通信方式数据值怎么求-程序员宅基地

文章浏览阅读3.7k次，点赞2次，收藏12次。通信传输方式串行通信（二进制）串行传送，数据是按顺序一位一位传送，一条数据线或差分线传输并行通信数据各位同时传送，多条数据线比较：串行通常传输速度比较慢，成本低，适用于计算机间的远距离传输。并行传输速率高，成本也高，适用于近距离设备传输，当然了还有RS-485，RS-422，使用了串行差分通信总线，传输速率快，抗干扰性能好，同时传输距离远。同步传输与异步传输_异步串行通信方式数据值怎么求

SpringCloud若依RuoYi多数据源切换_若依框架下业务层一个方法下更换数据源调用接口-程序员宅基地

文章浏览阅读3.8k次。若依自带dynamic-datasource直接使用com.baomidou.dynamic.datasource.annotation.DS注解就可以完成多数据源切换有 dynamic-datasource 就不用添加这个依赖<dependency> <groupId>com.baomidou</groupId> <artifactId>dynamic-datasource-spring-boot-starter</artifactId&_若依框架下业务层一个方法下更换数据源调用接口

11级_Java_曹建波 03.02 Struts2_事物管理&文件上传-程序员宅基地

文章浏览阅读98次。在实现登陆后对admin的增删改查的操作中。http客户端------------->web容器----->struts2过滤器------->struts.xml--->Action----service-->dao->J数据库登陆Action中验证用户是否登陆成功Adminentity;getEntity(){returnen..._java struts2事物