當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

B-树的操作

發布時間：2024/9/30 编程问答 23 豆豆

生活随笔收集整理的這篇文章主要介紹了 B-树的操作小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

http://blog.163.com/zhoumhan_0351/blog/static/39954227200910231032917/

前面討論的查找都是內查詢算法，被查詢的數據都在內存。當查詢的數據放在外存，用平衡二叉樹作磁盤文件的索引組織時，若以結點為內外存交換的單位，則找到需要的關鍵字之前，平均要進行lgn次磁盤讀操作，而磁盤、光盤的讀寫時間要比隨機存取的內存代價大得多。其二，外存的存取是以“頁”為單位的，一頁的大小通常是1024字節或2048字節。

?針對上述特點，1972年R.Bayer和E.M.Cright提出了一種B-樹的多路平衡查找樹，以適合磁盤等直接存取設備上組織動態查找表。B-樹上算法的執行時間主要由讀、寫磁盤的次數來決定，故一次I/O操作應讀寫盡可能多的信息。因此B-樹的結點規模一般以一個磁盤頁為單位。一個結點包含的關鍵字及其孩子個數取決于磁盤頁的大小。

一、基本概念

B-樹又稱為多路平衡查找樹。

?????????一棵度為m的B-樹稱為m階B_樹。一個結點有k個孩子時，必有k-1個關鍵字才能將子樹中所有關鍵字劃分為k個子集。B-樹中所有結點的孩子結點最大值稱為B-樹的階，通常用m表示。從查找效率考慮，一般要求m≥3。一棵m階的B-樹或者是一棵空樹，或者是滿足下列要求的m叉樹：

（1）根結點或者為葉子，或者至少有兩棵子樹，至多有m棵子樹。

（2）除根結點外，所有非終端結點至少有ceil(m/2)棵子樹，至多有m棵子樹。

（3）所有葉子結點都在樹的同一層上。

（4）每個結點的結構為：

???????（n，A0，K1，A1，K2，A2，…??，Kn，An）

其中，Ki(1≤i≤n)為關鍵字，且Ki<Ki+1(1≤i≤n-1)。

????????Ai(0≤i≤n)為指向子樹根結點的指針。且A_i所指子樹所有結點中的關鍵字均小于K_i+1。An所指子樹中所有結點的關鍵字均大于Kn。

n為結點中關鍵字的個數，滿足ceil(m/2)-1≤n≤m-1。

????????比如，一棵3階B-樹，m=3。它滿足：?

（1）每個結點的孩子個數小于等于3。?

（2）除根結點外，其他結點至少有=2個孩子。?

（3）根結點有兩個孩子結點。?

（4）除根結點外的所有結點的n大于等于=1，小于等于2。?

（5）所有葉結點都在同一層上。
???

二、B-樹查找的算法思想

1、B-樹的查找

B-樹的查找過程：根據給定值查找結點和在結點的關鍵字中進行查找交叉進行。首先從根結點開始重復如下過程：

???????若比結點的第一個關鍵字小，則查找在該結點第一個指針指向的結點進行；若等于結點中某個關鍵字，則查找成功；若在兩個關鍵字之間，則查找在它們之間的指針指向的結點進行；若比該結點所有關鍵字大，則查找在該結點最后一個指針指向的結點進行；若查找已經到達某個葉結點，則說明給定值對應的數據記錄不存在，查找失敗。

2.??B-樹的插入

插入的過程分兩步完成：

???（1）利用前述的B-樹的查找算法查找關鍵字的插入位置。若找到，則說明該關鍵字已經存在，直接返回。否則查找操作必失敗于某個最低層的非終端結點上。

???（2）判斷該結點是否還有空位置。即判斷該結點的關鍵字總數是否滿足n<=m-1。若滿足，則說明該結點還有空位置，直接把關鍵字k插入到該結點的合適位置上。若不滿足，說明該結點己沒有空位置，需要把結點分裂成兩個。

分裂的方法是：生成一新結點。把原結點上的關鍵字和k按升序排序后，從中間位置把關鍵字（不包括中間位置的關鍵字）分成兩部分。左部分所含關鍵字放在舊結點中，右部分所含關鍵字放在新結點中，中間位置的關鍵字連同新結點的存儲位置插入到父結點中。如果父結點的關鍵字個數也超過（m-1），則要再分裂，再往上插。直至這個過程傳到根結點為止。

3、B-樹的刪除

在B-樹上刪除關鍵字k的過程分兩步完成：

