基於B-樹和B+樹的應用：數據搜刮和數據庫索引的具體引見。本站提示廣大學習愛好者：（基於B-樹和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<Ki+1，
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 的拔出地位信息*/
}
B- 樹查找算法剖析
從查找算法中可以看出， 在B- 樹中停止查找包括兩種根本操作:
( 1) 在B- 樹中查找結點；
( 2) 在結點中查找症結字。
因為B- 樹平日存儲在磁盤上， 則前一查找操作是在磁盤長進行的， 爾後一查找操作是在內存中停止的， 即在磁盤上找到指針p 所指結點後， 先將結點中的信息讀入內存， 然後再應用次序查找或折半查找查詢等於K 的症結字。明顯， 在磁盤長進行一次查找比在內存中停止一次查找的時光消費多很多.
是以， 在磁盤長進行查找的次數、即待查找症結字地點結點在B- 樹上的條理樹， 是決議B樹查找效力的重要身分
那末，對含有n 個症結碼的m 階B-樹，最壞情形下到達多深呢？可按二叉均衡樹停止相似剖析。起首，評論辯論m 階B-數各層上的起碼結點數。
由B樹界說：B樹包括n個症結字。是以有n+1個樹葉都在第J+1 層。
1）第一層為根，至多一個結點，根至多有兩個孩子，是以在第二層至多有兩個結點。
2）除根和樹葉外，其它結點至多有[m/2]個孩子,是以第三層至多有2*[m/2]個結點,在第四層至多有2*[m/2]2 個結點…
3）那末在第J+1層至多有2*[m/2]J-1個結點,而J+1層的結點為葉子結點,因而葉子結點的個數n+1。有：
也就是說在n個症結字的B樹查找，從根節點到症結字地點的節點所觸及的節點數不跨越：
3.B-樹的拔出
B-樹的生成也是從空樹起，逐一拔出症結字而得。但因為B-樹結點中的症結字個數必需≥ceil(m／2)-1，是以，每次拔出一個症結字不是在樹中添加一個葉子結點，而是起首在最低層的某個非終端結點中添加一個症結字，若該結點的症結字個數不跨越m-1，則拔出完成，不然要發生結點的“決裂”，
如圖（a） 為3階的B-樹(圖中略去F結點(即葉子結點))，假定需順次拔出症結字30，26，85。
1) 起首經由過程查找肯定拔出的地位。由根*a 起停止查找，肯定30應拔出的在*d 節點中。因為*d 中症結字數量不跨越2（即m-1），故第一個症結字拔出完成：如（b）
2) 異樣，經由過程查找肯定症結字26亦應拔出 *d. 因為*d節點症結字數量跨越2，此時須要將 *d決裂成兩個節點，症結字26及其前、後兩個指針仍保存在 *d 節點中，而症結字37 及其前、後兩個指針存儲到新的發生的節點 *d` 中。同時將症結字30 和指導節點 *d `的指針拔出到其雙親的節點中。因為 *b節點中的症結字數量沒有跨越2，則拔出完成.如（c）(d)
3) (e) -(g) 為拔出85後;
拔出算法：
int InserBTree(NodeType **t,KeyType kx,NodeType *q,int i){
/* 在m 階B 樹*t 上結點*q 的key[i],key[i+1]之間拔出症結碼kx*/
/*若惹起結點過年夜，則沿雙親鏈停止需要的結點決裂調劑，使*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->keynum<m) finished=TRUE; /*拔出完成*/
else
{ /*決裂結點*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]移入新結點*ap*/
q=q->parent;
if(q) i=Search(q,kx); /*在雙親結點*q 中查找kx 的拔出地位*/
}
}
if(!finished) /*(*t)是空樹或根結點已決裂為*q*和ap*/
NewRoot(t,q,x,ap); /*生成含信息(t,x,ap)的新的根結點*t,原*t 和ap 為子樹指針*/
}
4. B-樹的刪除
反之，若在B-樹上刪除一個症結字，則起首應找到該症結字地點結點，並從中刪除之，若該結點為最基層的非終端結點，且個中的症結字數量很多於ceil(m/2)，則刪除完成，不然要停止“歸並”結點的操作。假若所刪症結字為非終端結點中的Ki，則可以指針Ai所指子樹中的最小症結字Y替換Ki，然後在響應的結點中刪去Y。例如，鄙人圖 圖4.1( a)的B-樹上刪去45，可以*f結點中的50替換45，然後在*f結點中刪去50。
圖4.1( a)
是以，上面我們可以只需評論辯論刪除最基層非終端結點中的症結字的情況。有以下三種能夠：
(1)被刪症結字地點結點中的症結字數量不小於ceil(m/2)，則只需從該結點中刪去該症結字Ki和響應指針Ai，樹的其它部門不變，例如，從圖 圖4.1( a)所示B-樹中刪去症結字12，刪除後的B-樹如圖 圖4.2( a)所示：
圖4.2( a)
(2)被刪症結字地點結點中的症結字數量等於ceil(m/2)-1，而與該結點相鄰的右兄弟(或左兄弟)結點中的症結字數量年夜於ceil(m/2)-1，則需將其兄弟結點中的最小(或最年夜)的症結字上移至雙親結點中，而將雙親結點中小於(或年夜於)且緊靠該上移症結字的症結字下移至被刪症結字地點結點中。
[例如]，從圖圖4.2( a)中刪去50，需將其右兄弟結點中的61上移至*e結點中，而將*e結點中的53移至*f，從而使*f和*g中症結字數量均不小於ceil(m-1)-1，而雙親結點中的症結字數量不變，如圖圖4.2(b)所示。
圖4.2(b)
(3)被刪症結字地點結點和其相鄰的兄弟結點中的症結字數量均等於ceil(m/2)-1。假定該結點有右兄弟，且其右兄弟結點地址由雙親結點中的指針Ai所指，則在刪去症結字以後，它地點結點中殘剩的症結字和指針，加上雙親結點中的症結字Ki一路，歸並到 Ai所指兄弟結點中(若沒有右兄弟，則歸並至左兄弟結點中)。
[例如]，從圖4.2(b)所示 B-樹中刪去53，則應刪去*f結點，並將*f中的殘剩信息(指針“空”)和雙親*e結點中的 61一路歸並到右兄弟結點*g中。刪除後的樹如圖4.2(c)所示。
圖4.2(c)
假如是以使雙親結點中的症結字數量小於ceil(m/2)-1，則順次類推。
[例如]，在 圖4.2(c)的B-樹中刪去症結字37以後，雙親b結點中殘剩信息(“指針c”)應和其雙親*a結點中症結字45一路歸並至右兄弟結點*e中，刪除後的B-樹如圖 4.2(d)所示。 
圖 4.2(d)
B-樹重要運用在文件體系
為了將年夜型數據庫文件存儲在硬盤上 以削減拜訪硬盤次數為目標 在此提出了一種均衡多路查找樹——B-樹構造 由其機能剖析可知它的檢索效力是相當高的 為了進步 B-樹機能'還有許多種B-樹的變型，力爭對B-樹停止改良
1. 索引在數據庫中的感化
在數據庫體系的應用進程傍邊，數據的查詢是應用最頻仍的一種數據操作。
最根本的查詢算法固然是次序查找（linear search），遍歷表然後逐行婚配行值能否等於待查找的症結字，當時間龐雜度為O（n）。但時光龐雜度為O（n）的算律例模小的表，負載輕的數據庫，也能有好的機能。 然則數據增年夜的時刻，時光龐雜度為O（n）的算法明顯是蹩腳的，機能就很快降低了。
好在盤算機迷信的成長供給了許多更優良的查找算法，例如二分查找（binary search）、二叉樹查找（binary tree search）等。假如略微剖析一下會發明，每種查找算法都只能運用於特定的數據構造之上，例如二分查找請求被檢索數據有序，而二叉樹查找只能運用於二叉查找樹上，然則數據自己的組織構造弗成能完整知足各類數據構造（例如，實際上弗成能同時將兩列都按次序停止組織），所以，在數據以外，數據庫體系還保護著知足特定查找算法的數據構造，這些數據構造以某種方法援用（指向）數據，如許便可以在這些數據構造上完成高等查找算法。這類數據構造，就是索引。
索引是對數據庫表 中一個或多個列的值停止排序的構造。與在表 中搜刮一切的行比擬，索援用指針 指向存儲在表中指定列的數據值，然後依據指定的順序分列這些指針，有助於更快地獲得信息。平日情 況下 ，只要當常常查詢索引列中的數據時 ，才須要在表上創立索引。索引將占用磁盤空間，而且影響數 據更新的速度。然則在多半情形下 ，索引所帶來的數據檢索速度優勢年夜年夜跨越它的缺乏的地方。
2. B+樹在數據庫索引中的運用
今朝年夜部門數據庫體系及文件體系都采取B-Tree或其變種B+Tree作為索引構造
1）在數據庫索引的運用
在數據庫索引的運用中，B+樹依照以下方法停止組織 ：
① 葉結點的組織方法 。B+樹的查找鍵 是數據文件的主鍵 ，且索引是濃密的。也就是說 ，葉結點 中為數據文件的第一個記載設有一個鍵、指針對 ，該數據文件可以按主鍵排序，也能夠不按主鍵排序 ；數據文件按主鍵排序，且 B +樹是稀少索引 ， 在葉結點中為數據文件的每個塊設有一個鍵、指針對 ；數據文件不按鍵屬性排序 ，且該屬性是 B +樹 的查找鍵 ， 葉結點中為數據文件裡湧現的每一個屬性K設有一個鍵 、 指針對 ， 個中指針履行排序鍵值為 K的 記載中的第一個。
② 非葉結點 的組織方法。B+樹 中的非葉結點構成 了葉結點上的一個多級稀少索引。 每一個非葉結點中至多有ceil( m/2 ) 個指針 ， 至少有 m 個指針 。
2）B+樹索引的拔出和刪除
①在向數據庫中拔出新的數據時，同時也須要向數據庫索引中拔出響應的索引鍵值 ，則須要向 B+樹 中拔出新的鍵值。即下面我們提到的B-樹拔出算法。
②當從數據庫中刪除數據時，同時也須要從數據庫索引中刪除響應的索引鍵值 ，則須要從 B+樹 中刪 除該鍵值 。即B-樹刪除算法
為何應用B-Tree（B+Tree）
二叉查找樹退化種類的紅黑樹等數據構造也能夠用來完成索引，然則文件體系及數據庫體系廣泛采取B-/+Tree作為索引構造。
普通來講，索引自己也很年夜，弗成能全體存儲在內存中，是以索引常常以索引文件的情勢存儲的磁盤上。如許的話，索引查找進程中就要發生磁盤I/O消費，絕對於內存存取，I/O存取的消費要高幾個數目級，所以評價一個數據構造作為索引的好壞最主要的目標就是在查找進程中磁盤I/O操作次數的漸進龐雜度。換句話說，索引的構造組織要盡可能削減查找進程中磁盤I/O的存取次數。為何應用B-/+Tree，還跟磁盤存取道理有關。
部分性道理與磁盤預讀
因為存儲介質的特征，磁盤自己存取就比主存慢許多，再加上機械活動消耗，磁盤的存取速度常常是主存的幾百分分之一，是以為了進步效力，要盡可能削減磁盤I/O。為了到達這個目標，磁盤常常不是嚴厲按需讀取，而是每次都邑預讀，即便只須要一個字節，磁盤也會從這個地位開端，次序向後讀取必定長度的數據放入內存。如許做的實際根據是盤算機迷信中有名的部分性道理：
當一個數據被用到時，其鄰近的數據也平日會立時被應用。
法式運轉時代所須要的數據平日比擬集中。
因為磁盤次序讀取的效力很高（不須要尋道時光，只需很少的扭轉時光），是以關於具有部分性的法式來講，預讀可以進步I/O效力。
預讀的長度普通為頁（page）的整倍數。頁是盤算機治理存儲器的邏輯塊，硬件及操作體系常常將主存和磁盤存儲辨別割為持續的年夜小相等的塊，每一個存儲塊稱為一頁（在很多操作體系中，頁得年夜小平日為4k），主存和磁盤以頁為單元交流數據。當法式要讀取的數據不在主存中時，會觸發一個缺頁異常，此時體系會向磁盤收回讀盤旌旗燈號，磁盤會找到數據的肇端地位並向後持續讀取一頁或幾頁載入內存中，然後異常前往，法式持續運轉。
我們下面剖析B-/+Tree檢索一次最多須要拜訪節點：
h =
數據庫體系奇妙應用了磁盤預讀道理，將一個節點的年夜小設為等於一個頁，如許每一個節點只須要一次I/O便可以完整載入。為了到達這個目標，在現實完成B- Tree還須要應用以下技能：
每次新建節點時，直接請求一個頁的空間，如許就包管一個節點物理上也存儲在一個頁裡，加上盤算機存儲分派都是按頁對齊的，就完成了一個node只需一次I/O。
B-Tree中一次檢索最多須要h-1次I/O（根節點常駐內存），漸進龐雜度為O（h）=O（logmN）。普通現實運用中，m長短常年夜的數字，平日跨越100，是以h異常小（平日不跨越3）。
綜上所述，用B-Tree作為索引構造效力長短常高的。
而紅黑樹這類構造，h顯著要深的多。因為邏輯上很近的節點（父子）物理上能夠很遠，沒法應用部分性，所以紅黑樹的I/O漸進龐雜度也為O（h），效力顯著比B-Tree差許多。
MySQL的B-Tree索引（技巧上說B+Tree）在 MySQL 中，重要有四品種型的索引，分離為： B-Tree 索引， Hash 索引， Fulltext 索引和 R-Tree 索引。我們重要剖析B-Tree 索引。
B-Tree 索引是 MySQL 數據庫中應用最為頻仍的索引類型，除 Archive 存儲引擎以外的其他一切的存儲引擎都支撐 B-Tree 索引。Archive 引擎直到 MySQL 5.1 才支撐索引，並且只支撐索引單個 AUTO_INCREMENT 列。
不只僅在 MySQL 中是如斯，現實上在其他的許多數據庫治理體系中B-Tree 索引也異樣是作為最重要的索引類型，這重要是由於 B-Tree 索引的存儲構造在數據庫的數據檢索中有異常優良的表示。
普通來講， MySQL 中的 B-Tree 索引的物理文件年夜多都是以 Balance Tree 的構造來存儲的，也就是一切現實須要的數據都寄存於 Tree 的 Leaf Node(葉子節點) ，並且就任何一個 Leaf Node 的最短途徑的長度都是完整雷同的，所以我們年夜家都稱之為 B-Tree 索引。固然，能夠各類數據庫（或 MySQL 的各類存儲引擎）在寄存本身的 B-Tree 索引的時刻會對存儲構造稍作改革。如 Innodb 存儲引擎的 B-Tree 索引現實應用的存儲構造現實上是 B+Tree，也就是在 B-Tree 數據構造的基本上做了很小的改革，在每個Leaf Node 下面出了寄存索引鍵的相干信息以外，還存儲了指向與該 Leaf Node 相鄰的後一個 LeafNode 的指針信息（增長了次序拜訪指針），這重要是為了加速檢索多個相鄰 Leaf Node 的效力斟酌。
上面重要評論辯論MyISAM和InnoDB兩個存儲引擎的索引完成方法：
1. MyISAM索引完成：1）主鍵索引：
MyISAM引擎應用B+Tree作為索引構造，葉節點的data域寄存的是數據記載的地址。下圖是MyISAM主鍵索引的道理圖：
（圖myisam1）
這裡設表一共有三列，假定我們以Col1為主鍵，圖myisam1是一個MyISAM表的主索引（Primary key）表示。可以看出MyISAM的索引文件僅僅保留數據記載的地址。
2）幫助索引（Secondary key）
在MyISAM中，主索引和幫助索引（Secondary key）在構造上沒有任何差別，只是主索引請求key是獨一的，而幫助索引的key可以反復。假如我們在Col2上樹立一個幫助索引，則此索引的構造以下圖所示：
異樣也是一顆B+Tree，data域保留數據記載的地址。是以，MyISAM中索引檢索的算法為起首依照B+Tree搜刮算法搜刮索引，假如指定的Key存在，則掏出其data域的值，然後以data域的值為地址，讀取響應數據記載。
MyISAM的索引方法也叫做“非集合”的，之所以這麼稱謂是為了與InnoDB的集合索引辨別。
2. InnoDB索引完成然InnoDB也應用B+Tree作為索引構造，但詳細完成方法卻與MyISAM判然不同.
1）主鍵索引：
MyISAM索引文件和數據文件是分別的，索引文件僅保留數據記載的地址。而在InnoDB中，表數據文件自己就是按B+Tree組織的一個索引構造，這棵樹的葉節點data域保留了完全的數據記載。這個索引的key是數據表的主鍵，是以InnoDB表數據文件自己就是主索引。
(圖inndb主鍵索引）
(圖inndb主鍵索引）是InnoDB主索引（同時也是數據文件）的表示圖，可以看到葉節點包括了完全的數據記載。這類索引叫做集合索引。由於InnoDB的數據文件自己要按主鍵集合，所以InnoDB請求表必需有主鍵（MyISAM可以沒有），假如沒有顯式指定，則MySQL體系會主動選擇一個可以獨一標識數據記載的列作為主鍵，假如不存在這類列，則MySQL主動為InnoDB表生成一個隱含字段作為主鍵，這個字段長度為6個字節，類型為長整形。
2）. InnoDB的幫助索引
InnoDB的一切幫助索引都援用主鍵作為data域。例如，下圖為界說在Col3上的一個幫助索引：
InnoDB 表是基於聚簇索引樹立的。是以InnoDB 的索引能供給一種異常疾速的主鍵查找機能。不外，它的幫助索引（Secondary Index， 也就長短主鍵索引）也會包括主鍵列，所以，假如主鍵界說的比擬年夜，其他索引也將很年夜。假如想在表上界說 、許多索引，則爭奪盡可能把主鍵界說得小一些。InnoDB 不會緊縮索引。
文字符的ASCII碼作為比擬原則。集合索引這類完成方法使得按主鍵的搜刮非常高效，然則幫助索引搜刮須要檢索兩遍索引：起首檢索幫助索引取得主鍵，然後用主鍵到主索引中檢索取得記載。
分歧存儲引擎的索引完成方法關於准確應用和優化索引都異常有贊助，例如曉得了InnoDB的索引完成後，就很輕易明確為何不建議應用太長的字段作為主鍵，由於一切幫助索引都援用主索引，太長的主索引會令幫助索引變得過年夜。再例如，用非單調的字段作為主鍵在InnoDB中不是個好主張，由於InnoDB數據文件自己是一顆B+Tree，非單調的主鍵會形成在拔出新記載時數據文件為了保持B+Tree的特征而頻仍的決裂調劑，非常低效，而應用自增字段作為主鍵則是一個很好的選擇。
InnoDB索引和MyISAM索引的差別：
一是主索引的差別，InnoDB的數據文件自己就是索引文件。而MyISAM的索引和數據是離開的。
二是幫助索引的差別：InnoDB的幫助索引data域存儲響應記載主鍵的值而不是地址。而MyISAM的幫助索引和主索引沒有多年夜差別。
