算法-B-树、B树、B+树详解

算法-B-树、B树、B+树详解

文章目录

​​B-树（即B树）​​

​​B-树的定义​​

​​结点类型定义​​

​​B-树的查找​​​​B-树的插入​​​​B-树的删除​​

​​B+树​​

​​B+ 树和B-树的差异​​​​B+树的查找​​​​B+树的插入​​​​B+树的删除​​

B-tree树即B树，B即Balanced，平衡的意思。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是另一种树。而事实上是，B-tree就是指的B树。

B-树，磁盘管理系统中的目录管理，以及数据库系统中的索引组织多数都采用B-树这种数据结构。

B-树的定义

对任一关键字 K; 而言，Pi-1 相当于指向其 “ 左子树", Pi+·1相当于指向其 “右子树”。

结点类型定义

#define m 3 // B-树的阶，暂设为3typedef struct BTNode { int keynum; // 结点中关键字的个数，即结点的大小 struct BTNode *parent; // 指向双亲结点 KeyType key[m+ 1] ; // 关键字向量，0号单元未用 struct BTNode *ptr[m+1]; // 子树指针向量 Record *recptr[m+1]; // 记录指针向量，0号单元未用}BTNode,*BTree; // B-树结点和 B-树的类型typedef struct { BTNode *pt; // 指向找到的结点 int i; // 1 .. m, 在结点中的关键字序号 int tag; // 1: 查找成功， 0: 查找失败}Result; // B-树的查找结果类型

B-树的查找

由B-树的定义可知，在B-树上进行查找的过程和二叉排序树的查找类似。

例如，在上图7.22所示的B-树上查找关键字47的过程如下：首先从根开始，根据根结点指针t找到a结点，因a结点中只有一个关键字，且47> 35, 若查找的记录存在，则必在指针P1所指的子树内，顺指针找到c结点，该结点看两个关键字(43 和78), 而43 <47 < 78, 若查找的记录存在，则必在指针 P1所指的子树中。同样，顺指针找到g结点，在该结点中 顺序查找， 找到关键字47, 由此，查找成功。

查找不成功的过程也类似，例如，在同一棵树中查找23。从根开始，因为23 < 35, 则顺该结点中指针凡找到b结点，又因为b结点中只有一个关键字18, 且23 > 18, 所以顺结点中第二个指针 P1 找到*e结点。同理，因为23 < 27, 则顺指针往下找，此时因指针所指为叶子结点，说明此棵 B-树中不存在关键字23 , 查找因失败而告终。

【算法步骤】 将给定值key与根结点的各个关键字K,K2, …, Kj (1≤j≤m - 1)进行比较， 由于该关键字序列是有序的， 所以查找时可采用顺序查找， 也可采用折半查找。 查找时： ① 若key=Ki (1≤i≤j）， 则查找成功； ② 若keyKj， 则顺着指针Pj所指向的子树继续向下查找。 如果在自上而下的查找过程中， 找到了值为key的关键字， 则查找成功；如果直到叶子结点也未找到， 则查找失败。

Result SearchBTree(BTree T,KeyType key) { // 在 m 阶 B-树 T 上查找关键字 key, 返回结果(pt,i, tag) // 若查找成功，则特征值 tag=1, 指针 pt 所指结点中第i 个关键字等于 key // 否则特征值 tag=O, 等于 key 的关键字应插入在指针 pt 所指结点中第 1 和第i+1 个关键字之间 p=T;q=NULL;found=FALSE;i=O; // 初始化， p 指向待查结点， q 指向 p 的双亲 while (p&& !found) { i=Search(p,key); // 在 p-> key [ 1 .. keynum]中查找 i, 使得： p->key[i] <=keykey[i+1] if(i>O&&p->key[i]==k) found=TRUE; // 找到待查关键字 else{q=p; p=p->ptr[i];} } if (found) return (p, i, 1); // 查找成功 else return(q,i,0); // 查找不成功，返回K的插人位置信息}

B-树的插入

Status InsertBTree(BTree &T,KeyType K,BTree q,int i) { // 在m阶B-树T上结点*q的key[i] 与 key[i+1]之间插人关键字k // 若引起结点过大， 则沿双亲链进行必要的结点分裂调整 ， 使T仍是m阶B-树 x=K;ap=NULL;finished=FALSE; // x表示新插入的关键字， ap 为一个空指针 while (q&& !finished) { Insert(q,i,x,ap); // 将x和ap分别插入到q->key[i+1]和q->ptr[i+1] if (q->keynumkey[s]; // 将 q->key[ s+ 1. . m] , q->ptr [ s .. rn]和q->recptr[ s+ 1. . m]移入新结点*ap q=q->parent; if(q) i=Search(q, x); // 在双亲结点*q 中查找 x的插入位置 } } if (!finished) // T是空树（参数q初值为NULL)或者根结点已分裂为结点*q和*ap NewRoot(T,q,x,ap); // 生成含信息(T,x,ap)的新的根结点*T, 原T和ap为子树指针 return OK; }

B-树的删除

m阶B-树的删除操作是在B-树的某个结点中删除指定的关键字及其邻近的一个指针， 删除后应该进行调整使该树仍然满足B-树的定义， 也就是要保证每个结点的关键字数目范围为[ [m/2] -1 , m ]。删除记录后， 结点的关键字个数如果小于[m/2]-1, 则要进行 “合并“ 结点的操作。除了删除记录， 还要删除该记录邻近的指针。若该结点为最下层的非终端结点， 由于其指针均为空， 删除后不会影响其他结点， 可直接删除；若该结点不是最下层的非终端结点， 邻近的指针则指向一棵子树， 不可直接删除。此时可做如下处理：将要删除记录用其右（左）边邻近指针指向的子树中关键字最小（大）的记录（该记录必定在最下层的非终端结点中）替换。采取这种方法进行处理， 无论要删除的记录所在的结点是否为最下层的非终端结点， 都可归结为在最下层的非终端结点中删除记录的情况。

B+树

B+ 树是一种 B-树的变形树，更适合用于文件索引系统。

B+ 树和B-树的差异

一棵m阶的 B+ 树和m阶的 B-树的差异在于： （1）有n棵子树的结点中含有n个关键字； （2）所有的叶子结点中包含了全部关键字的信息，以及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接； （3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。

B+树的查找

若非终端结点上的关键字等于给定值， 并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。B+树查找的分析类似于B-树。

B+树不仅能够有效地查找单个关键字，而且更适合查找某个范围内的所有关键字。例如，在B+树上找出范围在[a, b]之间的所有关键字值。 处理方法如下：通过一次查找找出关键字 a, 不管它是否存在，都可以到达可能出现a的叶子结点，然后在叶子结点中查找关键字值等于a或大于a的那些关键字，对千所找到的每个关键字都有一个指针指向相应的记录，这些记录的关键字在所需要的范围。 如果在当前结点中没有发现大于b的关键字，就可以使用当前叶子结点的最后一个指针找到下一个叶子结点，并继续进行同样的处理，直至在某个叶子结点中找到大于b的关键字，才停止查找。

B+树的插入

仅在叶子结点上进行插入，当结点中的关键字个数大于m时要分裂成两个结点，它们所含关键字的个数分别为[(m+1)/2] 和 [(m+1)/2]并且，它们的双亲结点中应同时包含这两个结点中的最大关键字。

B+树的删除

B+树的删除也仅在叶子结点进行，当叶子结点中最大关键字被删除时，其 在非终端结点中的值可以作为一个 “分界关键字“ 存在。若因删除 而使结点中关键字的个数少于「m/2]时，其和兄弟结点的合 并过程亦和B-树类似。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。