???（1）利用前述的B-樹的查找算法找出該關鍵字所在的結點。然后根據?k所在結點是否為葉子結點有不同的處理方法。

???（2）若該結點為非葉結點，且被刪關鍵字為該結點中第i個關鍵字key[i]，則可從指針son[i]所指的子樹中找出最小關鍵字Y，代替key[i]的位置，然后在葉結點中刪去Y。

因此，把在非葉結點刪除關鍵字k的問題就變成了刪除葉子結點中的關鍵字的問題了。

在B-樹葉結點上刪除一個關鍵字的方法是

首先將要刪除的關鍵字?k直接從該葉子結點中刪除。然后根據不同情況分別作相應的處理，共有三種可能情況：

（1）如果被刪關鍵字所在結點的原關鍵字個數n>=ceil(m/2)，說明刪去該關鍵字后該結點仍滿足B-樹的定義。這種情況最為簡單，只需從該結點中直接刪去關鍵字即可。

（2）如果被刪關鍵字所在結點的關鍵字個數n等于ceil(m/2)-1，說明刪去該關鍵字后該結點將不滿足B-樹的定義，需要調整。

調整過程為：如果其左右兄弟結點中有“多余”的關鍵字,即與該結點相鄰的右（左）兄弟結點中的關鍵字數目大于ceil(m/2)-1。則可將右（左）兄弟結點中最小（大）關鍵字上移至雙親結點。而將雙親結點中小（大）于該上移關鍵字的關鍵字下移至被刪關鍵字所在結點中。

（3）如果左右兄弟結點中沒有“多余”的關鍵字，即與該結點相鄰的右（左）兄弟結點中的關鍵字數目均等于ceil(m/2)-1。這種情況比較復雜。需把要刪除關鍵字的結點與其左（或右）兄弟結點以及雙親結點中分割二者的關鍵字合并成一個結點,即在刪除關鍵字后，該結點中剩余的關鍵字加指針，加上雙親結點中的關鍵字K_i一起，合并到A_i（是雙親結點指向該刪除關鍵字結點的左（右）兄弟結點的指針）所指的兄弟結點中去。如果因此使雙親結點中關鍵字個數小于ceil(m/2)-1，則對此雙親結點做同樣處理。以致于可能直到對根結點做這樣的處理而使整個樹減少一層。

總之，設所刪關鍵字為非終端結點中的Ki，則可以指針Ai所指子樹中的最小關鍵字Y代替Ki，然后在相應結點中刪除Y。對任意關鍵字的刪除都可以轉化為對最下層關鍵字的刪除。

如圖示：

a、被刪關鍵字Ki所在結點的關鍵字數目不小于ceil(m/2)，則只需從結點中刪除Ki和相應指針Ai，樹的其它部分不變。

b、被刪關鍵字Ki所在結點的關鍵字數目等于ceil(m/2)-1，則需調整。調整過程如上面所述。

c、被刪關鍵字Ki所在結點和其相鄰兄弟結點中的的關鍵字數目均等于ceil(m/2)-1，假設該結點有右兄弟，且其右兄弟結點地址由其雙親結點指針Ai所指。則在刪除關鍵字之后，它所在結點的剩余關鍵字和指針，加上雙親結點中的關鍵字Ki一起，合并到Ai所指兄弟結點中（若無右兄弟，則合并到左兄弟結點中）。如果因此使雙親結點中的關鍵字數目少于ceil(m/2)-1，則依次類推。

三、B-樹的C語言描述

1、存儲結構

2、插入

3、查找

四、B-樹的C語言實現

#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#define OK 1
#define ERROR -1
#define m 3 //3階樹
#define N 16 //數據元素個數
#define MAX 5 //字符串最大長度＋1
typedef int KeyType;
struct Others? //記錄的其它部分
{
char info[MAX];
};
struct Record
{
KeyType key; //關鍵字
Others others; //其它部分
};
typedef struct BTNode
{
int keynum; //結點中關鍵字個數
BTNode *parent;//指向雙親節點
?? struct Node? //結點向量類型
?? {
?? KeyType key; //關鍵字向量
?? BTNode *ptr;//子樹指針向量
?? Record *recptr; //記錄向量指針
?? }node[m+1]; //key,recptr的0號單元未用
}BTNode,*BTree;
struct Result //B樹的查找結果類型?
{
BTNode *pt; //指向找到的結點
int i; //在節點中關鍵字序號，1...m
int tag; //1表示查找成功，0表示查找失敗。
};

