B-樹

B-tree樹即B樹，B即Balanced，平衡的意思，B-樹又稱為多路平衡查找樹。因為B樹的原英文名稱為B-tree，而國内很多人喜歡把B-tree譯作B-樹，其實，這是個非常不好的直譯，很容易讓人産生誤解。如人們可能會以為B-樹是一種樹，而B樹又是另一種樹。而事實上是，B-tree就是指的B樹。

一、定義

B-樹是一種多路搜尋樹（并不一定是二叉的）

1970年，R.Bayer和E.mccreight提出了一種适用于外查找的樹，它是一種平衡的多叉樹，稱為B樹（或B-樹、B_樹）。一棵m階B樹(balanced tree of order m)是一棵平衡的m路搜尋樹。它或者是空樹，或者是滿足下列性質的樹：

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

1、根結點至少有兩個子女； 2、每個非根節點所包含的關鍵字個數 j 滿足：┌m/2┐ - 1 <= j <= m - 1； 3、除根結點以外的所有結點（不包括葉子結點）的度數正好是關鍵字總數加1，故内部子樹個數 k 滿足：┌m/2┐ <= k <= m ； 4、所有的葉子結點都位于同一層。在B-樹中，每個結點中關鍵字從小到大排列，并且當該結點的孩子是非葉子結點時，該k-1個關鍵字正好是k個孩子包含的關鍵字的值域的分劃。因為葉子結點不包含關鍵字，是以可以把葉子結點看成在樹裡實際上并不存在外部結點，指向這些外部結點的指針為空，葉子結點的數目正好等于樹中所包含的關鍵字總個數加1。 B-樹中的一個包含n個關鍵字，n+1個指針的結點的一般形式為：（n,P0,K1,P1,K2,P2,…,Kn,Pn）其中，Ki為關鍵字，K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之間的關鍵字的子樹的指針。

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

二、概念

M為樹的階數，B-樹或為空樹，否則滿足下列條件：

定義任意非葉子結點最多隻有M個兒子；且M>2；

2. 根結點的兒子數為[2, M]； 3.除根結點以外的非葉子結點的兒子數為[M/2, M]； 4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字,根節點至少一個關鍵字）； 5.非葉子結點的關鍵字個數=指向兒子的指針個數-1； 6.非葉子結點的關鍵字：K[1], K[2], …, K[m-1]，m<M+1；且K [i]< K[i+1] ； 7.非葉子結點的指針：P[1], P[2], …, P[m]；其中P[1]指向關鍵字小于K[1]的子樹，P[m]指向關鍵字大于K[m-1]的子樹，其它P[i]指向關鍵字屬于(K[i-1], K[i])的子樹； 8.所有葉子結點位于同一層；如：（M=3）

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

M=3的B-樹 B-樹的搜尋，從根結點開始，對結點内的關鍵字（有序）序列進行二分查找，如果命中則結束，否則進入查詢關鍵字所屬範圍的兒子結點；重複，直到所對應的兒子指針為空，或已經是葉子結點。

三、特性

1.關鍵字集合分布在整顆樹中； 2.任何一個關鍵字出現且隻出現在一個結點中； 3.搜尋有可能在非葉子結點結束； 4.其搜尋性能等價于在關鍵字全集内做一次二分查找； 5.自動層次控制；由于限制了除根結點以外的非葉子結點，至少含有M/2個兒子，確定了結點的至少使用率，其最底搜尋性能為：其中，M為設定的非葉子結點最多子樹個數，N為關鍵字總數；是以B-樹的性能總是等價于二分查找（與M值無關），也就沒有B樹平衡的問題；由于M/2的限制，在插入結點時，如果結點已滿，需要将結點分裂為兩個各占M/2的結點；删除結點時，需将兩個不足M/2的兄弟節點合并.

(1)根結點隻有1個，關鍵字字數的範圍[1,m-1]，分支數量範圍[2,m]；

(2)除根以外的非葉結點，每個結點包含分支數範圍[[m/2],m]，即關鍵字字數的範圍是[[m/2]-1,m-1]，其中[m/2]表示取大于m/2的最小整數；

(3)非葉結點是由葉結點分裂而來的，是以葉結點關鍵字個數也滿足[[m/2]-1,m-1]；

四、B樹查找的算法思想

1、B-樹的查找

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

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

2. B-樹的插入

