MySQL中B樹索引和B+樹索引的區別是什么

本文小編為大家詳細介紹“MySQL中B樹索引和B+樹索引的區別是什么”，內容詳細，步驟清晰，細節處理妥當，希望這篇“MySQL中B樹索引和B+樹索引的區別是什么”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

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

1. 多路搜索樹

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

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

3、M路搜索樹主要用于解決數據量大無法全部加載到內存的數據存儲。通過增加每層節點的個數和在每個節點存放更多的數據來在一層中存放更多的數據，從而降低樹的高度，在數據查找時減少磁盤訪問次數。

4、所以每層的節點數和每個節點包含的關鍵字越多，則樹的高度越矮。但是在每個節點確定數據就越慢，但是B樹關注的是磁盤性能瓶頸，所以在單個節點搜索數據的開銷可以忽略。

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

B樹是一種M路搜索樹，B樹主要用于解決M路搜索樹的不平衡導致樹的高度變高，跟二叉樹退化為鏈表導致性能問題一樣。B樹通過對每層的節點進行控制、調整，如節點分離，節點合并，一層滿時向上分裂父節點來增加新的層等操作來來保證該M路搜索樹的平衡。

M為B樹的階數或者說是路數，在B樹中，每個節點都是一個磁盤塊(頁)。每個非葉子節點存放了關鍵字和指向兒子樹的指針，具體數量為：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-Tree結構圖中可以看到每個節點中不僅包含數據的key值，還有data值。而每一個頁的存儲空間是有限的，如果data數據較大時將會導致每個節點（即一個頁）能存儲的key的數量很小，當存儲的數據量很大時同樣會導致B-Tree的深度較大，增大查詢時的磁盤I/O次數，進而影響查詢效率。在B+Tree中，所有數據記錄節點都是按照鍵值大小順序存放在同一層的葉子節點上，而非葉子節點上只存儲key值信息，這樣可以大大加大每個節點存儲的key值數量，降低B+Tree的高度。

B+Tree相對于B-Tree有幾點不同：

1、非葉子節點只存儲鍵值信息和指向子節點頁號的指針；

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

3、數據記錄都存放在葉子節點中；

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

(1) B+ 樹非葉子節點上是不存儲數據的，僅存儲鍵值，而 B 樹節點中不僅存儲鍵值，也會存儲數據。

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

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

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

B+ 樹中各個頁之間是通過雙向鏈表連接的，葉子節點中的數據是通過單向鏈表連接的，通過這種方式可以找到表中的所有數據。B+ 樹使得范圍查找，排序查找，分組查找以及去重查找變得異常簡單。而 B 樹因為數據分散在各個節點，要實現這一點是很不容易的。

讀到這里，這篇“MySQL中B樹索引和B+樹索引的區別是什么”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。