int InitDSTable(BTree &DT)
{
DT=NULL;
return OK;
}//InitDSTable

void DestroyDSTable(BTree &DT)
{
int i;
if(DT) //非空樹
??? {
???? for(i=0;i<=DT->keynum;i++)
?? ???? ?DestroyDSTable(DT->node[i].ptr);
?? ? free(DT);
?? ? DT=NULL;
??? }//if
}//DestroyDSTable

int Search(BTree p,KeyType K)
{//在p->node[1...keytype].key中查找i,使得p->node[i].key<=K<
?? ?//p->node[i+1].key
?? ?int i=0,j;
?? ?for(j=1;j<=p->keynum;j++)
?? ???? if(p->node[j].key<=K)
?? ???? ??? i=j;
?? ?return i;
}//Search

void Insert(BTree &q,int i,Record *r,BTree ap)
{//將r->key、r和ap分別插入到q->key[i+1]、
?? ?//q->recptr[????????????? i+1]和q->ptr[i+1]中
?? ?int j;
?? ?for(j=q->keynum;j>i;j--) //空出q->node[i+1]
?? ? q->node[j+1]=q->node[j];
??? q->node[i+1].key=r->key;
??? q->node[i+1].ptr=ap; //前加入的結點，還沒有兒子結點
??? q->node[i+1].recptr=r;
??? q->keynum++;
}//Insert

void NewRoot(BTree &T,Record *r,BTree ap)
{// 生成含信息(T,r,ap)的新的根結點*T，原T和ap為子樹指針
BTree p;
p=(BTree)malloc(sizeof(BTNode));
p->node[0].ptr=T;
T=p;
if(T->node[0].ptr)
?? ?T->node[0].ptr->parent=T;
T->parent=NULL;
T->keynum=1;
T->node[1].key=r->key;
T->node[1].recptr=r;
T->node[1].ptr=ap;
if(T->node[1].ptr)
?? ?T->node[1].ptr->parent=T;
}//NewRoot

void split(BTree &q,BTree &ap)
{// 將結點q分裂成兩個結點，前一半保留，后一半移入新生結點ap
int i,s=(m+1)/2;
ap=(BTree)malloc(sizeof(BTNode));//生成新結點ap
ap->node[0].ptr=q->node[s].ptr;//原來結點中間位置關鍵字相應指針指向的子樹放到
?????????????????????????????? //新生成結點的0棵子樹中去
for(i=s+1;i<=m;i++) //后一半移入ap
?? {
?? ap->node[i-s]=q->node[i];
?? if(ap->node[i-s].ptr)
?? ??? ap->node[i-s].ptr->parent=ap;
?? }//for
?? ap->keynum=m-s;
?? ap->parent=q->parent;
?? q->keynum=s-1; // q的前一半保留，修改keynum
}//split

void InsertBTree(BTree &T,Record *r,BTree q,int i)
{//在m階B樹T上結點*q的key[i]與key[i+1]之間插入關鍵字K的指針r。若引起
?? // 結點過大,則沿雙親鏈進行必要的結點分裂調整,使T仍是m階B樹。
BTree ap=NULL;
int finished=false;
int s;
Record *rx;
rx=r;
while(q&&!finished)
?? {
??? Insert(q,i,rx,ap);//將r->key、r和ap分別插入到q->key[i+1]、
?? ?????????????????? //q->recptr[i+1]和q->ptr[i+1]中
?? ?if(q->keynum<m)
?? ???? finished=true;
?? ?else
?? ?? {//分裂結點*q
????? s=(m+1)/2;
?? ?? rx=q->node[s].recptr;
?? ?? split(q,ap);//將q->key[s+1..m],q->ptr[s..m]和q->recptr[s+1..m]
?? ???? ??? ??? ? //移入新結點*ap
?? ?? q=q->parent;
?? ?? if(q)
?? ???? ? i=Search(q,rx->key);//在雙親結點*q中查找rx->key的插入位置
?? ?? }//else
?? }//while
if(!finished) //T是空樹(參數q初值為NULL)或根結點已分裂為
?? ?????????? //結點*q和*ap
NewRoot(T,rx,ap);?? ?
}//InsertBTree

