MySQL中B樹索引和B+樹索引的差別是什麼

如果用樹作為索引的資料結構，每查找一次資料就會從磁碟中讀取樹的一個節點，也就是一頁，而二元樹的每個節點只儲存一條數據，並不能填滿一頁的儲存空間，那多餘的儲存空間豈不是要浪費了？為了解決一個二元平衡搜尋樹的這個弊端，我們應該尋找一個單一節點可以儲存更多資料的資料結構，也就是多路搜尋樹。

1. 多路搜尋樹

1、完全二元樹高度：O(log2N)，其中2為對數，樹每層的節點數；

2、完全M路搜尋樹的高度：O(logmN)，其中M為對數，樹每層的節點數；

M路搜尋樹適用於儲存資料量過大無法一次載入到記憶體的場景。透過增加每層節點的數量和在每個節點存放更多的數據來在一層中存放更多的數據，從而降低樹的高度，在數據查找時減少磁碟存取次數。

因此，如果每個節點包含的關鍵字數量和每層的節點數量增加，則樹的高度將減少。儘管每個節點的資料確定會更加耗時，但B樹的關注點在於解決磁碟效能瓶頸，因此單一節點搜尋資料的成本可以被忽略。

2. B樹-多路平衡搜尋樹

B樹是一種M路搜尋樹，B樹主要用於解決M路搜尋樹的不平衡導致樹的高度變高，跟二元樹退化為鍊錶導致效能問題一樣。 B樹透過對每層的節點進行控制、調整，如節點分離，節點合併，一層滿時向上分裂父節點來增加新的層等操作來確保該M路搜索樹的平衡。

在B樹中，每個節點都是一個磁碟區塊（頁），而階數或說路數M則規定了節點中最多的子節點數量。每個非葉子節點存放了關鍵字和指向兒子樹的指針，具體數量為：M階的B樹，每個非葉子節點存放了M-1個關鍵字和M個指向子樹的指針。如圖為5階B樹結構的示意圖：

3. B樹索引

先建立一個user表：

create table user(
	id int,
	name varchar,
	primary key(id)
) ROW_FORMAT=COMPACT;

假如我們使用B樹對錶中的使用者記錄建立索引：

B樹的每個節點佔用一個磁碟區塊，磁碟區塊也就是頁，從上圖可以看出，B樹相對於平衡二元樹，每個節點儲存了更多的主鍵key和資料data，並且每個節點擁有了更多的子節點，子節點的個數一般稱為階，上述圖中的B樹為3階B樹，高度也會降低。假如我們要找id=28的用戶訊息，那麼查找流程如下：

#1、根據根節點找到頁1，讀入記憶體。 【磁碟I/O操作第1次】

2、比較鍵值28在區間（17,35），找到頁1的指標p2；

3、根據p2指標找到頁3，讀入記憶體。 【磁碟I/O操作第2次】

4、比較鍵值28在區間（26,35），找到頁3的指標p2。

5、根據p2指標找到頁8，讀入記憶體。 【磁碟I/O操作第3次】

6、在頁8中的鍵值清單中找到鍵值28，鍵值對應的使用者資訊為(28,po)；

B-Tree相對於AVLTree縮減了節點個數，使每次磁碟I/O取到記憶體的資料都發揮了作用，從而提高了查詢效率。

4. B 樹索引

B Tree是在B-Tree基礎上的一種最佳化，使其更適合實現外部儲存索引結構，B 樹的性質：

1、非葉子節點的子樹指標與關鍵字個數相同；

2、為所有葉子節點增加一個鏈結指標；

3、所有關鍵字都在葉子節點出現， 且鍊錶中的關鍵字恰好是有序的；

4、非葉子節點相當於是葉子節點的索引,葉子節點相當於是儲存(關鍵字)資料的資料層；

InnoDB儲存引擎就是用B Tree實現其索引結構。

B-樹結構圖中可見每個節點除了資料的key值外，還包含資料值。而每一個頁的儲存空間是有限的，如果data資料較大時將會導致每個節點（即一個頁）能儲存的key的數量很小，當儲存的資料量很大時同樣會導致B- Tree的深度較大，增加查詢時的磁碟I/O次數，進而影響查詢效率。在B Tree中，所有資料記錄節點都是按照鍵值大小順序存放在同一層的葉子節點上，而非葉子節點上只存儲key值信息，這樣可以大大加大每個節點存儲的key值數量，降低B Tree的高度。

B Tree相對於B-Tree有幾點不同：

#1、非葉子節點只儲存鍵值資訊和指向子節點頁號的指標；

2、所有葉子節點之間都有一個鏈指標；

3、資料記錄都存放在葉子節點中；

根據上圖我們來看下B 樹和B 樹有什麼不同：

(2) 在B 樹中，非葉節點僅儲存鍵值，而B樹節點既儲存鍵值，也儲存資料。

頁的大小是固定的，InnoDB 中頁的預設大小是 16KB。如果不儲存數據，那麼就會儲存更多的鍵值，相應的樹的階數就會更大，樹就會更矮更胖，如此一來我們查找數據進行磁碟的IO 次數又會再次減少，資料查詢的效率也會更快。

另外，如果我們的 B 樹一個節點可以儲存 1000 個鍵值，那麼 3 層 B 樹可以儲存 1000×1000×1000=10 億個資料。一般根節點是常駐記憶體的(第一次檢索根節點不用讀取磁碟)，所以一般我們查找 10 億數據，只需要 2 次磁碟 IO。

(2) B 樹索引的所有資料都儲存在葉子節點，而且資料是按照順序排列的。

B 樹中各個頁之間是透過雙向鍊錶連接的，葉子節點中的資料是透過單向鍊錶連接的，透過這種方式可以找到表中的所有資料。 B 樹讓範圍查詢、排序查詢、分組查詢和去重查詢變得極為簡單。而 B 樹因為資料分散在各個節點，要實現這一點是很不容易的。

以上是MySQL中B樹索引和B+樹索引的差別是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章！