基于B-樹(shù)和B+樹(shù)的使用:數(shù)據(jù)搜索和數(shù)據(jù)庫(kù)索引的詳細(xì)介紹
1 .B-樹(shù)定義
B-樹(shù)是一種平衡的多路查找樹(shù),它在文件系統(tǒng)中很有用。
定義:一棵m 階的B-樹(shù),或者為空樹(shù),或?yàn)闈M(mǎn)足下列特性的m 叉樹(shù):
⑴樹(shù)中每個(gè)結(jié)點(diǎn)至多有m 棵子樹(shù);
⑵若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn),則至少有兩棵子樹(shù);
⑶除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有[m/2] 棵子樹(shù);
⑷所有的非終端結(jié)點(diǎn)中包含以下信息數(shù)據(jù):
(n,A0,K1,A1,K2,…,Kn,An)
其中:Ki(i=1,2,…,n)為關(guān)鍵碼,且Ki<Ki+1,
Ai 為指向子樹(shù)根結(jié)點(diǎn)的指針(i=0,1,…,n),且指針Ai-1 所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵碼均小于Ki (i=1,2,…,n),An 所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵碼均大于Kn.
n 為關(guān)鍵碼的個(gè)數(shù)。
⑸所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上,并且不帶信息(可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn),實(shí)際上這些結(jié)點(diǎn)不存在,指向這些結(jié)點(diǎn)的指針為空)。
即所有葉節(jié)點(diǎn)具有相同的深度,等于樹(shù)高度。
如一棵四階B-樹(shù),其深度為4.
B-樹(shù)的查找類(lèi)似二叉排序樹(shù)的查找,所不同的是B-樹(shù)每個(gè)結(jié)點(diǎn)上是多關(guān)鍵碼的有序表,在到達(dá)某個(gè)結(jié)點(diǎn)時(shí),先在有序表中查找,若找到,則查找成功;否則,到按照對(duì)應(yīng)的指針信息指向的子樹(shù)中去查找,當(dāng)?shù)竭_(dá)葉子結(jié)點(diǎn)時(shí),則說(shuō)明樹(shù)中沒(méi)有對(duì)應(yīng)的關(guān)鍵碼。
在上圖的B-樹(shù)上查找關(guān)鍵字47的過(guò)程如下:
1)首先從更開(kāi)始,根據(jù)根節(jié)點(diǎn)指針找到 *節(jié)點(diǎn),因?yàn)?*a 節(jié)點(diǎn)中只有一個(gè)關(guān)鍵字,且給定值47 > 關(guān)鍵字35,則若存在必在指針A1所指的子樹(shù)內(nèi)。
2)順指針找到 *c節(jié)點(diǎn),該節(jié)點(diǎn)有兩個(gè)關(guān)鍵字(43和 78),而43 < 47 < 78,若存在比在指針A1所指的子樹(shù)中。
3)同樣,順指針找到 *g節(jié)點(diǎn),在該節(jié)點(diǎn)找到關(guān)鍵字47,查找成功。
2. 查找算法
typedef int KeyType ;
#define m 5 /*B 樹(shù)的階,暫設(shè)為5*/
typedef struct Node{
int keynum; /* 結(jié)點(diǎn)中關(guān)鍵碼的個(gè)數(shù),即結(jié)點(diǎn)的大小*/
struct Node *parent; /*指向雙親結(jié)點(diǎn)*/
KeyType key[m+1]; /*關(guān)鍵碼向量,0 號(hào)單元未用*/
struct Node *ptr[m+1]; /*子樹(shù)指針向量*/
Record *recptr[m+1]; /*記錄指針向量*/
}NodeType; /*B 樹(shù)結(jié)點(diǎn)類(lèi)型*/
typedef struct{
NodeType *pt; /*指向找到的結(jié)點(diǎn)*/
int i; /*在結(jié)點(diǎn)中的關(guān)鍵碼序號(hào),結(jié)點(diǎn)序號(hào)區(qū)間[1…m]*/
int tag; /* 1:查找成功,0:查找失敗*/
}Result; /*B 樹(shù)的查找結(jié)果類(lèi)型*/
Result SearchBTree(NodeType *t,KeyType kx)
{
/*在m 階B 樹(shù)t 上查找關(guān)鍵碼kx,反回(pt,i,tag)。若查找成功,則特征值tag=1,*/
/*指針pt 所指結(jié)點(diǎn)中第i 個(gè)關(guān)鍵碼等于kx;否則,特征值tag=0,等于kx 的關(guān)鍵碼記錄*/
/*應(yīng)插入在指針pt 所指結(jié)點(diǎn)中第i 個(gè)和第i+1 個(gè)關(guān)鍵碼之間*/
p=t;q=NULL;found=FALSE;i=0; /*初始化,p 指向待查結(jié)點(diǎn),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 的插入位置信息*/
}
B- 樹(shù)查找算法分析
從查找算法中可以看出, 在B- 樹(shù)中進(jìn)行查找包含兩種基本操作:
( 1) 在B- 樹(shù)中查找結(jié)點(diǎn);
( 2) 在結(jié)點(diǎn)中查找關(guān)鍵字。
由于B- 樹(shù)通常存儲(chǔ)在磁盤(pán)上, 則前一查找操作是在磁盤(pán)上進(jìn)行的, 而后一查找操作是在內(nèi)存中進(jìn)行的, 即在磁盤(pán)上找到指針p 所指結(jié)點(diǎn)后, 先將結(jié)點(diǎn)中的信息讀入內(nèi)存, 然后再利用順序查找或折半查找查詢(xún)等于K 的關(guān)鍵字。顯然, 在磁盤(pán)上進(jìn)行一次查找比在內(nèi)存中進(jìn)行一次查找的時(shí)間消耗多得多.
因此, 在磁盤(pán)上進(jìn)行查找的次數(shù)、即待查找關(guān)鍵字所在結(jié)點(diǎn)在B- 樹(shù)上的層次樹(shù), 是決定B樹(shù)查找效率的首要因素
那么,對(duì)含有n 個(gè)關(guān)鍵碼的m 階B-樹(shù),最壞情況下達(dá)到多深呢?可按二叉平衡樹(shù)進(jìn)行類(lèi)似分析。首先,討論m 階B-數(shù)各層上的最少結(jié)點(diǎn)數(shù)。
由B樹(shù)定義:B樹(shù)包含n個(gè)關(guān)鍵字。因此有n+1個(gè)樹(shù)葉都在第J+1 層。
1)第一層為根,至少一個(gè)結(jié)點(diǎn),根至少有兩個(gè)孩子,因此在第二層至少有兩個(gè)結(jié)點(diǎn)。
2)除根和樹(shù)葉外,其它結(jié)點(diǎn)至少有[m/2]個(gè)孩子,因此第三層至少有2*[m/2]個(gè)結(jié)點(diǎn),在第四層至少有2*[m/2]2 個(gè)結(jié)點(diǎn)…
3)那么在第J+1層至少有2*[m/2]J-1個(gè)結(jié)點(diǎn),而J+1層的結(jié)點(diǎn)為葉子結(jié)點(diǎn),于是葉子結(jié)點(diǎn)的個(gè)數(shù)n+1。有:
也就是說(shuō)在n個(gè)關(guān)鍵字的B樹(shù)查找,從根節(jié)點(diǎn)到關(guān)鍵字所在的節(jié)點(diǎn)所涉及的節(jié)點(diǎn)數(shù)不超過(guò):
3.B-樹(shù)的插入
B-樹(shù)的生成也是從空樹(shù)起,逐個(gè)插入關(guān)鍵字而得。但由于B-樹(shù)結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)必須≥ceil(m/2)-1,因此,每次插入一個(gè)關(guān)鍵字不是在樹(shù)中添加一個(gè)葉子結(jié)點(diǎn),而是首先在最低層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字,若該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)不超過(guò)m-1,則插入完成,否則要產(chǎn)生結(jié)點(diǎn)的“分裂”,
如圖(a) 為3階的B-樹(shù)(圖中略去F結(jié)點(diǎn)(即葉子結(jié)點(diǎn))),假設(shè)需依次插入關(guān)鍵字30,26,85。
1) 首先通過(guò)查找確定插入的位置。由根*a 起進(jìn)行查找,確定30應(yīng)插入的在*d 節(jié)點(diǎn)中。由于*d 中關(guān)鍵字?jǐn)?shù)目不超過(guò)2(即m-1),故第一個(gè)關(guān)鍵字插入完成:如(b)
2) 同樣,通過(guò)查找確定關(guān)鍵字26亦應(yīng)插入 *d. 由于*d節(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)目超過(guò)2,此時(shí)需要將 *d分裂成兩個(gè)節(jié)點(diǎn),關(guān)鍵字26及其前、后兩個(gè)指針仍保留在 *d 節(jié)點(diǎn)中,而關(guān)鍵字37 及其前、后兩個(gè)指針存儲(chǔ)到新的產(chǎn)生的節(jié)點(diǎn) *d` 中。同時(shí)將關(guān)鍵字30 和指示節(jié)點(diǎn) *d `的指針插入到其雙親的節(jié)點(diǎn)中。由于 *b節(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目沒(méi)有超過(guò)2,則插入完成.如(c)(d)
3) (e) -(g) 為插入85后;
插入算法:
int InserBTree(NodeType **t,KeyType kx,NodeType *q,int i){
/* 在m 階B 樹(shù)*t 上結(jié)點(diǎn)*q 的key[i],key[i+1]之間插入關(guān)鍵碼kx*/
/*若引起結(jié)點(diǎn)過(guò)大,則沿雙親鏈進(jìn)行必要的結(jié)點(diǎn)分裂調(diào)整,使*t仍為m 階B 樹(shù)*/
x=kx;ap=NULL;finished=FALSE;
while(q&&!finished)
{
Insert(q,i,x,ap); /*將x 和ap 分別插入到q->key[i+1]和q->ptr[i+1]*/
if(q->keynum<m) finished=TRUE; /*插入完成*/
else
{ /*分裂結(jié)點(diǎn)*p*/
s=m/2;split(q,ap);x=q->key[s];
/*將q->key[s+1…m],q->ptr[s…m]和q->recptr[s+1…m]移入新結(jié)點(diǎn)*ap*/
q=q->parent;
if(q) i=Search(q,kx); /*在雙親結(jié)點(diǎn)*q 中查找kx 的插入位置*/
}
}
if(!finished) /*(*t)是空樹(shù)或根結(jié)點(diǎn)已分裂為*q*和ap*/
NewRoot(t,q,x,ap); /*生成含信息(t,x,ap)的新的根結(jié)點(diǎn)*t,原*t 和ap 為子樹(shù)指針*/
}
4. B-樹(shù)的刪除
反之,若在B-樹(shù)上刪除一個(gè)關(guān)鍵字,則首先應(yīng)找到該關(guān)鍵字所在結(jié)點(diǎn),并從中刪除之,若該結(jié)點(diǎn)為最下層的非終端結(jié)點(diǎn),且其中的關(guān)鍵字?jǐn)?shù)目不少于ceil(m/2),則刪除完成,否則要進(jìn)行“合并”結(jié)點(diǎn)的操作。假若所刪關(guān)鍵字為非終端結(jié)點(diǎn)中的Ki,則可以指針Ai所指子樹(shù)中的最小關(guān)鍵字Y替代Ki,然后在相應(yīng)的結(jié)點(diǎn)中刪去Y。例如,在下圖 圖4.1( a)的B-樹(shù)上刪去45,可以*f結(jié)點(diǎn)中的50替代45,然后在*f結(jié)點(diǎn)中刪去50。
圖4.1( a)
因此,下面我們可以只需討論刪除最下層非終端結(jié)點(diǎn)中的關(guān)鍵字的情形。有下列三種可能:
(1)被刪關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目不小于ceil(m/2),則只需從該結(jié)點(diǎn)中刪去該關(guān)鍵字Ki和相應(yīng)指針Ai,樹(shù)的其它部分不變,例如,從圖 圖4.1( a)所示B-樹(shù)中刪去關(guān)鍵字12,刪除后的B-樹(shù)如圖 圖4.2( a)所示:
圖4.2( a)
(2)被刪關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目等于ceil(m/2)-1,而與該結(jié)點(diǎn)相鄰的右兄弟(或左兄弟)結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目大于ceil(m/2)-1,則需將其兄弟結(jié)點(diǎn)中的最小(或最大)的關(guān)鍵字上移至雙親結(jié)點(diǎn)中,而將雙親結(jié)點(diǎn)中小于(或大于)且緊靠該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在結(jié)點(diǎn)中。
[例如],從圖圖4.2( a)中刪去50,需將其右兄弟結(jié)點(diǎn)中的61上移至*e結(jié)點(diǎn)中,而將*e結(jié)點(diǎn)中的53移至*f,從而使*f和*g中關(guān)鍵字?jǐn)?shù)目均不小于ceil(m-1)-1,而雙親結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目不變,如圖圖4.2(b)所示。
圖4.2(b)
(3)被刪關(guān)鍵字所在結(jié)點(diǎn)和其相鄰的兄弟結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目均等于ceil(m/2)-1。假設(shè)該結(jié)點(diǎn)有右兄弟,且其右兄弟結(jié)點(diǎn)地址由雙親結(jié)點(diǎn)中的指針Ai所指,則在刪去關(guān)鍵字之后,它所在結(jié)點(diǎn)中剩余的關(guān)鍵字和指針,加上雙親結(jié)點(diǎn)中的關(guān)鍵字Ki一起,合并到 Ai所指兄弟結(jié)點(diǎn)中(若沒(méi)有右兄弟,則合并至左兄弟結(jié)點(diǎn)中)。
[例如],從圖4.2(b)所示 B-樹(shù)中刪去53,則應(yīng)刪去*f結(jié)點(diǎn),并將*f中的剩余信息(指針“空”)和雙親*e結(jié)點(diǎn)中的 61一起合并到右兄弟結(jié)點(diǎn)*g中。刪除后的樹(shù)如圖4.2(c)所示。
圖4.2(c)
如果因此使雙親結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目小于ceil(m/2)-1,則依次類(lèi)推。
[例如],在 圖4.2(c)的B-樹(shù)中刪去關(guān)鍵字37之后,雙親b結(jié)點(diǎn)中剩余信息(“指針c”)應(yīng)和其雙親*a結(jié)點(diǎn)中關(guān)鍵字45一起合并至右兄弟結(jié)點(diǎn)*e中,刪除后的B-樹(shù)如圖 4.2(d)所示。
圖 4.2(d)
B-樹(shù)主要應(yīng)用在文件系統(tǒng)
為了將大型數(shù)據(jù)庫(kù)文件存儲(chǔ)在硬盤(pán)上 以減少訪問(wèn)硬盤(pán)次數(shù)為目的 在此提出了一種平衡多路查找樹(shù)——B-樹(shù)結(jié)構(gòu) 由其性能分析可知它的檢索效率是相當(dāng)高的 為了提高 B-樹(shù)性能'還有很多種B-樹(shù)的變型,力圖對(duì)B-樹(shù)進(jìn)行改進(jìn)
樹(shù)的差異在于:
⑴有n 棵子樹(shù)的結(jié)點(diǎn)中含有n 個(gè)關(guān)鍵碼;
⑵所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵碼的信息,及指向含有這些關(guān)鍵碼記錄的指針,且
葉子結(jié)點(diǎn)本身依關(guān)鍵碼的大小自小而大的順序鏈接。
⑶所有的非終端結(jié)點(diǎn)可以看成是索引部分,結(jié)點(diǎn)中僅含有其子樹(shù)根結(jié)點(diǎn)中最大(或最?。╆P(guān)鍵碼。

樹(shù),不管查找成功與否,每次查找都是走了一條從根到葉子結(jié)點(diǎn)的路徑。
B+樹(shù)在數(shù)據(jù)庫(kù)中的應(yīng)用
1. 索引在數(shù)據(jù)庫(kù)中的作用
在數(shù)據(jù)庫(kù)系統(tǒng)的使用過(guò)程當(dāng)中,數(shù)據(jù)的查詢(xún)是使用最頻繁的一種數(shù)據(jù)操作。
最基本的查詢(xún)算法當(dāng)然是順序查找(linear search),遍歷表然后逐行匹配行值是否等于待查找的關(guān)鍵字,其時(shí)間復(fù)雜度為O(n)。但時(shí)間復(fù)雜度為O(n)的算法規(guī)模小的表,負(fù)載輕的數(shù)據(jù)庫(kù),也能有好的性能。 但是數(shù)據(jù)增大的時(shí)候,時(shí)間復(fù)雜度為O(n)的算法顯然是糟糕的,性能就很快下降了。
好在計(jì)算機(jī)科學(xué)的發(fā)展提供了很多更優(yōu)秀的查找算法,例如二分查找(binary search)、二叉樹(shù)查找(binary tree search)等。如果稍微分析一下會(huì)發(fā)現(xiàn),每種查找算法都只能應(yīng)用于特定的數(shù)據(jù)結(jié)構(gòu)之上,例如二分查找要求被檢索數(shù)據(jù)有序,而二叉樹(shù)查找只能應(yīng)用于二叉查找樹(shù)上,但是數(shù)據(jù)本身的組織結(jié)構(gòu)不可能完全滿(mǎn)足各種數(shù)據(jù)結(jié)構(gòu)(例如,理論上不可能同時(shí)將兩列都按順序進(jìn)行組織),所以,在數(shù)據(jù)之外,數(shù)據(jù)庫(kù)系統(tǒng)還維護(hù)著滿(mǎn)足特定查找算法的數(shù)據(jù)結(jié)構(gòu),這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用(指向)數(shù)據(jù),這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高級(jí)查找算法。這種數(shù)據(jù)結(jié)構(gòu),就是索引。
索引是對(duì)數(shù)據(jù)庫(kù)表 中一個(gè)或多個(gè)列的值進(jìn)行排序的結(jié)構(gòu)。與在表 中搜索所有的行相比,索引用指針 指向存儲(chǔ)在表中指定列的數(shù)據(jù)值,然后根據(jù)指定的次序排列這些指針,有助于更快地獲取信息。通常情 況下 ,只有當(dāng)經(jīng)常查詢(xún)索引列中的數(shù)據(jù)時(shí) ,才需要在表上創(chuàng)建索引。索引將占用磁盤(pán)空間,并且影響數(shù) 據(jù)更新的速度。但是在多數(shù)情況下 ,索引所帶來(lái)的數(shù)據(jù)檢索速度優(yōu)勢(shì)大大超過(guò)它的不足之處。
2. B+樹(shù)在數(shù)據(jù)庫(kù)索引中的應(yīng)用
目前大部分?jǐn)?shù)據(jù)庫(kù)系統(tǒng)及文件系統(tǒng)都采用B-Tree或其變種B+Tree作為索引結(jié)構(gòu)
1)在數(shù)據(jù)庫(kù)索引的應(yīng)用
在數(shù)據(jù)庫(kù)索引的應(yīng)用中,B+樹(shù)按照下列方式進(jìn)行組織 :
① 葉結(jié)點(diǎn)的組織方式 。B+樹(shù)的查找鍵 是數(shù)據(jù)文件的主鍵 ,且索引是稠密的。也就是說(shuō) ,葉結(jié)點(diǎn) 中為數(shù)據(jù)文件的第一個(gè)記錄設(shè)有一個(gè)鍵、指針對(duì) ,該數(shù)據(jù)文件可以按主鍵排序,也可以不按主鍵排序 ;數(shù)據(jù)文件按主鍵排序,且 B +樹(shù)是稀疏索引 , 在葉結(jié)點(diǎn)中為數(shù)據(jù)文件的每一個(gè)塊設(shè)有一個(gè)鍵、指針對(duì) ;數(shù)據(jù)文件不按鍵屬性排序 ,且該屬性是 B +樹(shù) 的查找鍵 , 葉結(jié)點(diǎn)中為數(shù)據(jù)文件里出現(xiàn)的每個(gè)屬性K設(shè)有一個(gè)鍵 、 指針對(duì) , 其中指針執(zhí)行排序鍵值為 K的 記錄中的第一個(gè)。
② 非葉結(jié)點(diǎn) 的組織方式。B+樹(shù) 中的非葉結(jié)點(diǎn)形成 了葉結(jié)點(diǎn)上的一個(gè)多級(jí)稀疏索引。 每個(gè)非葉結(jié)點(diǎn)中至少有ceil( m/2 ) 個(gè)指針 , 至多有 m 個(gè)指針 。
2)B+樹(shù)索引的插入和刪除
①在向數(shù)據(jù)庫(kù)中插入新的數(shù)據(jù)時(shí),同時(shí)也需要向數(shù)據(jù)庫(kù)索引中插入相應(yīng)的索引鍵值 ,則需要向 B+樹(shù) 中插入新的鍵值。即上面我們提到的B-樹(shù)插入算法。
②當(dāng)從數(shù)據(jù)庫(kù)中刪除數(shù)據(jù)時(shí),同時(shí)也需要從數(shù)據(jù)庫(kù)索引中刪除相應(yīng)的索引鍵值 ,則需要從 B+樹(shù) 中刪 除該鍵值 。即B-樹(shù)刪除算法
為什么使用B-Tree(B+Tree)
二叉查找樹(shù)進(jìn)化品種的紅黑樹(shù)等數(shù)據(jù)結(jié)構(gòu)也可以用來(lái)實(shí)現(xiàn)索引,但是文件系統(tǒng)及數(shù)據(jù)庫(kù)系統(tǒng)普遍采用B-/+Tree作為索引結(jié)構(gòu)。
一般來(lái)說(shuō),索引本身也很大,不可能全部存儲(chǔ)在內(nèi)存中,因此索引往往以索引文件的形式存儲(chǔ)的磁盤(pán)上。這樣的話,索引查找過(guò)程中就要產(chǎn)生磁盤(pán)I/O消耗,相對(duì)于內(nèi)存存取,I/O存取的消耗要高幾個(gè)數(shù)量級(jí),所以評(píng)價(jià)一個(gè)數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過(guò)程中磁盤(pán)I/O操作次數(shù)的漸進(jìn)復(fù)雜度。換句話說(shuō),索引的結(jié)構(gòu)組織要盡量減少查找過(guò)程中磁盤(pán)I/O的存取次數(shù)。為什么使用B-/+Tree,還跟磁盤(pán)存取原理有關(guān)。
局部性原理與磁盤(pán)預(yù)讀
由于存儲(chǔ)介質(zhì)的特性,磁盤(pán)本身存取就比主存慢很多,再加上機(jī)械運(yùn)動(dòng)耗費(fèi),磁盤(pán)的存取速度往往是主存的幾百分分之一,因此為了提高效率,要盡量減少磁盤(pán)I/O。為了達(dá)到這個(gè)目的,磁盤(pán)往往不是嚴(yán)格按需讀取,而是每次都會(huì)預(yù)讀,即使只需要一個(gè)字節(jié),磁盤(pán)也會(huì)從這個(gè)位置開(kāi)始,順序向后讀取一定長(zhǎng)度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理:
當(dāng)一個(gè)數(shù)據(jù)被用到時(shí),其附近的數(shù)據(jù)也通常會(huì)馬上被使用。
程序運(yùn)行期間所需要的數(shù)據(jù)通常比較集中。
由于磁盤(pán)順序讀取的效率很高(不需要尋道時(shí)間,只需很少的旋轉(zhuǎn)時(shí)間),因此對(duì)于具有局部性的程序來(lái)說(shuō),預(yù)讀可以提高I/O效率。
預(yù)讀的長(zhǎng)度一般為頁(yè)(page)的整倍數(shù)。頁(yè)是計(jì)算機(jī)管理存儲(chǔ)器的邏輯塊,硬件及操作系統(tǒng)往往將主存和磁盤(pán)存儲(chǔ)區(qū)分割為連續(xù)的大小相等的塊,每個(gè)存儲(chǔ)塊稱(chēng)為一頁(yè)(在許多操作系統(tǒng)中,頁(yè)得大小通常為4k),主存和磁盤(pán)以頁(yè)為單位交換數(shù)據(jù)。當(dāng)程序要讀取的數(shù)據(jù)不在主存中時(shí),會(huì)觸發(fā)一個(gè)缺頁(yè)異常,此時(shí)系統(tǒng)會(huì)向磁盤(pán)發(fā)出讀盤(pán)信號(hào),磁盤(pán)會(huì)找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁(yè)或幾頁(yè)載入內(nèi)存中,然后異常返回,程序繼續(xù)運(yùn)行。
我們上面分析B-/+Tree檢索一次最多需要訪問(wèn)節(jié)點(diǎn):
h =
數(shù)據(jù)庫(kù)系統(tǒng)巧妙利用了磁盤(pán)預(yù)讀原理,將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè),這樣每個(gè)節(jié)點(diǎn)只需要一次I/O就可以完全載入。為了達(dá)到這個(gè)目的,在實(shí)際實(shí)現(xiàn)B- Tree還需要使用如下技巧:
每次新建節(jié)點(diǎn)時(shí),直接申請(qǐng)一個(gè)頁(yè)的空間,這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁(yè)里,加之計(jì)算機(jī)存儲(chǔ)分配都是按頁(yè)對(duì)齊的,就實(shí)現(xiàn)了一個(gè)node只需一次I/O。
B-Tree中一次檢索最多需要h-1次I/O(根節(jié)點(diǎn)常駐內(nèi)存),漸進(jìn)復(fù)雜度為O(h)=O(logmN)。一般實(shí)際應(yīng)用中,m是非常大的數(shù)字,通常超過(guò)100,因此h非常?。ㄍǔ2怀^(guò)3)。
綜上所述,用B-Tree作為索引結(jié)構(gòu)效率是非常高的。
而紅黑樹(shù)這種結(jié)構(gòu),h明顯要深的多。由于邏輯上很近的節(jié)點(diǎn)(父子)物理上可能很遠(yuǎn),無(wú)法利用局部性,所以紅黑樹(shù)的I/O漸進(jìn)復(fù)雜度也為O(h),效率明顯比B-Tree差很多。
MySQL的B-Tree索引(技術(shù)上說(shuō)B+Tree)在 MySQL 中,主要有四種類(lèi)型的索引,分別為: B-Tree 索引, Hash 索引, Fulltext 索引和 R-Tree 索引。我們主要分析B-Tree 索引。
B-Tree 索引是 MySQL 數(shù)據(jù)庫(kù)中使用最為頻繁的索引類(lèi)型,除了 Archive 存儲(chǔ)引擎之外的其他所有的存儲(chǔ)引擎都支持 B-Tree 索引。Archive 引擎直到 MySQL 5.1 才支持索引,而且只支持索引單個(gè) AUTO_INCREMENT 列。
不僅僅在 MySQL 中是如此,實(shí)際上在其他的很多數(shù)據(jù)庫(kù)管理系統(tǒng)中B-Tree 索引也同樣是作為最主要的索引類(lèi)型,這主要是因?yàn)?B-Tree 索引的存儲(chǔ)結(jié)構(gòu)在數(shù)據(jù)庫(kù)的數(shù)據(jù)檢索中有非常優(yōu)異的表現(xiàn)。
一般來(lái)說(shuō), MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的結(jié)構(gòu)來(lái)存儲(chǔ)的,也就是所有實(shí)際需要的數(shù)據(jù)都存放于 Tree 的 Leaf Node(葉子節(jié)點(diǎn)) ,而且到任何一個(gè) Leaf Node 的最短路徑的長(zhǎng)度都是完全相同的,所以我們大家都稱(chēng)之為 B-Tree 索引。當(dāng)然,可能各種數(shù)據(jù)庫(kù)(或 MySQL 的各種存儲(chǔ)引擎)在存放自己的 B-Tree 索引的時(shí)候會(huì)對(duì)存儲(chǔ)結(jié)構(gòu)稍作改造。如 Innodb 存儲(chǔ)引擎的 B-Tree 索引實(shí)際使用的存儲(chǔ)結(jié)構(gòu)實(shí)際上是 B+Tree,也就是在 B-Tree 數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上做了很小的改造,在每一個(gè)Leaf Node 上面出了存放索引鍵的相關(guān)信息之外,還存儲(chǔ)了指向與該 Leaf Node 相鄰的后一個(gè) LeafNode 的指針信息(增加了順序訪問(wèn)指針),這主要是為了加快檢索多個(gè)相鄰 Leaf Node 的效率考慮。
下面主要討論MyISAM和InnoDB兩個(gè)存儲(chǔ)引擎的索引實(shí)現(xiàn)方式:
1. MyISAM索引實(shí)現(xiàn):1)主鍵索引:
MyISAM引擎使用B+Tree作為索引結(jié)構(gòu),葉節(jié)點(diǎn)的data域存放的是數(shù)據(jù)記錄的地址。下圖是MyISAM主鍵索引的原理圖:
(圖myisam1)
這里設(shè)表一共有三列,假設(shè)我們以Col1為主鍵,圖myisam1是一個(gè)MyISAM表的主索引(Primary key)示意??梢钥闯鯩yISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址。
2)輔助索引(Secondary key)
在MyISAM中,主索引和輔助索引(Secondary key)在結(jié)構(gòu)上沒(méi)有任何區(qū)別,只是主索引要求key是唯一的,而輔助索引的key可以重復(fù)。如果我們?cè)贑ol2上建立一個(gè)輔助索引,則此索引的結(jié)構(gòu)如下圖所示:
同樣也是一顆B+Tree,data域保存數(shù)據(jù)記錄的地址。因此,MyISAM中索引檢索的算法為首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,則取出其data域的值,然后以data域的值為地址,讀取相應(yīng)數(shù)據(jù)記錄。
MyISAM的索引方式也叫做“非聚集”的,之所以這么稱(chēng)呼是為了與InnoDB的聚集索引區(qū)分。
2. InnoDB索引實(shí)現(xiàn)然InnoDB也使用B+Tree作為索引結(jié)構(gòu),但具體實(shí)現(xiàn)方式卻與MyISAM截然不同.
1)主鍵索引:
MyISAM索引文件和數(shù)據(jù)文件是分離的,索引文件僅保存數(shù)據(jù)記錄的地址。而在InnoDB中,表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu),這棵樹(shù)的葉節(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄。這個(gè)索引的key是數(shù)據(jù)表的主鍵,因此InnoDB表數(shù)據(jù)文件本身就是主索引。
(圖inndb主鍵索引)
(圖inndb主鍵索引)是InnoDB主索引(同時(shí)也是數(shù)據(jù)文件)的示意圖,可以看到葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄。這種索引叫做聚集索引。因?yàn)镮nnoDB的數(shù)據(jù)文件本身要按主鍵聚集,所以InnoDB要求表必須有主鍵(MyISAM可以沒(méi)有),如果沒(méi)有顯式指定,則MySQL系統(tǒng)會(huì)自動(dòng)選擇一個(gè)可以唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵,如果不存在這種列,則MySQL自動(dòng)為InnoDB表生成一個(gè)隱含字段作為主鍵,這個(gè)字段長(zhǎng)度為6個(gè)字節(jié),類(lèi)型為長(zhǎng)整形。
2). InnoDB的輔助索引
InnoDB的所有輔助索引都引用主鍵作為data域。例如,下圖為定義在Col3上的一個(gè)輔助索引:
InnoDB 表是基于聚簇索引建立的。因此InnoDB 的索引能提供一種非??焖俚闹麈I查找性能。不過(guò),它的輔助索引(Secondary Index, 也就是非主鍵索引)也會(huì)包含主鍵列,所以,如果主鍵定義的比較大,其他索引也將很大。如果想在表上定義 、很多索引,則爭(zhēng)取盡量把主鍵定義得小一些。InnoDB 不會(huì)壓縮索引。
文字符的ASCII碼作為比較準(zhǔn)則。聚集索引這種實(shí)現(xiàn)方式使得按主鍵的搜索十分高效,但是輔助索引搜索需要檢索兩遍索引:首先檢索輔助索引獲得主鍵,然后用主鍵到主索引中檢索獲得記錄。
不同存儲(chǔ)引擎的索引實(shí)現(xiàn)方式對(duì)于正確使用和優(yōu)化索引都非常有幫助,例如知道了InnoDB的索引實(shí)現(xiàn)后,就很容易明白為什么不建議使用過(guò)長(zhǎng)的字段作為主鍵,因?yàn)樗休o助索引都引用主索引,過(guò)長(zhǎng)的主索引會(huì)令輔助索引變得過(guò)大。再例如,用非單調(diào)的字段作為主鍵在InnoDB中不是個(gè)好主意,因?yàn)镮nnoDB數(shù)據(jù)文件本身是一顆B+Tree,非單調(diào)的主鍵會(huì)造成在插入新記錄時(shí)數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整,十分低效,而使用自增字段作為主鍵則是一個(gè)很好的選擇。
InnoDB索引和MyISAM索引的區(qū)別:
一是主索引的區(qū)別,InnoDB的數(shù)據(jù)文件本身就是索引文件。而MyISAM的索引和數(shù)據(jù)是分開(kāi)的。
二是輔助索引的區(qū)別:InnoDB的輔助索引data域存儲(chǔ)相應(yīng)記錄主鍵的值而不是地址。而MyISAM的輔助索引和主索引沒(méi)有多大區(qū)別。
相關(guān)文章
Sql Server里刪除數(shù)據(jù)表中重復(fù)記錄的例子
這篇文章主要介紹了Sql Server里刪除數(shù)據(jù)表中重復(fù)記錄的例子,本文給出了3種操作方法,需要的朋友可以參考下2014-08-08SQL Server數(shù)據(jù)庫(kù)中的表名稱(chēng)、字段比較
這篇文章主要給大家介紹了關(guān)于SQl Server數(shù)據(jù)庫(kù)中表名稱(chēng)、字段比較的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家學(xué)習(xí)或者使用SQL Server具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09關(guān)于PowerDesigner初體驗(yàn)的使用介紹
本篇文章小編將為大家介紹,關(guān)于PowerDesigner初體驗(yàn)的使用介紹,有需要的朋友可以參考一下2013-04-04SQL?Server跨庫(kù)/服務(wù)器查詢(xún)及拓展知識(shí)點(diǎn)
因?yàn)闃I(yè)務(wù)要求,之前碰到需要跨服務(wù)器操作另一個(gè)數(shù)據(jù)庫(kù)的數(shù)據(jù),這里總結(jié)下,這篇文章主要給大家介紹了關(guān)于SQL?Server跨庫(kù)/服務(wù)器查詢(xún)及拓展知識(shí)點(diǎn)的相關(guān)資料,需要的朋友可以參考下2023-11-11SQLSERVER的排序問(wèn)題結(jié)果不是想要的
同一個(gè)查詢(xún)的結(jié)果集為什麼有時(shí)候是按他想要的順序排列,有時(shí)候又不是,接下來(lái)將為你詳細(xì)解答,感興趣的你可以參考下哈,希望對(duì)你有所幫助2013-03-03數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明備忘錄 線性表
線性表是線性結(jié)構(gòu)的抽象,線性結(jié)構(gòu)的特點(diǎn)是結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的線性關(guān)系。2010-03-03SQL?Server開(kāi)發(fā)智能提示插件SQL?Prompt介紹
這篇文章介紹了SQL?Server開(kāi)發(fā)智能提示插件SQL?Prompt,文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-05-05詳解partition by和group by對(duì)比
這篇文章主要介紹了詳解partition by和group by對(duì)比,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09