Result SearchBTree(BTree T,KeyType K)
{// 在m階B樹T上查找關鍵字K，返回結果(pt,i,tag)。若查找成功，則特征值
// tag=1，指針pt所指結點中第i個關鍵字等于K；否則特征值tag=0，等于K的
// 關鍵字應插入在指針Pt所指結點中第i和第i+1個關鍵字之間。
BTree p=T,q=NULL; //初始化，p指向待查結點，q指向p的雙親
int found=false;
int i=0;
Result r;
while(p&&!found)
?? {
?? i=Search(p,K);//p->node[i].key≤K<p->node[i+1].key
?? if(i>0&&p->node[i].key==K)
?? ??? found=true;
?? else?
???? {
???? q=p;
?? ? p=p->node[i].ptr;//在子樹中繼續查找
?? ? }//else
??? }//while
?? r.i=i;
?? if(found)
???? {
????? r.pt=p;
?? ?? r.tag=1;
???? }//if
?? else?
????? {
?????? r.pt=q;
?? ??? r.tag=0;
????? }//else
??? return r;
}//SearchBTree

void print(BTNode c,int i) // TraverseDSTable()調用的函數
?{
?? printf("(%d,%s)",c.node[i].key,c.node[i].recptr->others.info);
?}//print
void TraverseDSTable(BTree DT,void(*Visit)(BTNode,int))
{// 初始條件: 動態查找表DT存在，Visit是對結點操作的應用函數
// 操作結果: 按關鍵字的順序對DT的每個結點調用函數Visit()一次且至多一次
int i;
if(DT) //非空樹
??? {
????? if(DT->node[0].ptr) // 有第0棵子樹
???????? TraverseDSTable(DT->node[0].ptr,Visit);
????? for(i=1;i<=DT->keynum;i++)
??????? {
???????? Visit(*DT,i);
???????? if(DT->node[i].ptr) // 有第i棵子樹
???????? TraverseDSTable(DT->node[i].ptr,Visit);
??????? }//for
??? }//if
}//TraverseDSTable

