B-樹
1 .B-樹定義
B-樹是一種平衡的多路查找樹，它在文件系統(tǒng)中很有用。
定義：一棵m 階的B-樹，或者為空樹，或為滿足下列特性的m 叉樹：
⑴樹中每個結(jié)點至多有m 棵子樹；
⑵若根結(jié)點不是葉子結(jié)點，則至少有兩棵子樹；
⑶除根結(jié)點之外的所有非終端結(jié)點至少有[m/2] 棵子樹；
⑷所有的非終端結(jié)點中包含以下信息數(shù)據(jù)：
（n，A0，K1，A1，K2，…，Kn，An）
其中：Ki（i=1,2,…,n）為關(guān)鍵碼，且KiKi+1，
Ai 為指向子樹根結(jié)點的指針(i=0,1,…,n)，且指針Ai-1 所指子樹中所有結(jié)點的關(guān)鍵碼均小于Ki (i=1,2,…,n)，An 所指子樹中所有結(jié)點的關(guān)鍵碼均大于Kn.
n 
為關(guān)鍵碼的個數(shù)。
⑸所有的葉子結(jié)點都出現(xiàn)在同一層次上，并且不帶信息（可以看作是外部結(jié)點或查找失敗的結(jié)點，實際上這些結(jié)點不存在，指向這些結(jié)點的指針為空）。
即所有葉節(jié)點具有相同的深度，等于樹高度。
如一棵四階B-樹，其深度為4.
B-樹的查找類似二叉排序樹的查找，所不同的是B-樹每個結(jié)點上是多關(guān)鍵碼的有序表，在到達(dá)某個結(jié)點時，先在有序表中查找，若找到，則查找成功；否則，到按照對應(yīng)的指針信息指向的子樹中去查找，當(dāng)?shù)竭_(dá)葉子結(jié)點時，則說明樹中沒有對應(yīng)的關(guān)鍵碼。
在上圖的B-樹上查找關(guān)鍵字47的過程如下：
1）首先從更開始，根據(jù)根節(jié)點指針找到 *節(jié)點，因為 *a 節(jié)點中只有一個關(guān)鍵字，且給定值47 > 關(guān)鍵字35，則若存在必在指針A1所指的子樹內(nèi)。
2）順指針找到 *c節(jié)點，該節(jié)點有兩個關(guān)鍵字（43和 78），而43 47 78,若存在比在指針A1所指的子樹中。
3）同樣，順指針找到 *g節(jié)點，在該節(jié)點找到關(guān)鍵字47,查找成功。
2. 查找算法
復(fù)制代碼 代碼如下:
typedef int KeyType ;
#define m 5 /*B 樹的階，暫設(shè)為5*/
typedef struct Node{
int keynum; /* 結(jié)點中關(guān)鍵碼的個數(shù)，即結(jié)點的大小*/
struct Node *parent; /*指向雙親結(jié)點*/
KeyType key[m+1]; /*關(guān)鍵碼向量，0 號單元未用*/
struct Node *ptr[m+1]; /*子樹指針向量*/
Record *recptr[m+1]; /*記錄指針向量*/
}NodeType; /*B 樹結(jié)點類型*/
typedef struct{
NodeType *pt; /*指向找到的結(jié)點*/
int i; /*在結(jié)點中的關(guān)鍵碼序號，結(jié)點序號區(qū)間[1…m]*/
int tag; /* 1:查找成功，0:查找失敗*/
}Result; /*B 樹的查找結(jié)果類型*/
Result SearchBTree(NodeType *t,KeyType kx)
{
/*在m 階B 樹t 上查找關(guān)鍵碼kx，反回(pt,i,tag)。若查找成功，則特征值tag=1，*/
/*指針pt 所指結(jié)點中第i 個關(guān)鍵碼等于kx；否則，特征值tag=0,等于kx 的關(guān)鍵碼記錄*/
/*應(yīng)插入在指針pt 所指結(jié)點中第i 個和第i+1 個關(guān)鍵碼之間*/
p=t;q=NULL;found=FALSE;i=0; /*初始化，p 指向待查結(jié)點，q 指向p 的雙親*/
while(p!found)
{ n=p->keynum;i=Search(p,kx); /*在p-->key[1…keynum]中查找*/
if(i>0p->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- 樹查找算法分析
從查找算法中可以看出， 在B- 樹中進(jìn)行查找包含兩種基本操作:
( 1) 在B- 樹中查找結(jié)點；
( 2) 在結(jié)點中查找關(guān)鍵字。
由于B- 樹通常存儲在磁盤上， 則前一查找操作是在磁盤上進(jìn)行的， 而后一查找操作是在內(nèi)存中進(jìn)行的， 即在磁盤上找到指針p 所指結(jié)點后， 先將結(jié)點中的信息讀入內(nèi)存， 然后再利用順序查找或折半查找查詢等于K 的關(guān)鍵字。顯然， 在磁盤上進(jìn)行一次查找比在內(nèi)存中進(jìn)行一次查找的時間消耗多得多.
因此， 在磁盤上進(jìn)行查找的次數(shù)、即待查找關(guān)鍵字所在結(jié)點在B- 樹上的層次樹， 是決定B樹查找效率的首要因素
那么，對含有n 個關(guān)鍵碼的m 階B-樹，最壞情況下達(dá)到多深呢？可按二叉平衡樹進(jìn)行類似分析。首先，討論m 階B-數(shù)各層上的最少結(jié)點數(shù)。
由B樹定義：B樹包含n個關(guān)鍵字。因此有n+1個樹葉都在第J+1 層。
1）第一層為根，至少一個結(jié)點，根至少有兩個孩子，因此在第二層至少有兩個結(jié)點。
2）除根和樹葉外，其它結(jié)點至少有[m/2]個孩子,因此第三層至少有2*[m/2]個結(jié)點,在第四層至少有2*[m/2]2 個結(jié)點…
3）那么在第J+1層至少有2*[m/2]J-1個結(jié)點,而J+1層的結(jié)點為葉子結(jié)點,于是葉子結(jié)點的個數(shù)n+1。有：
也就是說在n個關(guān)鍵字的B樹查找，從根節(jié)點到關(guān)鍵字所在的節(jié)點所涉及的節(jié)點數(shù)不超過：
3.B-樹的插入
B-樹的生成也是從空樹起，逐個插入關(guān)鍵字而得。但由于B-樹結(jié)點中的關(guān)鍵字個數(shù)必須≥ceil(m／2)-1，因此，每次插入一個關(guān)鍵字不是在樹中添加一個葉子結(jié)點，而是首先在最低層的某個非終端結(jié)點中添加一個關(guān)鍵字，若該結(jié)點的關(guān)鍵字個數(shù)不超過m-1，則插入完成，否則要產(chǎn)生結(jié)點的“分裂”，
如圖（a） 為3階的B-樹(圖中略去F結(jié)點(即葉子結(jié)點))，假設(shè)需依次插入關(guān)鍵字30，26，85。
1) 首先通過查找確定插入的位置。由根*a 起進(jìn)行查找，確定30應(yīng)插入的在*d 節(jié)點中。由于*d 中關(guān)鍵字?jǐn)?shù)目不超過2（即m-1），故第一個關(guān)鍵字插入完成：如（b）
2) 同樣，通過查找確定關(guān)鍵字26亦應(yīng)插入 *d. 由于*d節(jié)點關(guān)鍵字?jǐn)?shù)目超過2，此時需要將 *d分裂成兩個節(jié)點，關(guān)鍵字26及其前、后兩個指針仍保留在 *d 節(jié)點中，而關(guān)鍵字37 及其前、后兩個指針存儲到新的產(chǎn)生的節(jié)點 *d` 中。同時將關(guān)鍵字30 和指示節(jié)點 *d `的指針插入到其雙親的節(jié)點中。由于 *b節(jié)點中的關(guān)鍵字?jǐn)?shù)目沒有超過2，則插入完成.如（c）(d)
3) (e) -(g) 為插入85后;
插入算法：
復(fù)制代碼 代碼如下:
int InserBTree(NodeType **t,KeyType kx,NodeType *q,int i){
/* 在m 階B 樹*t 上結(jié)點*q 的key[i],key[i+1]之間插入關(guān)鍵碼kx*/
/*若引起結(jié)點過大，則沿雙親鏈進(jìn)行必要的結(jié)點分裂調(diào)整，使*t仍為m 階B 樹*/
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->keynumm) finished=TRUE; /*插入完成*/
else
{ /*分裂結(jié)點*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é)點*ap*/
q=q->parent;
if(q) i=Search(q,kx); /*在雙親結(jié)點*q 中查找kx 的插入位置*/
}
}
if(!finished) /*(*t)是空樹或根結(jié)點已分裂為*q*和ap*/
NewRoot(t,q,x,ap); /*生成含信息(t,x,ap)的新的根結(jié)點*t,原*t 和ap 為子樹指針*/
}
4. B-樹的刪除
反之，若在B-樹上刪除一個關(guān)鍵字，則首先應(yīng)找到該關(guān)鍵字所在結(jié)點，并從中刪除之，若該結(jié)點為最下層的非終端結(jié)點，且其中的關(guān)鍵字?jǐn)?shù)目不少于ceil(m/2)，則刪除完成，否則要進(jìn)行“合并”結(jié)點的操作。假若所刪關(guān)鍵字為非終端結(jié)點中的Ki，則可以指針Ai所指子樹中的最小關(guān)鍵字Y替代Ki，然后在相應(yīng)的結(jié)點中刪去Y。例如，在下圖 圖4.1( a)的B-樹上刪去45，可以*f結(jié)點中的50替代45，然后在*f結(jié)點中刪去50。
圖4.1( a)
因此，下面我們可以只需討論刪除最下層非終端結(jié)點中的關(guān)鍵字的情形。有下列三種可能：
(1)被刪關(guān)鍵字所在結(jié)點中的關(guān)鍵字?jǐn)?shù)目不小于ceil(m/2)，則只需從該結(jié)點中刪去該關(guān)鍵字Ki和相應(yīng)指針Ai，樹的其它部分不變，例如，從圖 圖4.1( a)所示B-樹中刪去關(guān)鍵字12，刪除后的B-樹如圖 圖4.2( a)所示：
圖4.2( a)
(2)被刪關(guān)鍵字所在結(jié)點中的關(guān)鍵字?jǐn)?shù)目等于ceil(m/2)-1，而與該結(jié)點相鄰的右兄弟(或左兄弟)結(jié)點中的關(guān)鍵字?jǐn)?shù)目大于ceil(m/2)-1，則需將其兄弟結(jié)點中的最小(或最大)的關(guān)鍵字上移至雙親結(jié)點中，而將雙親結(jié)點中小于(或大于)且緊靠該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在結(jié)點中。
[例如]，從圖圖4.2( a)中刪去50，需將其右兄弟結(jié)點中的61上移至*e結(jié)點中，而將*e結(jié)點中的53移至*f，從而使*f和*g中關(guān)鍵字?jǐn)?shù)目均不小于ceil(m-1)-1，而雙親結(jié)點中的關(guān)鍵字?jǐn)?shù)目不變，如圖圖4.2(b)所示。
圖4.2(b)
(3)被刪關(guān)鍵字所在結(jié)點和其相鄰的兄弟結(jié)點中的關(guān)鍵字?jǐn)?shù)目均等于ceil(m/2)-1。假設(shè)該結(jié)點有右兄弟，且其右兄弟結(jié)點地址由雙親結(jié)點中的指針Ai所指，則在刪去關(guān)鍵字之后，它所在結(jié)點中剩余的關(guān)鍵字和指針，加上雙親結(jié)點中的關(guān)鍵字Ki一起，合并到 Ai所指兄弟結(jié)點中(若沒有右兄弟，則合并至左兄弟結(jié)點中)。
[例如]，從圖4.2(b)所示 B-樹中刪去53，則應(yīng)刪去*f結(jié)點，并將*f中的剩余信息(指針“空”)和雙親*e結(jié)點中的 61一起合并到右兄弟結(jié)點*g中。刪除后的樹如圖4.2(c)所示。
圖4.2(c)
如果因此使雙親結(jié)點中的關(guān)鍵字?jǐn)?shù)目小于ceil(m/2)-1，則依次類推。
[例如]，在 圖4.2(c)的B-樹中刪去關(guān)鍵字37之后，雙親b結(jié)點中剩余信息(“指針c”)應(yīng)和其雙親*a結(jié)點中關(guān)鍵字45一起合并至右兄弟結(jié)點*e中，刪除后的B-樹如圖 4.2(d)所示。
圖 4.2(d)
B-樹主要應(yīng)用在文件系統(tǒng)
為了將大型數(shù)據(jù)庫文件存儲在硬盤上 以減少訪問硬盤次數(shù)為目的 在此提出了一種平衡多路查找樹——B-樹結(jié)構(gòu) 由其性能分析可知它的檢索效率是相當(dāng)高的 為了提高 B-樹性能'還有很多種B-樹的變型，力圖對B-樹進(jìn)行改進(jìn)
B+樹 B+樹是應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種B-樹的變形樹。一棵m 階的B+樹和m 階的B-
樹的差異在于：
⑴有n 棵子樹的結(jié)點中含有n 個關(guān)鍵碼；
⑵所有的葉子結(jié)點中包含了全部關(guān)鍵碼的信息，及指向含有這些關(guān)鍵碼記錄的指針，且
葉子結(jié)點本身依關(guān)鍵碼的大小自小而大的順序鏈接。
⑶所有的非終端結(jié)點可以看成是索引部分，結(jié)點中僅含有其子樹根結(jié)點中最大（或最小）關(guān)鍵碼。
如圖一棵3階的B+樹:
通常在B+樹上有兩個頭指針，一個指向根節(jié)點，另一個指向關(guān)鍵字最小的葉子節(jié)點。因此可以對B+樹進(jìn)行兩種查找運算：一種是從最小關(guān)鍵字起順序查找，另一種是從根節(jié)點開始，進(jìn)行隨機(jī)查找。
在B+樹上進(jìn)行隨機(jī)查找、插入和刪除的過程基本上與B-樹類似。只是在查找時，若非終端結(jié)點上的關(guān)鍵碼等于給定值，并不終止，而是繼續(xù)向下直到葉子結(jié)點。因此，在B+
樹，不管查找成功與否，每次查找都是走了一條從根到葉子結(jié)點的路徑。
B+樹在數(shù)據(jù)庫中的應(yīng)用
1. 索引在數(shù)據(jù)庫中的作用
在數(shù)據(jù)庫系統(tǒng)的使用過程當(dāng)中，數(shù)據(jù)的查詢是使用最頻繁的一種數(shù)據(jù)操作。
最基本的查詢算法當(dāng)然是順序查找（linear search），遍歷表然后逐行匹配行值是否等于待查找的關(guān)鍵字，其時間復(fù)雜度為O（n）。但時間復(fù)雜度為O（n）的算法規(guī)模小的表，負(fù)載輕的數(shù)據(jù)庫，也能有好的性能。 但是數(shù)據(jù)增大的時候，時間復(fù)雜度為O（n）的算法顯然是糟糕的，性能就很快下降了。
好在計算機(jī)科學(xué)的發(fā)展提供了很多更優(yōu)秀的查找算法，例如二分查找（binary search）、二叉樹查找（binary tree search）等。如果稍微分析一下會發(fā)現(xiàn)，每種查找算法都只能應(yīng)用于特定的數(shù)據(jù)結(jié)構(gòu)之上，例如二分查找要求被檢索數(shù)據(jù)有序，而二叉樹查找只能應(yīng)用于二叉查找樹上，但是數(shù)據(jù)本身的組織結(jié)構(gòu)不可能完全滿足各種數(shù)據(jù)結(jié)構(gòu)（例如，理論上不可能同時將兩列都按順序進(jìn)行組織），所以，在數(shù)據(jù)之外，數(shù)據(jù)庫系統(tǒng)還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用（指向）數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實現(xiàn)高級查找算法。這種數(shù)據(jù)結(jié)構(gòu)，就是索引。
索引是對數(shù)據(jù)庫表 中一個或多個列的值進(jìn)行排序的結(jié)構(gòu)。與在表 中搜索所有的行相比，索引用指針 指向存儲在表中指定列的數(shù)據(jù)值，然后根據(jù)指定的次序排列這些指針，有助于更快地獲取信息。通常情 況下 ，只有當(dāng)經(jīng)常查詢索引列中的數(shù)據(jù)時 ，才需要在表上創(chuàng)建索引。索引將占用磁盤空間，并且影響數(shù) 據(jù)更新的速度。但是在多數(shù)情況下 ，索引所帶來的數(shù)據(jù)檢索速度優(yōu)勢大大超過它的不足之處。
2. B+樹在數(shù)據(jù)庫索引中的應(yīng)用
目前大部分?jǐn)?shù)據(jù)庫系統(tǒng)及文件系統(tǒng)都采用B-Tree或其變種B+Tree作為索引結(jié)構(gòu)
1）在數(shù)據(jù)庫索引的應(yīng)用
在數(shù)據(jù)庫索引的應(yīng)用中，B+樹按照下列方式進(jìn)行組織 ：
① 葉結(jié)點的組織方式 。B+樹的查找鍵 是數(shù)據(jù)文件的主鍵 ，且索引是稠密的。也就是說 ，葉結(jié)點 中為數(shù)據(jù)文件的第一個記錄設(shè)有一個鍵、指針對 ，該數(shù)據(jù)文件可以按主鍵排序，也可以不按主鍵排序 ；數(shù)據(jù)文件按主鍵排序，且 B +樹是稀疏索引 ， 在葉結(jié)點中為數(shù)據(jù)文件的每一個塊設(shè)有一個鍵、指針對 ；數(shù)據(jù)文件不按鍵屬性排序 ，且該屬性是 B +樹 的查找鍵 ， 葉結(jié)點中為數(shù)據(jù)文件里出現(xiàn)的每個屬性K設(shè)有一個鍵 、 指針對 ， 其中指針執(zhí)行排序鍵值為 K的 記錄中的第一個。
② 非葉結(jié)點 的組織方式。B+樹 中的非葉結(jié)點形成 了葉結(jié)點上的一個多級稀疏索引。 每個非葉結(jié)點中至少有ceil( m/2 ) 個指針 ， 至多有 m 個指針 。
2）B+樹索引的插入和刪除
①在向數(shù)據(jù)庫中插入新的數(shù)據(jù)時，同時也需要向數(shù)據(jù)庫索引中插入相應(yīng)的索引鍵值 ，則需要向 B+樹 中插入新的鍵值。即上面我們提到的B-樹插入算法。
②當(dāng)從數(shù)據(jù)庫中刪除數(shù)據(jù)時，同時也需要從數(shù)據(jù)庫索引中刪除相應(yīng)的索引鍵值 ，則需要從 B+樹 中刪 除該鍵值 。即B-樹刪除算法
為什么使用B-Tree（B+Tree）
二叉查找樹進(jìn)化品種的紅黑樹等數(shù)據(jù)結(jié)構(gòu)也可以用來實現(xiàn)索引，但是文件系統(tǒng)及數(shù)據(jù)庫系統(tǒng)普遍采用B-/+Tree作為索引結(jié)構(gòu)。
一般來說，索引本身也很大，不可能全部存儲在內(nèi)存中，因此索引往往以索引文件的形式存儲的磁盤上。這樣的話，索引查找過程中就要產(chǎn)生磁盤I/O消耗，相對于內(nèi)存存取，I/O存取的消耗要高幾個數(shù)量級，所以評價一個數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過程中磁盤I/O操作次數(shù)的漸進(jìn)復(fù)雜度。換句話說，索引的結(jié)構(gòu)組織要盡量減少查找過程中磁盤I/O的存取次數(shù)。為什么使用B-/+Tree，還跟磁盤存取原理有關(guān)。
局部性原理與磁盤預(yù)讀
由于存儲介質(zhì)的特性，磁盤本身存取就比主存慢很多，再加上機(jī)械運動耗費，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達(dá)到這個目的，磁盤往往不是嚴(yán)格按需讀取，而是每次都會預(yù)讀，即使只需要一個字節(jié)，磁盤也會從這個位置開始，順序向后讀取一定長度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計算機(jī)科學(xué)中著名的局部性原理：
當(dāng)一個數(shù)據(jù)被用到時，其附近的數(shù)據(jù)也通常會馬上被使用。
程序運行期間所需要的數(shù)據(jù)通常比較集中。
由于磁盤順序讀取的效率很高（不需要尋道時間，只需很少的旋轉(zhuǎn)時間），因此對于具有局部性的程序來說，預(yù)讀可以提高I/O效率。
預(yù)讀的長度一般為頁（page）的整倍數(shù)。頁是計算機(jī)管理存儲器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤存儲區(qū)分割為連續(xù)的大小相等的塊，每個存儲塊稱為一頁（在許多操作系統(tǒng)中，頁得大小通常為4k），主存和磁盤以頁為單位交換數(shù)據(jù)。當(dāng)程序要讀取的數(shù)據(jù)不在主存中時，會觸發(fā)一個缺頁異常，此時系統(tǒng)會向磁盤發(fā)出讀盤信號，磁盤會找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁或幾頁載入內(nèi)存中，然后異常返回，程序繼續(xù)運行。
我們上面分析B-/+Tree檢索一次最多需要訪問節(jié)點：
h =
數(shù)據(jù)庫系統(tǒng)巧妙利用了磁盤預(yù)讀原理，將一個節(jié)點的大小設(shè)為等于一個頁，這樣每個節(jié)點只需要一次I/O就可以完全載入。為了達(dá)到這個目的，在實際實現(xiàn)B- Tree還需要使用如下技巧：
每次新建節(jié)點時，直接申請一個頁的空間，這樣就保證一個節(jié)點物理上也存儲在一個頁里，加之計算機(jī)存儲分配都是按頁對齊的，就實現(xiàn)了一個node只需一次I/O。
B-Tree中一次檢索最多需要h-1次I/O（根節(jié)點常駐內(nèi)存），漸進(jìn)復(fù)雜度為O（h）=O（logmN）。一般實際應(yīng)用中，m是非常大的數(shù)字，通常超過100，因此h非常?。ㄍǔ２怀^3）。
綜上所述，用B-Tree作為索引結(jié)構(gòu)效率是非常高的。
而紅黑樹這種結(jié)構(gòu)，h明顯要深的多。由于邏輯上很近的節(jié)點（父子）物理上可能很遠(yuǎn)，無法利用局部性，所以紅黑樹的I/O漸進(jìn)復(fù)雜度也為O（h），效率明顯比B-Tree差很多。
MySQL的B-Tree索引（技術(shù)上說B+Tree）
在 MySQL 中，主要有四種類型的索引，分別為： B-Tree 索引， Hash 索引， Fulltext 索引和 R-Tree 索引。我們主要分析B-Tree 索引。
B-Tree 索引是 MySQL 數(shù)據(jù)庫中使用最為頻繁的索引類型，除了 Archive 存儲引擎之外的其他所有的存儲引擎都支持 B-Tree 索引。Archive 引擎直到 MySQL 5.1 才支持索引，而且只支持索引單個 AUTO_INCREMENT 列。
不僅僅在 MySQL 中是如此，實際上在其他的很多數(shù)據(jù)庫管理系統(tǒng)中B-Tree 索引也同樣是作為最主要的索引類型，這主要是因為 B-Tree 索引的存儲結(jié)構(gòu)在數(shù)據(jù)庫的數(shù)據(jù)檢索中有非常優(yōu)異的表現(xiàn)。
一般來說， MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的結(jié)構(gòu)來存儲的，也就是所有實際需要的數(shù)據(jù)都存放于 Tree 的 Leaf Node(葉子節(jié)點) ，而且到任何一個 Leaf Node 的最短路徑的長度都是完全相同的，所以我們大家都稱之為 B-Tree 索引。當(dāng)然，可能各種數(shù)據(jù)庫（或 MySQL 的各種存儲引擎）在存放自己的 B-Tree 索引的時候會對存儲結(jié)構(gòu)稍作改造。如 Innodb 存儲引擎的 B-Tree 索引實際使用的存儲結(jié)構(gòu)實際上是 B+Tree，也就是在 B-Tree 數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上做了很小的改造，在每一個Leaf Node 上面出了存放索引鍵的相關(guān)信息之外，還存儲了指向與該 Leaf Node 相鄰的后一個 LeafNode 的指針信息（增加了順序訪問指針），這主要是為了加快檢索多個相鄰 Leaf Node 的效率考慮。
下面主要討論MyISAM和InnoDB兩個存儲引擎的索引實現(xiàn)方式：
1. MyISAM索引實現(xiàn)：
1）主鍵索引：
MyISAM引擎使用B+Tree作為索引結(jié)構(gòu)，葉節(jié)點的data域存放的是數(shù)據(jù)記錄的地址。下圖是MyISAM主鍵索引的原理圖：
（圖myisam1）
這里設(shè)表一共有三列，假設(shè)我們以Col1為主鍵，圖myisam1是一個MyISAM表的主索引（Primary key）示意?？梢钥闯鯩yISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址。
2）輔助索引（Secondary key）
在MyISAM中，主索引和輔助索引（Secondary key）在結(jié)構(gòu)上沒有任何區(qū)別，只是主索引要求key是唯一的，而輔助索引的key可以重復(fù)。如果我們在Col2上建立一個輔助索引，則此索引的結(jié)構(gòu)如下圖所示：
同樣也是一顆B+Tree，data域保存數(shù)據(jù)記錄的地址。因此，MyISAM中索引檢索的算法為首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，則取出其data域的值，然后以data域的值為地址，讀取相應(yīng)數(shù)據(jù)記錄。
MyISAM的索引方式也叫做“非聚集”的，之所以這么稱呼是為了與InnoDB的聚集索引區(qū)分。
2. InnoDB索引實現(xiàn)
然InnoDB也使用B+Tree作為索引結(jié)構(gòu)，但具體實現(xiàn)方式卻與MyISAM截然不同.
1）主鍵索引：
MyISAM索引文件和數(shù)據(jù)文件是分離的，索引文件僅保存數(shù)據(jù)記錄的地址。而在InnoDB中，表數(shù)據(jù)文件本身就是按B+Tree組織的一個索引結(jié)構(gòu)，這棵樹的葉節(jié)點data域保存了完整的數(shù)據(jù)記錄。這個索引的key是數(shù)據(jù)表的主鍵，因此InnoDB表數(shù)據(jù)文件本身就是主索引。
(圖inndb主鍵索引）
(圖inndb主鍵索引）是InnoDB主索引（同時也是數(shù)據(jù)文件）的示意圖，可以看到葉節(jié)點包含了完整的數(shù)據(jù)記錄。這種索引叫做聚集索引。因為InnoDB的數(shù)據(jù)文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則MySQL系統(tǒng)會自動選擇一個可以唯一標(biāo)識數(shù)據(jù)記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個隱含字段作為主鍵，這個字段長度為6個字節(jié)，類型為長整形。
2）. InnoDB的輔助索引
InnoDB的所有輔助索引都引用主鍵作為data域。例如，下圖為定義在Col3上的一個輔助索引：
InnoDB 表是基于聚簇索引建立的。因此InnoDB 的索引能提供一種非?？焖俚闹麈I查找性能。不過，它的輔助索引（Secondary Index， 也就是非主鍵索引）也會包含主鍵列，所以，如果主鍵定義的比較大，其他索引也將很大。如果想在表上定義 、很多索引，則爭取盡量把主鍵定義得小一些。InnoDB 不會壓縮索引。
文字符的ASCII碼作為比較準(zhǔn)則。聚集索引這種實現(xiàn)方式使得按主鍵的搜索十分高效，但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄。
不同存儲引擎的索引實現(xiàn)方式對于正確使用和優(yōu)化索引都非常有幫助，例如知道了InnoDB的索引實現(xiàn)后，就很容易明白為什么不建議使用過長的字段作為主鍵，因為所有輔助索引都引用主索引，過長的主索引會令輔助索引變得過大。再例如，用非單調(diào)的字段作為主鍵在InnoDB中不是個好主意，因為InnoDB數(shù)據(jù)文件本身是一顆B+Tree，非單調(diào)的主鍵會造成在插入新記錄時數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整，十分低效，而使用自增字段作為主鍵則是一個很好的選擇。
InnoDB索引和MyISAM索引的區(qū)別：
一是主索引的區(qū)別，InnoDB的數(shù)據(jù)文件本身就是索引文件。而MyISAM的索引和數(shù)據(jù)是分開的。
二是輔助索引的區(qū)別：InnoDB的輔助索引data域存儲相應(yīng)記錄主鍵的值而不是地址。而MyISAM的輔助索引和主索引沒有多大區(qū)別。
您可能感興趣的文章:- B-Tree的性質(zhì)介紹
- MySQL Hash索引和B-Tree索引的區(qū)別
- SQLite中的B-Tree實現(xiàn)細(xì)節(jié)分析
- bitmap 索引和 B-tree 索引在使用中如何選擇
- B-樹的插入過程介紹
- 淺談MySQL的B樹索引與索引優(yōu)化小結(jié)
- 完整B樹算法Java實現(xiàn)代碼
- c語言B樹深入理解
- B-樹的刪除過程介紹
