数据结构B树或者B+树怎么构造 求告知

求解数据结构关于B树构造等问题，谢谢~

第六题：删除87也可以是77加左边的兄弟来合并，删除33也可以是47和右边的兄弟来合并




第七题：重复的43插入时被忽略了，删除43时也可以用33替代，一般是用53

一、B树的起源

B树，最早是由德国计算机科学家Rudolf Bayer等人于1972年在论文 《Organization and Maintenance of Large Ordered Indexes》提出的，不过我去看了看原文，发现作者也没有解释为什么就叫B-trees了，所以把B树的B，简单地解释为Balanced或者Binary都不是特别严谨，也许作者就是取其名字Bayer的首字母命名的也说不定啊……

二、B树长啥样

还是直接看图比较清楚，图中所示，B树事实上是一种平衡的多叉查找树，也就是说最多可以开m个叉（m>=2），我们称之为m阶b树，为了体现本博客的良心之处，不同于其他地方都能看到2阶B树，这里特意画了一棵5阶B树 。

总的来说，m阶B树满足以下条件：

• 每个节点至多可以拥有m棵子树

• 根节点，只有至少有2个节点（要么极端情况，就是一棵树就一个根节点，单细胞生物，即是根，也是叶，也是树)
  

• 非根非叶的节点至少有的Ceil(m/2)个子树(Ceil表示向上取整，图中5阶B树，每个节点至少有3个子树，也就是至少有3个叉)
  

• 非叶节点中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示该节点中保存的关键字个数，K为关键字且Ki<Ki+1，A为指向子树根节点的指针
  

• 从根到叶子的每一条路径都有相同的长度，也就是说，叶子节在相同的层，并且这些节点不带信息，实际上这些节点就表示找不到指定的值，也就是指向这些节点的指针为空
  

B树的查询过程和二叉排序树比较类似，从根节点依次比较每个结点，因为每个节点中的关键字和左右子树都是有序的，所以只要比较节点中的关键字，或者沿着指针就能很快地找到指定的关键字，如果查找失败，则会返回叶子节点，即空指针

例如查询图中字母表中的K

• 从根节点P开始，K的位置在P之前，进入左侧指针

• 左子树中，依次比较C、F、J、M，发现K在J和M之间
  

• 沿着J和M之间的指针，继续访问子树，并依次进行比较，发现第一个关键字K即为指定查找的值
  

三、Plus版——B+树

作为B树的加强版，B+树与B树的差异在于：

• 有n棵子树的节点含有n个关键字（也有认为是n-1个关键字）
  

• 所有的叶子节点包含了全部的关键字，及指向含这些关键字记录的指针，且叶子节点本身根据关键字自小而大顺序连接
  

• 非叶子节点可以看成索引部分，节点中仅含有其子树（根节点）中的最大（或最小）关键字

请点击输入图片描述

B+树的查找过程，与B树类似，只不过查找时，如果在非叶子节点上的关键字等于给定值，并不终止，而是继续沿着指针直到叶子节点位置。因此在B+树，不管查找成功与否，每次查找都是走了一条从根到叶子节点的路径

树又叫平衡多路查找树。一棵m阶的B 树 (m叉树)的特性如下：
树中每个结点最多含有m个孩子（m>=2）；
除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；
若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；
每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
a) Ki (i=1...n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。
b) Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
c) 关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。

---

湟中县17683423706： 数据结构B树或者B+树怎么构造 求告知 - ？
恭阎洛赛： 树又叫平衡多路查找树.一棵m阶的B 树 (m叉树)的特性如下:树中每个结点最多含有m个孩子(m>=2);除根结点和叶子结点外,其它每个结点至少有[ceil(m / 2)]个孩子(其中ceil(x)是一个取上限的函数);若根结点不是叶子结点,则至...

湟中县17683423706： 数据结构B树的设计与实现 - ？
恭阎洛赛： B树的插入算法在编写过程中还是觉得比较难写的,主要的问题是,结点的分裂, 对叶子结点的分裂和对非叶节点的分裂不一样,还有就是当ptr->parent==NULL, 需要新建父结点,而新建的结点始终是树的根结点,还有结点分裂过程中子树指 ...