void InputBR(BTree &t,Record r[])
{
Result s;?? ?
for(int i=0;i<N;i++)
?? {
???? s=SearchBTree(t,r[i].key);
???? if(!s.tag)
?????? InsertBTree(t,&r[i],s.pt,s.i);
?? }
}//InputBR
void UserSearch(BTree t)
{
int i;
Result s;
printf("\n請輸入待查找記錄的關鍵字: ");
scanf("%d",&i);
s=SearchBTree(t,i);
if(s.tag)
print(*(s.pt),s.i);
else
printf("沒找到");
printf("\n");
}//UserSearch
void DeleteIt(BTree t,BTNode *dnode,int id)
{
if(dnode->keynum>=ceil(m/2))
?? {
??? dnode->keynum--;
?? ?dnode->node[id].ptr=NULL;
?? }//if被刪關鍵字Ki所在結點的關鍵字數目不小于ceil(m/2)，則只需從結點中刪除Ki和相應指針Ai，樹的其它部分不變。
else if((dnode->keynum==(ceil(m/2)-1))&&((id+1)<(m-1))&&dnode->parent->node[id+1].ptr->keynum>(ceil(m/2)-1))
?? {
??? for(int i=1;i<m&&dnode->parent->node[i].key < dnode->parent->node[id+1].ptr->node[1].key;i++)
?? ???? dnode->node[i].key=dnode->parent->node[i].key;
?? ?dnode->parent->node[1].key=dnode->parent->node[id+1].ptr->node[1].key;
?? ?(dnode->parent->node[id+1].ptr->keynum)--;
?? }//else if 被刪關鍵字Ki所在結點的關鍵字數目等于ceil(m/2)-1，則需調整。本次為與右兄弟調整
else if((dnode->keynum==(ceil(m/2)-1))&&((id-1)>0??? )&&dnode->parent->node[id-1].ptr->keynum>(ceil(m/2)-1))
?? {
??? for(int i=1;i<m&&dnode->parent->node[i].key > dnode->parent->node[id-1].ptr->node[dnode->parent->node[id-1].ptr->keynum].key;i++)
?? ???? dnode->node[i].key=dnode->parent->node[i].key;
?? ?dnode->parent->node[1].key=dnode->parent->node[id-1].ptr->node[dnode->parent->node[id-1].ptr->keynum].key;
?? ?(dnode->parent->node[id-1].ptr->keynum)--;
?? }//2-else if被刪關鍵字Ki所在結點的關鍵字數目等于ceil(m/2)-1，則需調整。本次為與左兄弟調整
else if((dnode->keynum==(ceil(m/2)-1))&&((id+1)<(m-1))&&dnode->parent->node[id+1].ptr->keynum==(ceil(m/2)-1))
?? {
??? do
?? ?? {
?? ???? BTree tmp;
?? ???? tmp=dnode;
?? ??? dnode->parent->node[id+1].ptr->node[2]=dnode->parent->node[id+1].ptr->node[1];
?? ??? dnode->parent->node[id+1].ptr->node[1]=dnode->parent->node[1];
?? ??? dnode->parent->node[id+1].ptr->keynum++;
?? ??? dnode->parent->node[id+1].ptr->node[0].ptr=dnode->node[1].ptr;
?? ??? dnode->parent->keynum--;
?? ??? dnode->parent->node[id].ptr=NULL;
?? ??? tmp=dnode;
?? ??? if(dnode->parent->keynum>=(ceil(m/2)-1))
?? ???? ?? dnode->parent->node[1]=dnode->parent->node[2];
?? ??? dnode=dnode->parent;
?? ??? free(tmp);
?? ?? }while(dnode->keynum<(ceil(m/2)-1));??? //雙親中keynum<
?? }//3-else if被刪關鍵字Ki所在結點和其相鄰兄弟結點中的的關鍵字數目均等于ceil(m/2)-1，本次假設右兄弟存在?
else if((dnode->keynum==(ceil(m/2)-1))&&(id-1)>0????? &&dnode->parent->node[id-1].ptr->keynum==(ceil(m/2)-1))
?? {
??? do
?? ?? {
?? ???? BTree tmp;
?? ???? tmp=dnode;
?? ??? dnode->parent->node[id-1].ptr->node[2]=dnode->parent->node[id-1].ptr->node[1];
?? ??? dnode->parent->node[id-1].ptr->node[1]=dnode->parent->node[1];
?? ??? dnode->parent->node[id-1].ptr->keynum++;
?? ??? dnode->parent->node[id-1].ptr->node[0].ptr=dnode->node[1].ptr;
?? ??? dnode->parent->keynum--;
?? ??? dnode->parent->node[id].ptr=NULL;
?? ??? tmp=dnode;
?? ??? if(dnode->parent->keynum>=(ceil(m/2)-1))
?? ???? ?? dnode->parent->node[1]=dnode->parent->node[2];
?? ??? dnode=dnode->parent;
?? ??? free(tmp);
?? ?? }while(dnode->keynum<(ceil(m/2)-1)); //雙親中keynum<
?? }//4-else if被刪關鍵字Ki所在結點和其相鄰兄弟結點中的的關鍵字數目均等于ceil(m/2)-1，本次假設左兄弟存在?
?? ?else printf("Error!"); //出現異常
}//DeleteIt
void UserDelete(BTree t)
{
KeyType date;
Result s;
printf("Please input the date you want to delete:\n");
scanf("%d",&date);
s=SearchBTree(t,date);
if(!s.tag)? printf("Search failed,no such date\n");
else DeleteIt(t,s.pt,s.i);
}//UserDelete

int main()
{
Record r[N]={{24,"1"},{45,"2"},{53,"3"},{12,"4"},{37,"5"},
?? ???? {50,"6"},{61,"7"},{90,"8"},{100,"9"},{70,"10"},
?? ???? {3,"11"},{30,"12"},{26,"13"},{85,"14"},{3,"15"},
?? ???? {7,"16"}};?? ?
BTree t;
InitDSTable(t);
InputBR(t,r);
printf("按關鍵字的順序遍歷B_樹:\n");
TraverseDSTable(t,print);
UserSearch(t);
UserDelete(t);
TraverseDSTable(t,print);
DestroyDSTable(t);
return 1;
}

五、復雜度分析

B-樹查找包含兩種基本動作：

?????●在B-樹上查找結點

?????●在結點中找關鍵字

前一操作在磁盤上進行，后一操作在內存進行。因此查找效率主要由前一操作決定。在磁盤上查找的次數取決于關鍵字結點在B-樹上的層次數。

定理：若n≥1，m≥3，則對任意一棵具有n個關鍵字的m階B-樹，其樹高度h至多為log_t((n+1)/2)+1，t= ceil(m/2)。也就是說根結點到關鍵字所在結點的路徑上涉及的結點數不超過log_t((n+1)/2)+1。推理如下：

總結

以上是生活随笔為你收集整理的B-树的操作的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

操作

上一篇：系统抖动
下一篇：编程之美---小飞的电梯调度问题 1.8