插入的過程分兩步完成：

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

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

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

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

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。這種情況比較複雜。需把要删除關鍵字的結點與其左（或右）兄弟結點以及雙親結點中分割二者的關鍵字合并成一個結點,即在删除關鍵字後，該結點中剩餘的關鍵字加指針，加上雙親結點中的關鍵字Ki一起，合并到Ai（是雙親結點指向該删除關鍵字結點的左（右）兄弟結點的指針）所指的兄弟結點中去。如果是以使雙親結點中關鍵字個數小于ceil(m/2)-1，則對此雙親結點做同樣處理。以緻于可能直到對根結點做這樣的處理而使整個樹減少一層。

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

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

如圖示：

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

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

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

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

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

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

五、B-樹的C語言描述

1、存儲結構

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

2、插入

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

3、查找

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

六、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))

{

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))

{

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至多為logt((n+1)/2)+1，t= ceil(m/2)。也就是說根結點到關鍵字所在結點的路徑上涉及的結點數不超過logt((n+1)/2)+1。推理如下：

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

B+樹

B+ 樹是一種樹資料結構，是一個n叉樹，每個節點通常有多個孩子，一顆B+樹包含根節點、内部節點和葉子節點。根節點可能是一個葉子節點，也可能是一個包含兩個或兩個以上孩子節點的節點。

一、定義

B+樹是應檔案系統所需而出的一種B-樹的變型樹。一棵m階的B+樹和m階的B-樹的差異在于： 1.有n棵子樹的結點中含有n個關鍵字，每個關鍵字不儲存資料，隻用來索引，所有資料都儲存在葉子節點。 2.所有的葉子結點中包含了全部關鍵字的資訊，及指向含這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大順序連結。 3.所有的非終端結點可以看成是索引部分，結點中僅含其子樹（根結點）中的最大（或最小）關鍵字。

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

通常在B+樹上有兩個頭指針，一個指向根結點，一個指向關鍵字最小的葉子結點。

二、B+樹的查找、插入和删除

B+樹的查找

對B+樹可以進行兩種查找運算： 1.從最小關鍵字起順序查找； 2.從根結點開始，進行随機查找。在查找時，若非終端結點上的關鍵值等于給定值，并不終止，而是繼續向下直到葉子結點。是以，在B+樹中，不管查找成功與否，每次查找都是走了一條從根到葉子結點的路徑。其餘同B-樹的查找類似。以下是從根節點查找葉子節點k的僞代碼：

1 2 3 4 5 6 7 8 9 10

Function: search (k)

return

tree_search (k, root); Function: tree_search (k, node)

if

node is a leaf then

return

node;

switch

do

case

k < k_0

return

tree_search(k, p_0);

case

k_i ≤ k < k_{i+

return

tree_search(k, p_{i+

});

case

k_d ≤ k

return

tree_search(k, p_{d+

});

//僞代碼假設沒有重複值

B+樹的插入

m階B樹的插入操作在葉子結點上進行，假設要插入關鍵值a，找到葉子結點後插入a，做如下算法判别： ①如果目前結點是根結點并且插入後結點關鍵字數目小于等于m，則算法結束； ②如果目前結點是非根結點并且插入後結點關鍵字數目小于等于m，則判斷若a是新索引值時轉步驟④後結束，若a不是新索引值則直接結束； ③如果插入後關鍵字數目大于m(階數)，則結點先分裂成兩個結點X和Y，并且他們各自所含的關鍵字個數分别為：u=大于(m+1)/2的最小整數，v=小于(m+1)/2的最大整數；由于索引值位于結點的最左端或者最右端，不妨假設索引值位于結點最右端，有如下操作：如果目前分裂成的X和Y結點原來所屬的結點是根結點，則從X和Y中取出索引的關鍵字，将這兩個關鍵字組成新的根結點，并且這個根結點指向X和Y，算法結束；如果目前分裂成的X和Y結點原來所屬的結點是非根結點，依據假設條件判斷，如果a成為Y的新索引值，則轉步驟④得到Y的雙親結點P，如果a不是Y結點的新索引值，則求出X和Y結點的雙親結點P；然後提取X結點中的新索引值a’，在P中插入關鍵字a’，從P開始，繼續進行插入算法； ④提取結點原來的索引值b，自頂向下，先判斷根是否含有b，是則需要先将b替換為a，然後從根結點開始，記錄結點位址P，判斷P的孩子是否含有索引值b而不含有索引值a，是則先将孩子結點中的b替換為a，然後将P的孩子的位址指派給P，繼續搜尋，直到發現P的孩子中已經含有a值時，停止搜尋，傳回位址P。

B+樹的删除

B+樹的删除也僅在葉子結點進行，當葉子結點中的最大關鍵字被删除時，其在非終端結點中的值可以作為一個“分界關鍵字”存在。若因删除而使結點中關鍵字的個數少于m/2 （m/2結果取上界，如5/2結果為3）時，其和兄弟結點的合并過程亦和B-樹類似。

三、B+樹與B樹的差別

一棵m階的B+樹和m階的B樹的異同點在于：

所有的葉子結點中包含了全部關鍵字的資訊，及指向含有這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大的順序連結。(而B 樹的葉子節點并沒有包括全部需要查找的資訊)
所有的非終端結點可以看成是索引部分，結點中僅含有其子樹根結點中最大（或最小）關鍵字。(而B 樹的非終節點也包含需要查找的有效資訊)

四、B+樹與作業系統的檔案索引和資料庫索引

為什麼說B+樹比B 樹更适合實際應用中作業系統的檔案索引和資料庫索引？

B+樹的磁盤讀寫代價更低

B+樹的内部結點并沒有指向關鍵字具體資訊的指針。是以其内部結點相對B 樹更小。如果把所有同一内部結點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多。一次性讀入記憶體中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。舉個例子，假設磁盤中的一個盤塊容納16bytes，而一個關鍵字2bytes，一個關鍵字具體資訊指針2bytes。一棵9階 B-tree(一個結點最多8個關鍵字)的内部結點需要2個盤快。而B+樹内部結點隻需要1個盤快。當需要把内部結點讀入記憶體中的時候，B 樹就比B+樹多一次盤塊查找時間(在磁盤中就是盤片旋轉的時間)。
B+樹的查詢效率更加穩定由于非終結點并不是最終指向檔案内容的結點，而隻是葉子結點中關鍵字的索引。是以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導緻每一個資料的查詢效率相當。

紅黑樹

紅黑樹（Red Black Tree）是一種自平衡二叉查找樹，是在計算機科學中用到的一種資料結構，典型的用途是實作關聯數組。它是在1972年由Rudolf Bayer發明的，當時被稱為平衡二叉B樹（symmetric binary B-trees）。後來，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的“紅黑樹”。紅黑樹和AVL樹類似，都是在進行插入和删除操作時通過特定操作保持二叉查找樹的平衡，進而獲得較高的查找性能。它雖然是複雜的，但它的最壞情況運作時間也是非常良好的，并且在實踐中是高效的：它可以在O(log n)時間内做查找，插入和删除，這裡的n 是樹中元素的數目。

一、性質

紅黑樹是每個節點都帶有顔色屬性的二叉查找樹，顔色或紅色或黑色。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求: 性質1. 節點是紅色或黑色。性質2. 根節點是黑色。性質3 每個葉節點（NIL節點，空節點）是黑色的。性質4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點) 性質5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。這些限制強制了紅黑樹的關鍵性質: 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結果是這個樹大緻上是平衡的。因為操作比如插入、删除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。要知道為什麼這些特性確定了這個結果，注意到性質4導緻了路徑不能有兩個毗連的紅色節點就足夠了。最短的可能路徑都是黑色節點，最長的可能路徑有交替的紅色和黑色節點。因為根據性質5所有最長的路徑都有相同數目的黑色節點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。在很多樹資料結構的表示中，一個節點有可能隻有一個子節點，而葉子節點不包含資料。用這種範例表示紅黑樹是可能的，但是這會改變一些屬性并使算法複雜。為此，本ul 文中我們使用 "nil 葉子" 或"空(n l)葉子"，如上圖所示，它不包含資料而隻充當樹在此結束的訓示。這些節點在繪圖中經常被省略，導緻了這些樹好象同上述原則相沖突，而實際上不是這樣。與此有關的結論是所有節點都有兩個子節點，盡管其中的一個或兩個可能是空葉子。注意：由于紅黑樹也是二叉查找樹，它們當中每一個節點的比較值都必須大于或等于在它的左子樹中的所有節點，并且小于或等于在它的右子樹中的所有節點。這確定紅黑樹運作時能夠快速的在樹中查找給定的值。

二. 資料結構定義

RBT資料結構在基本二叉樹資料結構之上增加一個color和parent，color用于儲存節點顔色，parent指向父節點。

[cpp] view plain copy print ?

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

#define COLOR_RED 0
#define COLOR_BLACK 1
typedef int keyType;
// 定義而二叉樹節點資料結構
struct BinaryTreeNode {
keyType key;
int color;
BinaryTreeNode* parent; // 儲存父節點
BinaryTreeNode* left; // left child
BinaryTreeNode* right; // right child
};
// define red-black tree node
typedef BinaryTreeNode rbnode;
// define red-black tree
typedef BinaryTreeNode rbtree;

三、插入Key

無論怎麼樣操作，性質1和性質3是始終能夠保持的。新插入節點的時候，新節點的初始顔色為紅色，這樣可以不直接破壞性質5，這個時候可能性質4受到威脅，需要調整節點顔色或這左一些旋轉等操作。假設新插入的節點為N，其父節點為P，祖父節點為G，叔父節點為U，下面具體分析一下插入新節點的各種情況。

情形1 、空樹

當樹為空的時候，直接将N節點設為黑色作為樹的根節點傳回。

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

情形2 、P為黑色節點

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

圖中所示為N插入到P左孩子節點中，這個過程完全滿足性質 1 - 5 的要求，并沒有破壞 RBT 的規則，是以，此時即可停止檢查，插入過程結束。

同理，若P為黑色節點，N插入後作為P的右孩子節點也不會破壞 RBT的規則。

（下面開始讨論 P 為紅色的情形，由性質2 推導出 G 一定存在，根據性質 4，G一定是黑色）

情形3 、P為紅色節點，U存在且為紅色節點

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

這種情況下，将G變為紅色，P和U變為黑色，這樣維持了G為Root的子樹内性質4和5，然後以G作為新的插入節點，從情形1開始疊代。

情形4 、P為紅色節點，U不存在或者U為黑色

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key	（a）若P在G的左側，插入點N也在P的左側 ------ LL 型假設G的右側有路徑有 x個黑色節點，則c有x個黑色節點，G為root的子樹路徑有x+1個黑色節點。此時，隻需要以P為中心右旋，将P變為黑色，G變為紅色，G的左子樹替換為c，這樣就可以繼續保證以P為root的子樹有x+1個黑色節點，檢查停止。
B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key	（b）若P在G的左側，N在P的右側 -----LR型這時候先将節點P和節點N做調整，進行左旋，變化成（a）的形态，然後做一次右旋。到此，調整完畢。
圖略	（c）若P在G的右側，N在P的右側 ----------RR型情形和（a）正好相反，做一次左旋即可。
圖略	（d）若P在G的右側，N在P的左側 ----------RL型情形和（b）正好相反，先做做一次右旋，後進行一次左旋即可。

RBT插入算法過程代碼如下：

[cpp] view plain copy print ?

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

// 向右旋轉
void rb_right_rotate(rbnode* g) {
rbnode * p = g->left;
keyType k = g->key;
g->key = p->key;
p->key = k;
g->left = p->left;
if (NULL != p->left) {
p->left->parent = g;
}
p->left = p->right;
p->right = g->right;
if (NULL != g->right) {
g->right->parent = p;
}
g->right = p;
}
// 向左旋轉
void rb_left_rotate(rbnode* g) {
rbnode* p = g->right;
keyType k = g->key;
g->key = p->key;
p->key = k;
g->right = p->right;
if (NULL != p->right) {
p->right->parent = g;
}
p->right = p->left;
p->left = g->left;
if (NULL != g->left) {
g->left->parent = p;
}
g->left = p;
}
// check and adjust after insertion
void rbt_insert_check(rbnode* node) {
// CASE 1 : if the node equals the root
// set the color of the node black and return.
if (NULL == node->parent) {
node->color = COLOR_BLACK;
return;
}
// CASE 2 : when the parent of the node is black
// All features have been met, stop check and return
if (node->parent->color == COLOR_BLACK) {
return;
}
// Otherwise, the the parent node is RED, and this means the grandfather node exists.
rbnode* gf = node->parent->parent;
rbnode* uf = (gf->left == node->parent) ? gf->right : gf->left;
// CASE 3 : When the uncle node exists and it's RED
if (NULL != uf && uf->color == COLOR_RED) {
// set parent and uncle black, set grandfather red
node->parent->color = COLOR_BLACK;
uf->color = COLOR_BLACK;
gf->color = COLOR_RED;
// then re check the tree at grandfather node from CASE 1.
rbt_insert_check(gf);
return;
}
// CASE 4 : when the uncle is NULL or its color is Black.
if (node->parent == gf->left) { // the node in the left of its grandfather
// (a) LL model
if (node == node->parent->left) { // the node in the left of its parent
rb_right_rotate(gf);
}
// (b) LR model
else if (node == node->parent->right) { //the node in the right of its parent.
rb_left_rotate(node->parent);
rb_right_rotate(gf);
}
} else if (node->parent == gf->right) { //the node in the right of its grandfather
// (c) RR model
if (node == node->parent->right) { //the node in the right of its parent.
rb_left_rotate(gf);
}
// (d) RL model
else if (node == node->parent->left) { //the node in the left of its parent.
rb_right_rotate(node->parent);
rb_left_rotate(gf);
}
}
}
// 插入新的關鍵字
int rbt_insert(rbtree* &tree, keyType key) {
if (NULL == tree) { // if the tree is NULL
tree = (rbtree*) malloc((sizeof(rbnode)));
tree->key = key;
tree->color = COLOR_BLACK;
tree->parent = tree->left = tree->right = NULL;
return 1;
}
// find insert point
rbnode *n = tree, *p = tree->parent;
while (NULL != n) {
if (key == n->key) {
return 0;
}
p = n;
n = (key > p->key) ? p->right : p->left;
}
// insert the node
n = (rbtree*) malloc((sizeof(rbnode)));
n->key = key;
n->color = COLOR_RED;
n->parent = p;
n->right = n->left = NULL;
((key > p->key) ? p->right : p->left) = n;
// adjust the tree
rbt_insert_check(n);
return 1;
}

四、删除Key

從RBT中删除指定的Key時，需要重新調整樹的形态使之滿足紅黑樹的特性。下面來具體分析一下删除Key的過程。

（1）根據key找到要删除的節點Node：如果沒有找到，直接傳回，否則，進行下一步操作；

（2）如果Node有兩個孩子節點，那麼删除Node之後該如何放置其孩子節點呢？

這個時候需要進行預處理，轉化為删除隻有一個孩子的節點的情形。

找到Node的中序前驅（後繼）節點，将前驅（後繼）節點的值複制到Node中，Node指向前驅（後繼）節點；

（3）到此步驟，Node确切的訓示為待删除的節點，且Node最多隻有一個孩子節點。

删除Node節點，将Node的孩子節點頂替Node的位置.（注意Node為Root的情形）

（4）調整RBT樹使其滿足規定的5大特性。

假設上一步中頂替上來的節點為 N ，其父節點為 P ，其兄弟節點為 S ，Sl 和 Sr 分别為 S 的左右孩子節點，假設 N 在 P 的左側，調整過程如下：

（右側與左側對稱，這裡分析一種即可）

情形1 、N節點為紅色

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

當N節點為紅色的時候，由于左側缺少一個黑色的節點，可以将N節點的顔色修改為黑色，這樣即可從新滿足性質5.

調整完畢。

情形2、S節點為紅色

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

當S節點為紅色節點時，則可以将P節點向左旋轉，旋轉之後P為紅色，S為黑色，這個時候S-Sl這條簡單路徑黑色節點數目合法，S-P-Sl節點數目也合法，S-P-N路徑黑色節點數目少一個。

相當于，P的左側删除了一個黑色節點，應當重新調整 P，S，Sl，Sr所指向的節點，進行後續操作。

後續可能的情形為：3，5，6

情形3、P節點為紅色，S，Sl，Sr為黑色

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

當P為紅色，S為黑色，Sl和Sr均為黑色的時候，則可以簡單的交換P節點和S節點的顔色，這樣即可使各條簡單路徑的黑色節點數目和删除節點前相等。

調整完畢。

情形4、P，S，Sl，Sr均為黑色

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

當P、S、Sl、Sr均為黑色節點的時候，隻需要簡單的将S節點标記為紅色，這樣以P節點為根的個簡單路徑黑色節點數目比删除之前少一個。

是以，P相當與N的位置，從P的父節點開始遞歸進行調整。

（如果此時P為樹的根節點，即可停止調整）

情形5、Sl為紅色節點并且Sr為黑色

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

這種情況下，可以将Sl進行右旋操作，右旋之後，Sl為黑色，S為紅色，Sr不變，這樣保持P節點右子樹中各簡單路徑黑色節點數目和旋轉前一樣。

這個時候，原來的S相當于Sl的位置，Sl相當與a，Sr相當與S。

更新S，Sl，Sr新指向的位置，進行下一步操作。

後續情形為：6.

情形6、Sr為紅色

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

這時，将P節點做一次左旋操作，将Sr的顔色設定為黑色，P和S交換顔色，調整之後，各簡單路徑的黑色節點數目和删除節點之前一樣。

此時調整結束。

[cpp] view plain copy print ?

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

int is_black(rbnode * node) {
if (node == NULL) return 1;
if (node->color == COLOR_BLACK) return 1;
return 0;
}
// check and adjust after deletion
void rbt_delete_check(rbnode* p, bool delLeft) {
rbnode * n = delLeft ? p->left : p->right;
// case 1: n is red
if (NULL != n && n->color == COLOR_RED) {
n->color = COLOR_BLACK;
return;
}
// else the other subtree of p at least has one more node.
rbnode * s = delLeft ? p->right : p->left;
rbnode * sl = s->left;
rbnode * sr = s->right;
// case 2 : S is red , p left rotate
if (s->color == COLOR_RED) {
if (delLeft) {
rb_left_rotate(p);
} else {
rb_right_rotate(p);
}
p = s;
s = delLeft ? sl : sr;
sl = s->left;
sr = s->right;
}
// Other cases : S is black
// when SL and SR are black
if (is_black(sl) && is_black(sr)) {
// case 3 : P is red, S SL and SR are black
if (!is_black(p)) {
p->color = COLOR_BLACK;
s->color = COLOR_RED;
}
// case 4: P ,S, SL and SR are black
else {
s->color = COLOR_RED;
if (NULL == p->parent) {
return;
}
delLeft = (p == p->parent->left);
rbt_delete_check(p->parent, delLeft);
}
return;
}
// when SL and SR has red node
if (delLeft) {
if (is_black(sr)) { // case 5(a) : delLeft is true and SR is black
rb_right_rotate(s);
sr = s->right;
}
rb_left_rotate(p); // case 6(a) : rotate the p node
sr->color = COLOR_BLACK;
} else {
if (is_black(sl)) { // case 5(b) : delLeft is false and SL is black
rb_left_rotate(s);
sl = s->left;
}
rb_right_rotate(p); // case 6(b) : rotate the p node
sl->color = COLOR_BLACK;
}
}
// delete a key from the RBT
int rbt_delete(rbtree* &tree, keyType key) {
if (NULL == tree) {
return 0;
}
// find the node
rbnode *curr, *temp;
for (curr = tree;;) {
if (key == curr->key) {
break;
}
curr = (key > curr->key) ? curr->right : curr->left;
if (NULL == curr) {
return 0;
}
}
// if the node to delete has two children
if (NULL != curr->left && NULL != curr->right) {
for (temp = curr->left; NULL != temp->right; temp = temp->right) {
}
curr->key = temp->key;
curr = temp;
}
if (NULL == curr->parent) { // it is the tree root
tree = (NULL == curr->left) ? curr->right : curr->left;
if (tree != NULL) {
tree->color = COLOR_BLACK;
tree->parent = NULL;
}
free(curr);
return 1;
}
// delete the node
rbnode* fa = curr->parent;
temp = (NULL == curr->left) ? curr->right : curr->left;
bool delLeft = (fa->left == curr);
if (NULL != temp) {
temp->parent = fa;
}
delLeft ? fa->left = temp : fa->right = temp;
if (curr->color != COLOR_RED) { // adjust after deletion
rbt_delete_check(fa, delLeft);
}
free(curr);
return 1;
}

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

B-樹

B+樹的查找

B+樹的插入

B+樹的删除

二. 資料結構定義

三、插入Key

四、删除Key

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義 三、 插入Key四、删除Key

B-樹

B+樹的查找

B+樹的插入

B+樹的删除

二. 資料結構定義

三、 插入Key

四、删除Key

繼續閱讀

B-樹、B+樹、紅黑樹B-樹二. 資料結構定義三、插入Key四、删除Key

三、插入Key