B-tree中,每個結點包含:
1、本結點所含關鍵字的個數(shù);
2、指向父結點的指針;
3、關鍵字;
4、指向子結點的指針;
對于一棵m階B-tree,每個結點至多可以擁有m個子結點。各結點的關鍵字和可以擁有的子結點數(shù)都有限制,規(guī)定m階B-tree中,根結點至少有2個子結點,除非根結點為葉子節(jié)點,相應的,根結點中關鍵字的個數(shù)為1~m-1;非根結點至少有[m/2]([],向上取整)個子結點,相應的,關鍵字個數(shù)為[m/2]-1~m-1。
B-tree性能
B-tree有以下特性:
1、關鍵字集合分布在整棵樹中;
2、任何一個關鍵字出現(xiàn)且只出現(xiàn)在一個結點中;
3、搜索有可能在非葉子結點結束;
4、其搜索性能等價于在關鍵字全集內(nèi)做一次二分查找;
5、自動層次控制;
由于限制了除根結點以外的非葉子結點,至少含有M/2個兒子,確保了結點的至少利用率,其最低搜索性能為:
其中,M為設定的非葉子結點最多子樹個數(shù),N為關鍵字總數(shù);
所以B-樹的性能總是等價于二分查找(與M值無關),也就沒有B樹平衡的問題;
由于M/2的限制,在插入結點時,如果結點已滿,需要將結點分裂為兩個各占M/2的結點;刪除結點時,需將兩個不足M/2的兄弟結點合并。
鑒于B-tree具有良好的定位特性,其常被用于對檢索時間要求苛刻的場合,例如:
1、B-tree索引是數(shù)據(jù)庫中存取和查找文件(稱為記錄或鍵值)的一種方法。
2、硬盤中的結點也是B-tree結構的。與內(nèi)存相比,硬盤必須花成倍的時間來存取一個數(shù)據(jù)元素,這是因為硬盤的機械部件讀寫數(shù)據(jù)的速度遠遠趕不上純電子媒體的內(nèi)存。與一個結點兩個分支的二元樹相比,B-tree利用多個分支(稱為子樹)的結點,減少獲取記錄時所經(jīng)歷的結點數(shù),從而達到節(jié)省存取時間的目的。
/* btrees.h */
/*
* 平衡多路樹的一種重要方案。
* 在 1970 年由 R. Bayer 和 E. McCreight 發(fā)明。
*/
#define M 1
/* B 樹的階,即非根節(jié)點中鍵的最小數(shù)目。
* 有些人把階定義為非根節(jié)點中子樹的最大數(shù)目。
*/
typedef int typekey;
typedef struct btnode { /* B-Tree 節(jié)點 */
int d; /* 節(jié)點中鍵的數(shù)目 */
typekey k[2*M]; /* 鍵 */
char *v[2*M]; /* 值 */
struct btnode *p[2*M+1]; /* 指向子樹的指針 */
} node, *btree;
/*
* 每個鍵的左子樹中的所有的鍵都小于這個鍵,
* 每個鍵的右子樹中的所有的鍵都大于等于這個鍵。
* 葉子節(jié)點中的每個鍵都沒有子樹。
*/
/* 當 M 等于 1 時也稱為 2-3 樹
* +----+----+
* | k0 | k1 |
* +-+----+----+---
* | p0 | p1 | p2 |
* +----+----+----+
*/
extern int btree_disp; /* 查找時找到的鍵在節(jié)點中的位置 */
extern char * InsValue; /* 與要插的鍵相對應的值 */
extern btree search(typekey, btree);
extern btree insert(typekey,btree);
extern btree delete(typekey,btree);
extern int height(btree);
extern int count(btree);
extern double payload(btree);
extern btree deltree(btree);
/* end of btrees.h */
/*******************************************************/
/* btrees.c */
#include <stdlib.h>
#include <stdio.h>
#include "btrees.h"
btree search(typekey, btree);
btree insert(typekey,btree);
btree delete(typekey,btree);
int height(btree);
int count(btree);
double payload(btree);
btree deltree(btree);
static void InternalInsert(typekey, btree);
static void InsInNode(btree, int);
static void SplitNode(btree, int);
static btree NewRoot(btree);
static void InternalDelete(typekey, btree);
static void JoinNode(btree, int);
static void MoveLeftNode(btree t, int);
static void MoveRightNode(btree t, int);
static void DelFromNode(btree t, int);
static btree FreeRoot(btree);
static btree delall(btree);
static void Error(int,typekey);
int btree_disp; /* 查找時找到的鍵在節(jié)點中的位置 */
char * InsValue = NULL; /* 與要插的鍵相對應的值 */
static int flag; /* 節(jié)點增減標志 */
static int btree_level = 0; /* 多路樹的高度 */
static int btree_count = 0; /* 多路樹的鍵總數(shù) */
static int node_sum = 0; /* 多路樹的節(jié)點總數(shù) */
static int level; /* 當前訪問的節(jié)點所處的高度 */
static btree NewTree; /* 在節(jié)點分割的時候指向新建的節(jié)點 */
static typekey InsKey; /* 要插入的鍵 */
btree search(typekey key, btree t)
{
int i,j,m;
level=btree_level-1;
while (level >= 0)
{
for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m));
if (key == t->k [ i ])
{
btree_disp = i;
return t;
}
if (key > t->k [ i ]) /* i == t->d-1 時有可能出現(xiàn) */
i++;
t = t->p[ i ];
level--;
}
return NULL;
}
btree insert(typekey key, btree t)
{
level=btree_level;
InternalInsert(key, t);
if (flag == 1) /* 根節(jié)點滿之后,它被分割成兩個半滿節(jié)點 */
t=NewRoot(t); /* 樹的高度增加 */
return t;
}
void InternalInsert(typekey key, btree t)
{
int i,j,m;
level--;
if (level < 0) /* 到達了樹的底部: 指出要做的插入 */
{
NewTree = NULL; /* 這個鍵沒有對應的子樹 */
InsKey = key; /* 導致底層的葉子節(jié)點增加鍵值+空子樹對 */
btree_count++;
flag = 1; /* 指示上層節(jié)點把返回的鍵插入其中 */
return;
}
for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m));
if (key == t->k[ i ])
{
Error(1,key); /* 鍵已經(jīng)在樹中 */
flag = 0;
return;
}
if (key > t->k[ i ]) /* i == t->d-1 時有可能出現(xiàn) */
i++;
InternalInsert(key, t->p[ i ]);
if (flag == 0)
return;
/* 有新鍵要插入到當前節(jié)點中 */
if (t->d < 2*M) /* 當前節(jié)點未滿 */
{
InsInNode(t, i); /* 把鍵值+子樹對插入當前節(jié)點中 */
flag = 0; /* 指示上層節(jié)點沒有需要插入的鍵值+子樹,插入過程結束 */
}
else /* 當前節(jié)點已滿,則分割這個頁面并把鍵值+子樹對插入當前節(jié)點中 */
SplitNode(t, i); /* 繼續(xù)指示上層節(jié)點把返回的鍵值+子樹插入其中 */
}
/*
* 把一個鍵和對應的右子樹插入一個節(jié)點中
*/
void InsInNode(btree t, int d)
{
int i;
/* 把所有大于要插入的鍵值的鍵和對應的右子樹右移 */
for(i = t->d; i > d; i--)
{
t->k[ i ] = t->k[i-1];
t->v[ i ] = t->v[i-1];
t->p[i+1] = t->p[ i ];
}
/* 插入鍵和右子樹 */
t->k[ i ] = InsKey;
t->p[i+1] = NewTree;
t->v[ i ] = InsValue;
t->d++;
}
/*
* 前件是要插入一個鍵和對應的右子樹,并且本節(jié)點已經(jīng)滿
* 導致分割這個節(jié)點,插入鍵和對應的右子樹,
* 并向上層返回一個要插入鍵和對應的右子樹
*/
void SplitNode(btree t, int d)
{
int i,j;
btree temp;
typekey temp_k;
char *temp_v;
/* 建立新節(jié)點 */
temp = (btree)malloc(sizeof(node));
/*
* +---+--------+-----+-----+--------+-----+
* | 0 | ...... | M | M+1 | ...... |2*M-1|
* +---+--------+-----+-----+--------+-----+
* |<- M+1 ->|<- M-1 ->|
*/
if (d > M) /* 要插入當前節(jié)點的右半部分 */
{
/* 把從 2*M-1 到 M+1 的 M-1 個鍵值+子樹對轉移到新節(jié)點中,
* 并且為要插入的鍵值+子樹空出位置 */
for(i=2*M-1,j=M-1; i>=d; i--,j--)
{
temp->k[j] = t->k[ i ];
temp->v[j] = t->v[ i ];
temp->p[j+1] = t->p[i+1];
}
for(i=d-1,j=d-M-2; j>=0; i--,j--)
{
temp->k[j] = t->k[ i ];
temp->v[j] = t->v[ i ];
temp->p[j+1] = t->p[i+1];
}
/* 把節(jié)點的最右子樹轉移成新節(jié)點的最左子樹 */
temp->p[0] = t->p[M+1];
/* 在新節(jié)點中插入鍵和右子樹 */
temp->k[d-M-1] = InsKey;
temp->p[d-M] = NewTree;
temp->v[d-M-1] = InsValue;
/* 設置要插入上層節(jié)點的鍵和值 */
InsKey = t->k[M];
InsValue = t->v[M];
}
else /* d <= M */
{
/* 把從 2*M-1 到 M 的 M 個鍵值+子樹對轉移到新節(jié)點中 */
for(i=2*M-1,j=M-1; j>=0; i--,j--)
{
temp->k[j] = t->k[ i ];
temp->v[j] = t->v[ i ];
temp->p[j+1] = t->p[i+1];
}
if (d == M) /* 要插入當前節(jié)點的正中間 */
/* 把要插入的子樹作為新節(jié)點的最左子樹 */
temp->p[0] = NewTree;
/* 直接把要插入的鍵和值返回給上層節(jié)點 */
else /* (d<M) 要插入當前節(jié)點的左半部分 */
{
/* 把節(jié)點當前的最右子樹轉移成新節(jié)點的最左子樹 */
temp->p[0] = t->p[M];
/* 保存要插入上層節(jié)點的鍵和值 */
temp_k = t->k[M-1];
temp_v = t->v[M-1];
/* 把所有大于要插入的鍵值的鍵和對應的右子樹右移 */
for(i=M-1; i>d; i--)
{
t->k[ i ] = t->k[i-1];
t->v[ i ] = t->v[i-1];
t->p[i+1] = t->p[ i ];
}
/* 在節(jié)點中插入鍵和右子樹 */
t->k[d] = InsKey;
t->p[d+1] = NewTree;
t->v[d] = InsValue;
/* 設置要插入上層節(jié)點的鍵和值 */
InsKey = temp_k;
InsValue = temp_v;
}
}
t->d =M;
temp->d = M;
NewTree = temp;
node_sum++;
}
btree delete(typekey key, btree t)
{
level=btree_level;
InternalDelete(key, t);
if (t->d == 0)
/* 根節(jié)點的子節(jié)點合并導致根節(jié)點鍵的數(shù)目隨之減少,
* 當根節(jié)點中沒有鍵的時候,只有它的最左子樹可能非空 */
t=FreeRoot(t);
return t;
}
void InternalDelete(typekey key, btree t)
{
int i,j,m;
btree l,r;
int lvl;
level--;
if (level < 0)
{
Error(0,key); /* 在整個樹中未找到要刪除的鍵 */
flag = 0;
return;
}
for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m));
if (key == t->k[ i ]) /* 找到要刪除的鍵 */
{
if (t->v[ i ] != NULL)
free(t->v[ i ]); /* 釋放這個節(jié)點包含的值 */
if (level == 0) /* 有子樹為空則這個鍵位于葉子節(jié)點 */
{
DelFromNode(t,i);
btree_count--;
flag = 1;
/* 指示上層節(jié)點本子樹的鍵數(shù)量減少 */
return;
}
else /* 這個鍵位于非葉節(jié)點 */
{
lvl = level-1;
/* 找到前驅(qū)節(jié)點 */
r = t->p[ i ];
while (lvl > 0)
{
r = r->p[r->d];
lvl--;
}
t->k[ i ]=r->k[r->d-1];
t->v[ i ]=r->v[r->d-1];
r->v[r->d-1]=NULL;
key = r->k[r->d-1];
}
}
else if (key > t->k[ i ]) /* i == t->d-1 時有可能出現(xiàn) */
i++;
InternalDelete(key,t->p[ i ]);
/* 調(diào)整平衡 */
if (flag == 0)
return;
if (t->p[ i ]->d < M)
{
if (i == t->d) /* 在最右子樹中發(fā)生了刪除 */
i--; /* 調(diào)整最右鍵的左右子樹平衡 */
l = t->p [ i ];
r = t->p[i+1];
if (r->d > M)
MoveLeftNode(t,i);
else if(l->d > M)
MoveRightNode(t,i);
else
{
JoinNode(t,i);
/* 繼續(xù)指示上層節(jié)點本子樹的鍵數(shù)量減少 */
return;
}
flag = 0;
/* 指示上層節(jié)點本子樹的鍵數(shù)量沒有減少,刪除過程結束 */
}
}
/*
* 合并一個節(jié)點的某個鍵對應的兩個子樹
*/
void JoinNode(btree t, int d)
{
btree l,r;
int i,j;
l = t->p[d];
r = t->p[d+1];
/* 把這個鍵下移到它的左子樹 */
l->k[l->d] = t->k[d];
l->v[l->d] = t->v[d];
/* 把右子樹中的所有鍵值和子樹轉移到左子樹 */
for (j=r->d-1,i=l->d+r->d; j >= 0 ; j--,i--)
{
l->k[ i ] = r->k[j];
l->v[ i ] = r->v[j];
l->p[ i ] = r->p[j];
}
l->p[l->d+r->d+1] = r->p[r->d];
l->d += r->d+1;
/* 釋放右子樹的節(jié)點 */
free(r);
/* 把這個鍵右邊的鍵和對應的右子樹左移 */
for (i=d; i < t->d-1; i++)
{
t->k[ i ] = t->k[i+1];
t->v[ i ] = t->v[i+1];
t->p[i+1] = t->p[i+2];
}
t->d--;
node_sum--;
}
/*
* 從一個鍵的右子樹向左子樹轉移一些鍵,使兩個子樹平衡
*/
void MoveLeftNode(btree t, int d)
{
btree l,r;
int m; /* 應轉移的鍵的數(shù)目 */
int i,j;
l = t->p[d];
r = t->p[d+1];
m = (r->d - l->d)/2;
/* 把這個鍵下移到它的左子樹 */
l->k[l->d] = t->k[d];
l->v[l->d] = t->v[d];
/* 把右子樹的最左子樹轉移成左子樹的最右子樹
* 從右子樹向左子樹移動 m-1 個鍵+子樹對 */
for (j=m-2,i=l->d+m-1; j >= 0; j--,i--)
{
l->k[ i ] = r->k[j];
l->v[ i ] = r->v[j];
l->p[ i ] = r->p[j];
}
l->p[l->d+m] = r->p[m-1];
/* 把右子樹的最左鍵提升到這個鍵的位置上 */
t->k[d] = r->k[m-1];
t->v[d] = r->v[m-1];
/* 把右子樹中的所有鍵值和子樹左移 m 個位置 */
r->p[0] = r->p[m];
for (i=0; i<r->d-m; i++)
{
r->k[ i ] = r->k[i+m];
r->v[ i ] = r->v[i+m];
r->p[ i ] = r->p[i+m];
}
r->p[r->d-m] = r->p[r->d];
l->d+=m;
r->d-=m;
}
/*
* 從一個鍵的左子樹向右子樹轉移一些鍵,使兩個子樹平衡
*/
void MoveRightNode(btree t, int d)
{
btree l,r;
int m; /* 應轉移的鍵的數(shù)目 */
int i,j;
l = t->p[d];
r = t->p[d+1];
m = (l->d - r->d)/2;
/* 把右子樹中的所有鍵值和子樹右移 m 個位置 */
r->p[r->d+m]=r->p[r->d];
for (i=r->d-1; i>=0; i--)
{
r->k[i+m] = r->k[ i ];
r->v[i+m] = r->v[ i ];
r->p[i+m] = r->p[ i ];
}
/* 把這個鍵下移到它的右子樹 */
r->k[m-1] = t->k[d];
r->v[m-1] = t->v[d];
/* 把左子樹的最右子樹轉移成右子樹的最左子樹 */
r->p[m-1] = l->p[l->d];
/* 從左子樹向右子樹移動 m-1 個鍵+子樹對 */
for (i=l->d-1,j=m-2; j>=0; j--,i--)
{
r->k[j] = l->k[ i ];
r->v[j] = l->v[ i ];
r->p[j] = l->p[ i ];
}
/* 把左子樹的最右鍵提升到這個鍵的位置上 */
t->k[d] = l->k[ i ];
t->v[d] = l->v[ i ];
l->d-=m;
r->d+=m;
}
/*
* 把一個鍵和對應的右子樹從一個節(jié)點中刪除
*/
void DelFromNode(btree t, int d)
{
int i;
/* 把所有大于要刪除的鍵值的鍵左移 */
for(i=d; i < t->d-1; i++)
{
t->k[ i ] = t->k[i+1];
t->v[ i ] = t->v[i+1];
}
t->d--;
}
/*
* 建立有兩個子樹和一個鍵的根節(jié)點
*/
btree NewRoot(btree t)
{
btree temp;
temp = (btree)malloc(sizeof(node));
temp->d = 1;
temp->p[0] = t;
temp->p[1] = NewTree;
temp->k[0] = InsKey;
temp->v[0] = InsValue;
btree_level++;
node_sum++;
return(temp);
}
/*
* 釋放根節(jié)點,并返回它的最左子樹
*/
btree FreeRoot(btree t)
{
btree temp;
temp = t->p[0];
free(t);
btree_level--;
node_sum--;
return temp;
}
void Error(int f,typekey key)
{
if (f)
printf("Btrees error: Insert %d!\n",key);
else
printf("Btrees error: delete %d!\n",key);
}
int height(btree t)
{
return btree_level;
}
int count(btree t)
{
return btree_count;
}
double payload(btree t)
{
if (node_sum==0)
return 1;
return (double)btree_count/(node_sum*(2*M));
}
btree deltree (btree t)
{
level=btree_level;
btree_level = 0;
return delall(t);
}
btree delall(btree t)
{
int i;
level--;
if (level >= 0)
{
for (i=0; i < t->d; i++)
if (t->v[ i ] != NULL)
free(t->v[ i ]);
if (level > 0)
for (i=0; i<= t->d ; i++)
t->p[ i ]=delall(t->p[ i ]);
free(t);
}
return NULL;
}
/* end of btrees.c */
另外還有一種與此類似的樹結構叫B+樹,像 Berkerly DB , sqlite , mysql 數(shù)據(jù)庫都使用了B+樹算法處理索引。
B+和B-(即B)是因為每個結點上的關鍵字不同。一個多一個,一個少一個。
對于B+樹,其結點結構與B-tree相同,不同的是各結點的關鍵字和可以擁有的子結點數(shù)。如m階B+樹中,每個結點至多可以擁有m個子結點。非根結點至少有[m/2]個子結點,而關鍵字個數(shù)比B-tree多一個,為[m/2]~m。
這兩種處理索引的數(shù)據(jù)結構的不同之處:
1。B樹中同一鍵值不會出現(xiàn)多次,并且它有可能出現(xiàn)在葉結點,也有可能出現(xiàn)在非葉結點中。而B+樹的鍵一定會出現(xiàn)在葉結點中,并且有可能在非葉結點中也有可能重復出現(xiàn),以維持B+樹的平衡。
2。因為B樹鍵位置不定,且在整個樹結構中只出現(xiàn)一次,雖然可以節(jié)省存儲空間,但使得在插入、刪除操作復雜度明顯增加。B+樹相比來說是一種較好的折中。
3。B樹的查詢效率與鍵在樹中的位置有關,最大時間復雜度與B+樹相同(在葉結點的時候),最小時間復雜度為1(在根結點的時候)。而B+樹的時間復雜度對某建成的樹是固定的。
結點平差在工程測量中的具體應用
格式:pdf
大?。?span id="2yu1ny7" class="single-tag-height">187KB
頁數(shù): 10頁
評分: 4.3
拉結點預埋技術交底
格式:pdf
大?。?span id="dluqr12" class="single-tag-height">187KB
頁數(shù): 3頁
評分: 4.4
第 1 頁 共 3 頁 1、本表由施工單位填寫,交底單位和接受單位各存一份。 2、當做分項工程施工技術交底時,應填寫“分項工程名稱”欄,其他技術交底可不填寫。 技 術 交 底 記 錄 表 C2-1 編 號 工程名稱 鷹潭恒大綠洲( 4~14#棟)主體 及配套工程 -10#樓 交底日期 2011年 9月 施工單位 中鐵建設集團武漢分公司第五項目部 分項工程名稱 / 交底提要 腳手架預埋技術交底 交底內(nèi)容: 一、施工準備 600mm長鋼管(數(shù)量根據(jù)現(xiàn)場需要確定) 、拉結點預埋位置布置圖(如圖 1-1 和圖 1-2 所示) 二、施工方法 根據(jù)圖 1-1 中的拉結點預埋位置, 混凝土澆筑施工前, 在相應樓層的相應位置預埋 600mm 長鋼管作為連墻件與結構的拉結點。 三、拉結點構造要求及注意事項 1、不大于 30m2 設置一個拉結點。 2、連墻件采用剛性拉接,層層設置,以承受水平方向的壓力作用,加