B-Tree、B+Tree_命运的左岸的博客-CSDN博客_为什么b树的高度与磁盘存取成正比
B-Tree、B+Tree
命运的左岸
于 2018-01-03 21:31:35 发布
3190
收藏
分类专栏：
数据结构
文章标签：
B-Tree
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/mingyundezuoan/article/details/78965745
版权
数据结构
专栏收录该内容
1 篇文章
0 订阅
订阅专栏
B-Tree、B+Tree
B-Tree
B 树又叫平衡多路查找树。一棵m阶的B树的特性如下：
树中每个结点最多含有m个孩子（m>=2）；除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，……，Kn，Pn)。其中：
Ki (i=1…n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。 Pi为指向子树根的接点，且指针P(i-1)指向子树中所有结点的关键字均小于Ki，但都大于K(i-1)。 关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。
B-Tree的度：
结点：表示树中的元素。结点的度：拥有子结点的个数。叶子：度为0的结点。树的度：树中结点的最大的度。结点的层次：根结点是第一层，它的孩子结点是第二层，依次类推。树的高度：最大层次数。B-Tree中每个节点能包含的关键字的数量有一个上界和下界。下界称为B-Tree的最小度数。
// 上图是一个度数为2的B-Tree，而不是 4,此处 B-Tree 的度指代的是B-Tree的最小度数
// 另一篇博文中对B-Tree的描述如下：
d为大于1的一个正整数，称为B-Tree的度。
每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d
// 如果按照二叉树中对度的定义去理解的话，d 是节点的最大孩子数，那么非叶子节点拥有的指针个数 n 就应该等于 d , 又何谈 n <= 2d , 因为随着指针个数的增大，B-Tree 的度也在随之增大，n 的上限永远也达不到 2d
// 此处个人理解有误，纠结了好久。
B-Tree的高度
从B-Tree的最小度来计算
B树上大部分操作所需的磁盘存取次数与B树的高度成正比。下面分析B树的最坏高度情况。如果n>=1, 则对任意一棵包含n个关键字、高度为h（从0开始）、最小度数t>=2的B树有： h = logt((n+1)/2);证明：
如果一棵B-Tree的高度为h，最小度数 t （即每个节点中包含的关键字数量的下界）根节点至少包括一个关键字，而其他节点至少t个关键字。t+1 个孩子深度为0的节点，即根节点，只有1个节点，至少有t个关键字深度为1的节点至少有2个，至少有2t个关键字深度为2的节点至少有2(t+1)个，至少有2t(t+1)个关键字（每个节点中关键字数量的下限t，则该节点至少有t+1个孩子节点）深度为3的节点至少为2*
(t+1)2
个，至少有2t*
(t+1)2
个关键字深度为h-1的节点至少有2
(t+1)h−2
个，至少有2t
(t+1)h−2
个关键字深度为h 的节点至少为2
(t+1)h−1
个，深度为h的叶子节点，不保存关键字信息，因此，n = t+2t+2(t+1)t+2t
(t+1)2
+……+2t*
(t+1)h−2
1n - 1
2( t +
t2
+
t3
+……+
th−2
) （ 此处：类比二叉树，节点总数 n = 1+2 +
22
+ …….+
2h−1
n =
2h
- 1 h =
log2(n+1)
） n - 1
2(
th−2
- 1) 所以：
h≥logt(n+1)2
从B-Tree的阶数计算
若B树某一非叶子节点包含N个关键字，则此非叶子节点含有N+1个孩子结点，而所有的叶子结点都在第I层，我们可以得出：
因为根至少有两个孩子，因此第2层至少有两个结点。除根和叶子外，其它结点至少有┌
m2
┐个孩子，因此在第3层至少有2*┌
m2
┐个结点，在第4层至少有2*┌
(m2)2
┐个结点，在第 I层至少有2*┌
(m2)(I−2)
┐个结点，于是有： N+1 ≥ 2*┌
(m2)(I−2)
)┐；考虑第L层的结点个数为N+1，那么2*┌
(m2)(I−2)
)┐≤N+1，也就是L层的最少结点数刚好达到N+1个，即：
I≤logm2(N+1)2+2
；所以当B树包含N个关键字时，B树的最大高度为l-1（因为计算B树高度时，叶结点所在层不计算在内），即：
l−1=logm2(N+1)2+1
B-Tree 数据检索
检索过程描述
首先从根节点进行二分查找如果找到则返回对应节点的data否则对相应区间的指针指向的节点递归进行查找根据根节点的数据与需要查找的数据进行比较，确认走哪个分支直到找到节点或找到null指针，前者查找成功，后者查找失败
伪代码实现
BTree_Search(node, key) {
if(node == null) return null;
foreach(node.key)
if(node.key[i] == key) return node.data[i];
// 走节点的左侧指针指向的分支
if(node.key[i] > key) return BTree_Search(point[i]->node);
// 走节点的右侧指针指向的分支
return BTree_Search(point[i+1]->node);
data = BTree_Search(root, my_key);
时间复杂度
查找次数与高度 h 有关，
h≥logt(n+1)2
时间复杂度为：
O(logdN)
B+Tree
B+树是B-树的变体，也是一种多路搜索树，其定义基本与B-树同，区别：
1.非叶子结点的子树指针与关键字个数相同；2.非叶子结点的子树指针P[i]，指向关键字值属于[K[i],K[i+1])的子树（B-树是开区间）；3.为所有叶子结点增加一个链指针；在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree；目的：是为了提高区间访问的性能4.所有关键字都在叶子结点出现5.B+Tree中叶节点和内节点一般大小不同；虽然B-Tree中不同节点存放的key和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree往往对每个节点申请同等大小的空间
特性：
所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；不可能在非叶子结点命中查询结果；数据记录存储在叶子节点中非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；更适合文件索引系统；更适合实现外存储索引结构，具体原因与外存储器原理及计算机存取原理有关
参考资料
B-Tree 、B+树、B*树树的术语及性质
命运的左岸
关注
关注
点赞
收藏
打赏
评论
B-Tree、B+Tree
B-Tree、B+TreeB-TreeB 树又叫平衡多路查找树。一棵m阶的B树的特性如下：树中每个结点最多含有m个孩子（m>=2）；除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；所有叶
复制链接
扫一扫
专栏目录
Java实现B+Tree
01-12
步骤为数据库文件创建一个B+树索引：
(1)生成数据文件，
(2)为数据库文件的属性创建B+ 树文件。
(3)给定键值，通过B+树进行查找。同时比较与直接扫描表的性能差别。（利用B+树时可根据内存大小决定放置多少层次到内存）
(4)给定键值，完成数据插入，并按需更新B+树。
(5)给定键值，完成数据删除，并按需更新B+树
资源包括：Java源码及实验报告！
数据结构 | 【查找】考研相关结论与例题
Jeremiah
07-19
1277
采用顺序查找算法，对有序表从头开始查找，发现当前元素已不小于待查元素时，停止查找，确定查找不成功，已知查找任一元素的概率是相同的，则在两种表中成功查找（）.【解析】对于顺序查找，不管线性表是有序的还是无序的，成功查找第一个元素的比较次数为1，成功查找第二个元素的比较次数为2，以此类推，即。2、已知一个长度为16的顺序表，其元素按关键字有序排列，若采用折半查找法查找一个中不存在的元素，则比较的次数至少是（），至多是（）。D选项，1、10相加除二向下取整，6、7相加除二向上取整，矛盾。下列二叉树中，可能成为折半
参与评论
您还未登录，请先
登录
后发表或查看评论
B+Tree详解
最新发布
我的博客
11-17
453
不爱写博客。但是为了流水线，为了乐爷，为了zzq，为...(可变参数)能咋办。写呗
B树(B-树)最大最小高度的推导
weixin_46127065的博客
10-07
1243
B树(B-树)最大最小高度的推导
推导B树的最大高度和最小高度得出B树的高度范围
乐行僧的博客
08-28
1万+
前提条件：n>=1，则对于任意一棵包含n个关键字、高度为h、阶数为m的B树。
一、最小高度：
对于任意树类型的数据结构，如果其每层节点能够分布的足够满，其高度也会随之变得足够的低。基于这个思路，对于B树无外乎也是一种树，B树的关键子树以及儿子节点个数满足这样的条件(ceil代表向上取整)：
//根节点
儿子节点个数[2, m]
关键字个数[1, m-1]
//非根节点
儿子节点个数[...
B树最大高度推导
Guo_ping'blog
12-31
7179
文章目录B树最大高度推导推导B树的最小高度推导最大高度B+树：MySQL数据库索引是如何实现的？1. 遇到问题2. 尝试用学过的数据结构解决这个问题3. 改造二叉查找树4. 索引的弊端
B树最大高度推导
【声明几个重要概念】
B树的关键字就是要查找的东西
B树中的 阶：可理解为分支数. 三阶树也可理解三叉树
按照定义：
m阶B tree，每个节点最多有 m 个subnode，除根节点和叶子节点外，...
【数据结构与算法】B tree 即相关操作 深入解读
u010900754的专栏
02-24
551
B tree是从其他搜索树结构中延伸出来的一种用于外存设备比如disk的一种数据结构。先抛开B tree与disk的关系，单纯地了解下数据结构。
1.定义
粗略地来讲，B tree定义主要包含以下几个方面：
（1）每一个节点的结构，节点包含关键字key，指针pointer，key数目n和叶节点标志bool。
（2）顺序问题，每一个节点的key以非降序方式排列。而且，如果ci是ki和ki+1...
（五）平衡多路查找树（B-Tree B+Tree）
kaka
06-30
6946
B-tree就是我们常说的B树，常常用于实现数据库索引，因为它的查找效率比较高
前面提到的2-3树可以看作B树的一种实例
一.为什么不用二叉搜索树用B树？
二叉查找树的时间复杂度是O（logN），查找次数和比较次数较少，但是对于磁盘的IO次数，最坏情况下磁盘的IO次数由树的高度决定，所以减少磁盘IO次数就必须压缩树的高度，让瘦高的树尽量变成矮胖的树，这样B树就诞生了
二.B-...
BTree和B+Tree详解
MayMatrix 的博客
04-16
746
B-Tree是平衡搜索多叉树。
B+树索引是B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平衡（balance），而不是二叉（binary），因为B+树是从最早的平衡二叉树演化而来的。
在讲B+树之前必须先了解二叉查找树、平衡二叉树（AVLTree）和平衡多路查找树（B-Tree），B+树即由这些树逐步优化而来。
树 是数据结构基础知识，想要深...
B-Tree 和 B+Tree详解
weixin_54787921的博客
05-06
1312
B-Tree 和 B+Tree一、什么是B-Tree1.B树插入2.B树删除3.总结二、什么是B+Tree1.B+树插入2.B+树删除3.总结
一、什么是B-Tree
B-Tree又叫做B树，和平衡二叉树不同的地方在于B树是多叉树(平衡多路查找树)，Oracle和MongoDB的索引技术就是基于B树的数据结构，B树也可以看作是对2-3查找树的一种扩展。
一个m阶的B-Tree有以下性质：
每个节点最多有m个子节点
每个非叶子节点（根节点除外）至少含有m/2个子节点
如果根节点不是叶子节点，那么根节点至少有
【数据结构】B树的创建
lz201788的博客
03-19
9591
B树也是一种搜索树，二叉搜索树、红黑树、都是动态查找树，典型的二叉搜索结构，查找的时间复杂度和树的高度相关O(log2N)。这些二叉搜索结构有一个共同的缺陷：数据量大，树的高度太高，增大访问磁盘的次数，从而效率低下。想要加速对数据的访问速度：
1.提高I/O的时间
2.降低树的高度——平衡多叉树B树的定义
一棵M阶（M>2）的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足以下性质：
B树的阶和最小度
m0_47360218的博客
07-13
2267
数据结构
度：一个结点含有的子结点的个数称为该结点的度【百度百科】
阶：一棵树的最大孩子数
B树
最小度minimum degree（t）：用来衡量结点的关键字数量范围
阶 order（m）：衡量B树的最多孩子数
结点的关键字数范围： t-1至2t-1
B树的最大孩子数 = 2t
他们关系如下：
t=Math.ceil(m/2) (向上取整)
m = 2t
例子：
假如定义一颗B树的最小度为3，那么结点（除根节点）的关键字数在2~5，孩子数最大为6
...
B树的创建
fern_girl的博客
06-01
8220
1.B树的概念一棵M阶的（M>2） 的平衡二叉树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：
根节点至少有两个孩子；
原因：因为根节点至少有一个关键字，有两个指针域；
每个非根节点至少有M/2-1（上取整）个关键字，至多有M-1个关键字，并且以升序排列；
每个非根节点至少有M/2（上取整）个孩子，至多有M个孩子；
key[i]和key[i+1]之间的孩子节点的值介于key[i]、ke
B-树 构建
Dream_JW的博客
02-22
3108
经常不写博客感觉有些知识都有些模糊，闹了许多笑话。现在开始将自己之前接触到的学习过的，还有正准备学习研究的记录下来。方便自己回看，也便于交流。
今天看到了一种新的搜索结构B-树。之前刚开始接触二叉树时感觉挺简单的，以为树也差不多。今天才发现在插入时挺复杂的。
B-树——平衡多叉树
一棵M阶（M>2）的B树，是一棵平衡的M路平衡搜索树。满足以下性质。
1.
图解B树构建过程
桔飞飞
06-24
5560
1.B树结构同时满足以下特性
每个节点最多包含n个孩子，即n叉树；
除了根节点和叶子节点外，每个节点至少有ceil(n/2)个孩子（ceil是向上取整）；
若根节点不是叶子节点，则至少有两个孩子；
所有叶子节点在同一层；
☆☆☆每个非叶子节点由m个key和m+1个指针组成，其中(ceil(n/2)-1)<=m<=n-1；
【B树的非叶子节点示意图】
key是存储的值，保存的是数据表某一列的内容
p是指针，指向当前节点的孩子
一个非叶子节点中包括m个key和m+1个指针
【伪代码示例】
mysql索引原理：B-Tree 和 B+Tree简介
许佳佳的博客
10-17
1395
本文参考：https://www.kancloud.cn/kancloud/theory-of-mysql-index/41856
完全不了解B-Tree的读者可以先看下这篇文章：
https://www.kancloud.cn/kancloud/theory-of-mysql-index/41844
B-Tree
B-Tree毫无疑问是树结构，如下图：
主要有以下特性：
d为大于1的一个...
B+Tree 与 B-Tree
qq_36647176的博客
03-10
110
一 B-Tree
1. d为大于1的一个正整数，称为B-Tree的度。（即一个节点内包含的关键字个数，如图是15 56 77 三个）
2. h为一个正整数，称为B-Tree的高度。（与树的定义相同）
3 .M是节点的孩子个数，称为b树的阶
特性
B树中每个节点包含了键值和数据对象，
任何一个关键字出现且只出现在一个结点中；（15 56 77 等就是关...
B-Tree 、B+树、B*树
ZhangXL的专栏
08-17
1万+
大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。
1. B-Tree
B 树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树。许多数据库系统都一般使用B树或者B树的各种变形结构，如下文即将要介绍的B+树
B-Tree和B+Tree详解
tyrroo的博客
06-22
605
B+树索引是B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平衡（balance），而不是二叉（binary），因为B+树是从最早的平衡二叉树演化而来的。在讲B+树之前必须先了解二叉查找树、平衡二叉树（AVLTree）和平衡多路查找树（B-Tree），B+树即由这些树逐步优化而来。
二叉查找树
二叉树具有以下性质：左子树的键值小于根的键值，右子树的键值大于根的键值。
如下图所示就是一棵二叉查找树，
对该二叉树的节点进行查找发现深度为1的节点的查找次数为1，深...
简单剖析B树（B-Tree）与Ｂ+树
热门推荐
编程随笔与杂谈
03-25
6万+
注意：首先需要说明的一点是：B-树就是B树，没有所谓的B减树
引言
　　我们都知道二叉查找树的查找的时间复杂度是Ｏ(log N)，其查找效率已经足够高了，那为什么还有Ｂ树和Ｂ＋树的出现呢？难道它两的时间复杂度比二叉查找树还小吗？
　　答案当然不是，Ｂ树和Ｂ＋树的出现是因为另外一个问题，那就是磁盘ＩＯ；众所周知，ＩＯ操作的效率很低，那么，当在大量数据存储中，查询时我们不能一下子将所有数据加载到...
“相关推荐”对你有帮助么？
非常没帮助
没帮助
一般
有帮助
非常有帮助
提交
©️2022 CSDN
皮肤主题：大白
设计师：CSDN官方博客
返回首页
命运的左岸
CSDN认证博客专家
CSDN认证企业博客
码龄11年
暂无认证
517
原创
2万+
周排名
108万+
总排名
74万+
访问
等级
8282
积分
128
粉丝
163
获赞
41
评论
699
收藏
私信
关注
热门文章
java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.String
53488
@Transactional
42541
ERR invalid expire time in setex
24959
Failed to invoke the method getXXX in the service
21116
Exception 'java.lang.Exception' is never thrown in the method less
20621
分类专栏
Algorithm
1篇
CAS
4篇
Collection
4篇
Conception
1篇
Concurrent
14篇
Docker
4篇
Dubbo
5篇
Guava
3篇
Git
Hadoop
9篇
Hbase
4篇
Hive
7篇
Idea
7篇
Java
9篇
java.io
1篇
java.lang
13篇
java.lang.ref
6篇
java.util
16篇
java.util.concurrent.atomic
1篇
JavaWeb
10篇
JVM
2篇
Linux
11篇
Maven
1篇
MyBatis
19篇
MyBatis 技术内幕
6篇
MySQL
37篇
NIO
5篇
Poi
1篇
Python
2篇
RabbitMq
2篇
Redis
2篇
Regex
1篇
RPC
1篇
Shell
1篇
Shiro
3篇
Slf4j
1篇
Spring
5篇
Spring 标签
1篇
Storm
6篇
sun.misc
1篇
SVN
3篇
Tomcat
2篇
UML
2篇
Velocity
6篇
Zookeeper
3篇
读书笔记
12篇
点滴生活
1篇
人生感悟
2篇
人生哲理
1篇
书香人生
5篇
心理书籍
1篇
学习方法
3篇
自我感悟
1篇
多线程
7篇
配置管理
5篇
数据结构
1篇
代码艺术
10篇
编程习惯
3篇
常用代码
4篇
设计模式
6篇
设计原则
1篇
面试总结
29篇
编码规则
4篇
方案设计
1篇
职场原则
9篇
职场办公
2篇
项目管理
1篇
自律人生
2篇
功能实现
18篇
技巧总结
8篇
电影赏析
3篇
电影漫威
19篇
其他知识
9篇
性能调优
1篇
问题总结
5篇
问题汇总
22篇
异常汇总
63篇
异常记录
20篇
最新评论
java.lang.OutOfMemoryError: Java heap space
wo41chuan_luan_ma:
感觉懂了，又感觉没懂，这种是设置xss大点就可以吗，默认是1m
fastjson.toJSONString() 输出 {"empty":false}
m0_52316587:
怎么解决阿
Exception 'java.lang.Exception' is never thrown in the method less
Talonc:
还有可能情况是 代码已经try-catch-finally 了 但是 还是throws Exception 了 把 throws 删掉就行
如何解决@Resource引入服务为空问题
不羡不妒:
什么锤子
您愿意向朋友推荐“博客详情页”吗？
强烈不推荐
不推荐
一般般
推荐
强烈推荐
提交
最新文章
线程概念
多线程知识体系
如何有效阅读一本书
2019年99篇
2018年142篇
2017年175篇
2016年17篇
2015年86篇
目录
目录
分类专栏
Algorithm
1篇
CAS
4篇
Collection
4篇
Conception
1篇
Concurrent
14篇
Docker
4篇
Dubbo
5篇
Guava
3篇
Git
Hadoop
9篇
Hbase
4篇
Hive
7篇
Idea
7篇
Java
9篇
java.io
1篇
java.lang
13篇
java.lang.ref
6篇
java.util
16篇
java.util.concurrent.atomic
1篇
JavaWeb
10篇
JVM
2篇
Linux
11篇
Maven
1篇
MyBatis
19篇
MyBatis 技术内幕
6篇
MySQL
37篇
NIO
5篇
Poi
1篇
Python
2篇
RabbitMq
2篇
Redis
2篇
Regex
1篇
RPC
1篇
Shell
1篇
Shiro
3篇
Slf4j
1篇
Spring
5篇
Spring 标签
1篇
Storm
6篇
sun.misc
1篇
SVN
3篇
Tomcat
2篇
UML
2篇
Velocity
6篇
Zookeeper
3篇
读书笔记
12篇
点滴生活
1篇
人生感悟
2篇
人生哲理
1篇
书香人生
5篇
心理书籍
1篇
学习方法
3篇
自我感悟
1篇
多线程
7篇
配置管理
5篇
数据结构
1篇
代码艺术
10篇
编程习惯
3篇
常用代码
4篇
设计模式
6篇
设计原则
1篇
面试总结
29篇
编码规则
4篇
方案设计
1篇
职场原则
9篇
职场办公
2篇
项目管理
1篇
自律人生
2篇
功能实现
18篇
技巧总结
8篇
电影赏析
3篇
电影漫威
19篇
其他知识
9篇
性能调优
1篇
问题总结
5篇
问题汇总
22篇
异常汇总
63篇
异常记录
20篇
目录
评论
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
查看更多评论
打赏作者
命运的左岸
你的鼓励将是我创作的最大动力
¥2
¥4
¥6
¥10
¥20
输入1-500的整数
余额支付
(余额：-- )
扫码支付
扫码支付：¥2
获取中
扫码支付
您的余额不足，请更换扫码支付或充值
打赏作者
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额
抵扣说明：
1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。 2.余额无法直接购买下载，可以购买VIP、C币套餐、付费专栏及课程。
余额充值