二叉树学习笔记之B树、B+树、B*树

简介: 动态查找树主要有二叉查找树(Binary Search Tree),平衡二叉查找树(Balanced Binary Search Tree), 红黑树 (Red-Black Tree ), 都是典型的二叉查找树结构,查找的时间复杂度 O(log2-N) 与树的深度相关,降低树的深度会提高查找效率,于是有了多路的B-tree/B+-tree/ B*-tree (B~Tree)。

动态查找树主要有二叉查找树(Binary Search Tree),平衡二叉查找树(Balanced Binary Search Tree), 红黑树 (Red-Black Tree ),

都是典型的二叉查找树结构,查找的时间复杂度 O(log2-N) 与树的深度相关,降低树的深度会提高查找效率,于是有了多路的B-tree/B+-tree/ B*-tree (B~Tree)。

关于这B树以及B树的两种变体,其实很好区分,

相比B树,B+树不维护关键字具体信息,不考虑value的存储,所有的我们需要的信息都在叶子节点上,

B*树在B+树的基础上增加了非叶子节点兄弟间的指针,在某些场景效率更高,

主要掌握B树的操作,也就掌握了这两种变体树的操作。


B树(B-tree),即B-树

注意B树也就是B-树,B树的英文是B-tree,很多地方直译成了B-树,其实B-树和B树是同一种树。
B树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树。

(1)B-Tree的接点结构
B-tree中,每个结点包含:
本结点所含关键字的个数;
指向父结点的指针;
关键字;
指向子结点的指针数组;

1
2
3
4
5
6
7
8
9
10
#define Max l000 //结点中关键字的最大数目:Max=m-1,m是B-树的阶
#define Min 500 //非根结点中关键字的最小数目:Min=m/2-1
typedef  int  KeyType;  //KeyType关键字类型由用户定义
typedef  struct  node{  //结点定义中省略了指向关键字代表的记录的指针
     int  keynum;  //结点中当前拥有的关键字的个数,keynum<<Max
    KeyType key[Max+1];  //关键字向量为key[1..keynum],key[0]不用。
     struct  node *parent;  //指向双亲结点
     struct  node *son[Max+1]; //指向孩子结点的指针数组,孩子指针向量为son[0..keynum]
  }BTreeNode;
typedef  BTreeNode *BTree;

(2)B-tree的特点

  • B-tree是一种多路搜索树(并不是二叉的),对于一棵M阶树:
  • 定义任意非叶子结点最多只有M个孩子;且M>2;
  • 根结点的孩子数为[2, M],除非根结点为叶子节点;
  • 除根结点以外的非叶子结点的儿子数为[M/2, M];
  • 非叶子结点的关键字个数=指向儿子的指针个数-1;
  • 每个非叶子结点存放至少M/2-1(取上整)和至多M-1个关键字;
  • 非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
  • 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
  • 所有叶子结点位于同一层;

以M=3的一棵3阶B树为例:

一棵包含了24个英文字母的5阶B树的结构:

(3)B-tree高度与复杂度

B树的高度是,而不是其它几种树的H=log2n,其中T为度数(每个节点包含的元素个数),即所谓的阶数,n为总元素个数或总关键字数。

B树查找的时间复杂度为O(Log2-N),下面是参考推导过程:



其中M为设定的非叶子结点最多子树个数,N为关键字总数;所以B-树的性能总是等价于二分查找(与M值无关),也就没有AVL树平衡的问题。

 


B-tree的基本操作

(1)查找操作

在B-树中查找给定关键字的方法类似于二叉排序树上的查找。不同的是在每个结点上确定向下查找的路径不一定是二路而是keynum+1路的。
对结点内的存放有序关键字序列的向量key[l..keynum] 用顺序查找或折半查找方法查找。若在某结点内找到待查的关键字K,则返回该结点的地址及K在key[1..keynum]中的位置;否则,确定K在某个key[i]和key[i+1]之间结点后,从磁盘中读son[i]所指的结点继续查找。直到在某结点中查找成功;或直至找到叶结点且叶结点中的查找仍不成功时,查找过程失败。

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
BTreeNode *SearchBTree(BTree T,KeyType K, int  *pos)
  //在B-树T中查找关键字K,成功时返回找到的结点的地址及K在其中的位置*pos
