B+樹在mysql資料庫索引中的使用

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

定義：一棵m 階的B-樹，或者為空樹，或為滿足下列特性的m 叉樹：

⑴樹中每個結點至多有m 棵子樹。

⑵若根結點不是葉子結點，則至少有兩棵子樹。

⑶除根結點之外的所有非葉結點至少有[m/2] 棵子樹；

⑷所有的非終端結點中包含以下資訊資料：（n，A0，K1，A1，K2，…，Kn，An）

其中：n 為關鍵碼的個數，Ki（i=1,2,…,n）為關鍵碼且Ki<Ki+1，Ai 為指向子樹根結點的指針(i=0,1,…,n)，且指針Ai-1 所指子樹中所有結點的關鍵碼均小于Ki大于Ki-1。

⑸所有的葉子結點都出現在同一層次上，并且不帶資訊（實際上這些結點不存在，指向這些結點的指針為空）。即所有葉節點具有相同的深度，等于樹高度。

如一棵四階B-樹，其深度為4，如下圖：

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

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

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

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

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

二：B+樹是應檔案系統所需而産生的一種B-樹的變形樹。

一棵m階的B+樹和m階的B-樹的差異在于：

⑴ 有n 棵子樹的結點中含有n 個關鍵碼；

⑵所有的葉子結點中包含了全部關鍵碼的資訊，及指向含有這些關鍵碼記錄的指針，且 葉子結點本身依關鍵碼的大小自小而大組成順序連結清單。

⑶在B+樹上進行随機查找、插入和删除的過程基本上與B-樹類似。 隻是在查找時，若非葉結點上的關鍵碼等于給定值，也并不終止，而是繼續向下直到葉子結點。是以，在B+樹中，不管查找成功與否，每次查找都是走了一條從根節點到葉子結點的路徑。

如圖一棵3階的B+樹： 通常在B+樹上有兩個頭指針，一個指向根節點，另一個指向關鍵字最小的葉子節點。是以可以對B+樹進行兩種查找運算：一種是從最小關鍵字起順序查找，另一種是從根節點開始，進行随機查找。

三：下面來介紹B+樹在資料庫索引中的典型應用。

資料庫索引常用B+樹來實作。 資料庫索引分為聚集索引（也叫聚簇索引）和非聚集索引（非聚簇索引）兩種類型。

InnoDB引擎使用的是聚集索引。所謂 聚集索引：就是B+樹的葉子節點的data域中存放的是完整的資料記錄。

對于聚集索引，按照B+樹中關鍵字的不同分為主鍵索引和輔助索引。使用主鍵屬性作為B+樹的關鍵字就是主鍵索引，使用非主鍵屬性作為B+樹的關鍵字就是輔助索引。如下圖：

上圖是InnoDB主鍵索引

上圖是InnoDB輔助索引

聚集索引這種實作方式使得按主鍵的搜尋十分高效，但是輔助索引搜尋需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然後用主鍵到主索引中檢索獲得記錄。從上面的資料結構也可以了解，用來做索引的屬性列的字段越短性能越好。

MyISAM引擎使用的是非聚集索引。所謂 非聚集索引：就是B+樹的葉子節點的data域中存放的是資料記錄的位址。按照B+樹中關鍵字的不同也可以分為主鍵索引和輔助索引。如圖所示：

上圖是MyISAM主鍵索引

上圖是MyISAM輔助索引

InnoDB索引和MyISAM索引的差別：

1) InnoDB是聚集索引，B+樹的葉子節點的data域中儲存的是完整的資料記錄。MyISAM是非聚集索引，B+樹的葉子節點的data域中儲存的是資料記錄的位址。

2) InnoDB的輔助索引中，B+樹的葉子節點的data域中儲存的是對應的主鍵，是以在InnoDB中使用輔助索引需要兩邊檢索。而對于MyISAM索引，無論是主鍵索引還是輔助索引對需要一次檢索即可。

3）     對于聚集索引，因為它的主鍵索引的data域中存儲的是完整的行資訊，是以不會再單獨存儲行資訊，這也是它的輔助索引的data域中存儲的是主鍵值的原因。對于非聚集索引，它的主鍵索引和輔助索引的data域中存儲的都是行資訊的位址，是以需要單獨的空間來存儲行資訊。如下圖：

B-Tree索引适用于全鍵值，鍵值或字首查找。其中鍵字首查找隻适用于根據最字首的查找。前面所述的索引對如下類型的查詢有效：

1. 全值比對：全值比對指的是和索引中的所有列進行比對。

2. 比對最左字首：即僅僅比對索引的最左側列。

3. 比對最左字首的一部分：即僅僅比對索引的最左側列的一部分。

4. 比對範圍值：指定索引的最左側列的範圍。

5. 精确比對前幾列并範圍比對後一列

将上面的叙述總結起來，可以歸納出B-Tree索引的限制：

1. 如果不是按照索引的最左列開始查找，則無法使用索引。

2. 查詢時不能跳過索引中的列。

3. 如果查詢中有某個列的範圍查詢，則其右邊所有的列都無法使用索引優化查找。

讀者應該明白，索引列的順序是很重要的，在性能優化的時候，可以建立相同的列但順序不同的索引來滿足不同的需求。

• 

• 大小: 24.4 KB

• 

• 大小: 20.5 KB

• 

• 大小: 19.5 KB

• 

• 大小: 42.6 KB

• 

• 大小: 43 KB

• 

• 大小: 24.8 KB

• 

• 大小: 96.9 KB

• 檢視圖檔附件