導讀:1建站知識本篇文章介紹了，基于B-樹和B+樹的使用：數據搜索和數據庫索引的詳細分析。需要的朋友參考下網站建設哪家好網站建設多少錢。

B-樹

1 .B-樹定義

B-樹是一種平衡的多路查找樹，它在文件系統中很有用。

定義：一棵m 階的B營銷型網站建設-樹，或者為空樹，或為滿足下列特性的m 叉樹： ⑴樹中每個結點至多有m 棵子樹； ⑵若根結點不是葉子結點，則至少有兩棵子樹；

⑶除根結點之外的所有非終端結點至少有[m/2] 棵子樹； ⑷所有的非終端結點中包含以下信息數據：

（n，A0，K1，A1，K2，…，Kn，An） 其中：Ki（i=1,2,…,n）為關鍵碼，且Ki

Ai 為指向子樹根結點的指針(i=0,1,…,n)，且指針Ai-1 所指子樹中所有結點的關鍵碼均小于Ki (i=1,2,…,n)，An 所指子樹中所有結點的關鍵碼均大于Kn.

n 為關鍵碼的個數。 ⑸所有的葉子結點都出現在同一層次上，并且不帶信息（可以看作是外部結點或查找失敗的結點，實際上這些結點不存在，指向這些結點的指針為空）。

即所有葉節點具有相同的深度，等于樹高度。

如一棵四階B-樹，其深度為4.

B-樹的查找類似二叉排序樹的查找，所不同的是B-樹每個結點上是多關鍵碼的有序表，在到達某個結點時，先在有序表中查找，若找到，則查找成功；否則，到按照對應的指針信息指向的子樹中去查找，當到達葉子結點時，則說明樹中沒有對應的關鍵碼。

在上圖的B-樹上查找關鍵字47的過程如下：

1）首先從更開始，根據根節點指針找到 *節點，因為 *a 節點中只有一個關鍵字，且給定值47 > 關鍵字35，則若存在必在指針A1所指的子樹內。

2）順指針找到 *c節點，該節點有兩個關鍵字（43和 78），而43 < 47 < 78,若存在比在指針A1所指的子樹中。

3）同樣，順指針找到 *g節點，在該節點找到關鍵字47,查找成功。

2. 查找算法

復制代碼 代碼如下:

typedef int KeyType ; #define m 5 /*B 樹的階，暫設為5*/ typedef struct Node{ int keynum; /* 結點中關鍵碼的個數，即結點的大小*/ struct Node *parent; /*指向雙親結點*/ KeyType key[m+1]; /*關鍵碼向量，0 號單元未用*/ struct Node *ptr[m+1]; /*子樹指針向量*/ Record *recptr[m+1]; /*記錄指針向量*/ }NodeType; /*B 樹結點類型*/ typedef struct{ NodeType *pt; /*指向找到的結點*/ int i; /*在結點中的關鍵碼序號，結點序號區間[1…m]*/ int tag; /* 1:查找成功，0:查找失敗*/ }Result; /*B 樹的查找結果類型*/ Result SearchBTree(NodeType *t,KeyType kx) { /*在m 階B 樹t 上查找關鍵碼kx，反回(pt,i,tag)。若查找成功，則特征值tag=1，*/ /*指針pt 所指結點中第i 個關鍵碼等于kx；否則，特征值tag=0,等于kx 的關鍵碼記錄*/ /*應插入在指針pt 所指結點中第i 個和第i+1 個關鍵碼之間*/ p=t;q=NULL;found=FALSE;i=0; /*初始化，p 指向待查結點，q 指向p 的雙親*/ while(p&&!found) { n=p->keynum;i=Search(p,kx); /*在p-->key[1…keynum]中查找*/ if(i>0&&p->key[i]= =kx) found=TRUE; /*找到*/ else {q=p;p=p->ptr[i];} } if(found) return (p,i,1); /*查找成功*/ else return (q,i,0); /*查找不成功，反回kx 的插入位置信息*/ }

關鍵詞標簽: 搜索 索引 詳細介紹