//失败则返回NULL,且*pos无定义
   int  i;
   T→key[0]=k;  //设哨兵.下面用顺序查找key[1..keynum]
   for (i=T->keynum;K<t->key[i];i--);  //从后向前找第1个小于等于K的关键字
   if (i>0 && T->key[i]==1){  //查找成功,返回T及i
     *pos=i;
     return  T;
    //结点内查找失败,但T->key[i]<K<T->key[i+1],下一个查找的结点应为
      //son[i]
   if (!T->son[i])  //*T为叶子,在叶子中仍未找到K,则整个查找过程失败
     return  NULL;
     //查找插入关键字的位置,则应令*pos=i,并返回T,见后面的插入操作
   DiskRead(T->son[i]);  //在磁盘上读人下一查找的树结点到内存中
   return  SearchBTree(T->Son[i],k,pos);  //递归地继续查找于树T->son[i]
  }

  

(2)查找操作的时间开销
B-树上的查找有两个基本步骤:
1.在B-树中查找结点,该查找涉及读盘DiskRead操作,属外查找;
2.在结点内查找,该查找属内查找。
查找操作的时间为:
1.外查找的读盘次数不超过树高h,故其时间是O(h);
2.内查找中,每个结点内的关键字数目keynum<m(m是B-树的阶数),故其时间为O(nh)。
注意:
1.实际上外查找时间可能远远大于内查找时间。
2.B-树作为数据库文件时,打开文件之后就必须将根结点读人内存,而直至文件关闭之前,此根一直驻留在内存中,故查找时可以不计读入根结点的时间。

(3)插入操作

 插入一个元素时,首先在B树中是否存在,如果不存在,即在叶子结点处结束,然后在叶子结点中插入该新的元素,注意:如果叶子结点空间足够,这里需要向右移动该叶子结点中大于新插入关键字的元素,如果空间满了以致没有足够的空间去添加新的元素,则将该结点进行“分裂”,将一半数量的关键字元素分裂到新的其相邻右结点中,中间关键字元素上移到父结点中(当然,如果父结点空间满了,也同样需要“分裂”操作),而且当结点中关键元素向右移动了,相关的指针也需要向右移。如果在根结点插入新元素,空间满了,则进行分裂操作,这样原来的根结点中的中间关键字元素向上移动到新的根结点中,因此导致树的高度增加一层。

(4)删除操作

首先查找B树中需删除的元素,如果该元素在B树中存在,则将该元素在其结点中进行删除,如果删除该元素后,首先判断该元素是否有左右孩子结点,如果有,则上移孩子结点中的某相近元素到父节点中,然后是移动之后的情况;如果没有,直接删除后,移动之后的情况。

B+树(B+-tree)

B+-tree是应文件系统所需而产生的一种B-tree的变形树。

(1)B树和B+树的对比
一棵m阶的B+树和m阶的B树的异同点在于:
1.有n棵子树的结点中含有n-1 个关键字;
2.所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)
3.所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字。 (而B 树的非终节点也包含需要查找的有效信息)
(2)为什么说B+-tree比B 树更适合实际应用中操作系统的文件索引和数据库索引?

  •  B+-tree的磁盘读写代价更低

B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。

如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。

一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子,假设磁盘中的一个盘块容纳16bytes,而一个关键字2bytes,一个关键字具体信息指针2bytes。

一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候,B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

  • B+-tree的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。


B*树(B*-tree)

B*-tree是B+-tree的变体,在B+树的基础上(所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针),

B*树中非根和非叶子结点再增加指向兄弟的指针;

B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2)。

下图是一棵典型的B*树:

 