湟中县17683423706： 数据结构中B树、B+树的区别 - ？
恭阎洛赛： 这两种处理索引的数据结构的不同之处:1.B树中同一键值不会出现多次,并且它有可能出现在叶结点,也有可能出现在非叶结点中.而B+树的键一定会出现在叶结点中,并且有可能在非叶结点中也有可能重复出现,以维持B+树的平衡.2.因为B树键位置不定,且在整个树结构中只出现一次,虽然可以节省存储空间,但使得在插入、删除操作复杂度明显增加.B+树相比来说是一种较好的折中.3.B树的查询效率与键在树中的位置有关,最大时间复杂度与B+树相同(在叶结点的时候),最小时间复杂度为1(在根结点的时候).而B+树的时候复杂度对某建成的树是固定的.

湟中县17683423706： 求数据结构 B - 树与B+树及其操作的代码(C语言版) - ？
恭阎洛赛： # include <stdio.h># include <malloc.h>struct BTNode{ int data; struct BTNode * pLchild;//p是指针,L是左,child是孩子 struct BTNode * pRchild;};//函数声明struct BTNode * CreateBTree(void);//创建树void PreTraverseBTree(struct ...

湟中县17683423706： 如何用C++建立B+树?急急急~~感谢万分~~~？
恭阎洛赛： 这个比较复杂 这里有 http://hi.baidu.com/tries_shenzhen/blog/item/1e3bf82bfb65adf9e6cd40ed.html /* B+ 树的阶,即内部结点中键的最小数目v. 也有些人把阶定义为内部结点中键的最大数目,即2v. 一般而言,叶子结点中最大数据个数和内部...

湟中县17683423706： B - 树 建立 - ？
恭阎洛赛： 一个 B-Tree 是一种针对在块设备上优化操作的数磁盘有相当重要的数据访问延迟,尤其是机械硬盘.在随机位置检索单个字节并不比检索更大的数据花费的时间更少.这是 B-Tree 的基本原理,InnoDB 使用的数据页为 16KB.让我们尝试简化 ...

湟中县17683423706： 如何建立mysql的索引b+树 - ？
恭阎洛赛： 在MySQL里常用的索引数据结构有B+树索引和哈希索引两种,我们来看下这两种索引数据结构的区别及其不同的应用建议. 二者区别 备注:先说下, 在MySQL文档里,实际上是把B+树索引写成了BTREE ,例如像下面这样的写法: CREATE TABLE t( aid int u...

湟中县17683423706： 什么是B+树索引? - ？
恭阎洛赛： B+树是一种树数据结构,常见于数据库与档案系统之中.B+树能够使资料保持有序,并拥有均匀的对数处理时间的插入和删除动作.B树的元素通常会自底向上插入,有别于多数自顶向下插入的二叉树.B+ 树在节点访问时间远远超过节点内部...

湟中县17683423706： 举例说明oracle数据库中B树索引的基本组织结构 - ？
恭阎洛赛： B树即二叉搜索树:1.所有非叶子结点至多拥有两个儿子(Left和Right);2.所有结点存储一个关键字;3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;如:B树的搜索,从根结点开始,如果查询的关键...

湟中县17683423706： 数据结构中的是树形的结构有哪些,算法叫什么名字? - ？
恭阎洛赛： 基础类:二叉搜索(排序)树,线索二叉树,哈夫曼树(最优二叉树),二叉堆 平衡树类:AVL,红黑树,2-3树,2-3-4树,B树,B+树,B-树,treap,SBT.优先队列类:左高树(左偏树,可并堆,斜堆),双端堆,斐波那契堆 集合类:并查集 区间树类:线段树,划分树,归并树,树状数组 字母树类:字典树,后缀树.AC自动机算法 动态树类:伸展树 计算几何类:KD-tree (块状树),4叉树 RMQ转LCA:笛卡尔树 图论相关:最小生成树,无根树 其它:败者树,博弈树