目录
相关文章
|
SQL 存储 Oracle
6 张图带你彻底搞懂分布式事务 XA 模式
XA 协议是由 X/Open 组织提出的分布式事务处理规范,主要定义了事务管理器 TM 和局部资源管理器 RM 之间的接口。目前主流的数据库,比如 oracle、DB2 都是支持 XA 协议的。
13647 1
6 张图带你彻底搞懂分布式事务 XA 模式
|
消息中间件 SQL 存储
超详细的RabbitMQ入门,看这篇就够了!
RabbitMQ入门,看这篇就够了
217030 68
|
数据采集 人工智能 数据管理
12款开源数据资产(元数据)管理平台选型分析(二)
12款开源数据资产(元数据)管理平台选型分析(二)
2793 0
Centos8安装yum源时候出现的异常问题及解决方案(保好使)
Centos8安装yum源时候出现的异常问题及解决方案(保好使)
|
关系型数据库 MySQL 数据库
[图解MySQL]MySQL组提交(group commit)
[图解MySQL]MySQL组提交(group commit)
18246 0
|
机器学习/深度学习 人工智能 自然语言处理
为什么要学习大模型?
本文深入探讨了大模型的学习意义、应用需求及训练方法,帮助读者理解其底层逻辑与潜力。通过类比PPT和Excel在职场中的重要性,强调掌握大模型技能对未来职业发展的关键作用。文章还分析了LLM微调的必要性及其在企业内外部场景的应用价值,如智能客服、游戏NPC等。此外,专栏专注于ChatGPT与通义千问的训练原理,提供系统化的学习路径,适合从零基础到进阶的不同人群。无论想提升工作效率还是从事相关工程开发,都能从中受益。内容收录于[Github](https://github.com/Java-Edge/Java-Interview-Tutorial),欢迎关注!
426 0
为什么要学习大模型?
|
存储 运维 监控
如何设计高可用的分布式系统
【7月更文挑战第29天】设计高可用的分布式系统是一个复杂而细致的过程,需要从架构设计、冗余策略、故障转移与恢复、监控与告警等多个方面综合考虑。通过采用微服务架构、无状态服务、负载均衡、数据冗余、服务冗余、跨地域部署等策略,可以显著提高系统的可用性和可靠性。同时,建立完善的监控和告警体系,确保对系统的任何变化都能及时感知和处理。最终,通过不断的优化和改进,实现系统的高可用性目标。
|
算法 JavaScript 前端开发
84坐标系、02坐标系、百度坐标之间相互转换算法
最近有同学反馈之前的坐标系转换有问题,对之前的工具类进行了修正。 一、地图坐标转换java工具类 包含84坐标系、02坐标系、百度地图、高德地图、腾讯地图坐标之间相互转换的算法 wgs84ToGcj02:将 WGS84 坐标系下的经纬度转换为 GCJ02 坐标系下的经纬度。 gcj02ToWgs84:将 GCJ02 坐标系下的经纬度转换为 WGS84 坐标系下的经纬度。 gcj02ToBd09:将 GCJ02 坐标系下的经纬度转换为 BD09 坐标系下的经纬度。 bd09ToGcj02:将 BD09 坐标系下的经纬度转换为 GCJ02 坐标系下的经纬度。
1658 0
84坐标系、02坐标系、百度坐标之间相互转换算法
|
存储 SQL 缓存
MySQL 配置文件 my.cnf / my.ini 逐行详解
充分理解 MySQL 配置文件中各个变量的意义对我们有针对性的优化 MySQL 数据库性能有非常大的意义。我们需要根据不同的数据量级,不同的生产环境情况对 MySQL 配置文件进行优化。Windows 和 Linux 下的 MySQL 配置文件的名字和存放位置都是不同的,WIndows 下 MySQL 配置文件是 `my.ini` 存放在 MySQL 安装目录的根目录下;Linux 下 MySQL 配置文件是 `my.cnf` 存放在 `/etc/my.cnf`、`/etc/mysql/my.cnf`。我们也可以通过 `find` 命令进行查找。
36757 2