MySQL B-tree與B+tree索引資料結構剖析

2022-08-22 14:03:17

一、產生的背景

二叉查詢樹的查詢時間複雜度是O(logN)，整體的查詢效率已經足夠高了，那麼為什麼還會有B樹和B+樹的進化演進呢? 主要的原因是：二元樹可能會退化成一個線性樹，造成磁碟IO次數增高的問題，當有大量的資料儲存的時候，二叉查詢樹查詢不能將所有的資料載入到記憶體中，只能逐一載入磁碟頁，每個磁碟對應樹的節點，造成大量的磁碟IO操作（最壞的情況IO次數為樹的高度），平衡二元樹由於樹深度過大而造成磁碟IO讀寫過於頻繁，進而導致效率低下。所以，為了減少磁的IO的次數，必須降低樹的深度，將瘦高的樹變得矮胖。

1.1 進化要求

每個結點能儲存多個元素
摒棄二元樹結構，採用多叉樹

二、B-tree

B-Tree是一種多叉的平衡搜尋樹（並不一定是二叉的），以一個三階B-tree為例子來分析，每個儲存塊都包含：關鍵字和指向孩子結點的指標，最多有M個孩子，M的大小主要取決於每個儲存塊的容量和資料庫的設定，M表示M階數的意思。

2.1 B-tree特性

根節點至少包括兩個孩子，範圍是[2,M]；
樹中每個節點最多包含M階數個孩子（M是階數，3階，即：每個節點最多包含3個孩子）；
除了根節點和葉子結點以外，其他每個節點至少有ceil(M/2)個孩子節點，ceil是取上限函數（M是階數，3階，即：每個節點至少有2個孩子）；
所有的葉子結點都位於同一層。

假設每個非葉子節點包含n個關鍵字資訊，其中：

Ki(i=1,2..,n)為關鍵字，且關鍵字按順序升序排序K(i-1)< Ki；
關鍵字的個數n必須滿足：[ceil(m/2)-1]<=n<=m-1（非葉子結點的關鍵字 = 指向孩子的指標個數-1）；
非葉子結點的指標：P[1],P[2],...,P[M]；其中P[1]指向關鍵字小於K[1]的子樹（即：3和5均小於8），P[M]指向關鍵字大於K[M-1]的子樹（即：13和15均大於12），其他P[i]指向關鍵字屬於(K[i-1],K[i])的子樹，是開區間（即：9和10都處於8-12區間）；

假設需要查詢資料15，查詢步驟：

首先從根部開始找，15<17，往左邊P1找，P1指向的子樹關鍵字為8和12；
由於15比8和12都大，因此會找到P3；
P3指向了13和15，13<15，最終找到15；
查詢的時間複雜度為O(logN)。

三、B+tree

3.1 B+tree特性

B+樹是B樹的變體，其定義基本上與B樹相同，除了：

非葉子結點的子樹指標與關鍵字的個數相同；
非葉子結點的子樹指標P[i]，指向關鍵字值 [K[i],K[i+1])的子樹，左閉右開區間；
非葉子結點僅用於索引，資料都儲存在葉子結點中；
所有的葉子結點均有一個鏈指標指向下一個葉子結點；
B+樹非葉子結點僅用來存放索引，能儲存更多的關鍵字，使得B+樹相對於B樹來說更矮壯，能儲存更多資料。
所有的資料都儲存在葉子結點。

四、結論

B+tree相比B-tree更適合用來儲存索引，原因如下：

B+樹的磁碟讀寫代價更低，B+樹內部節點不存放資料，只存放索引資訊，因此其內部節點相對B-tree會更小，所以同一個盤快就能儲存更多的關鍵字，一次性讀入記憶體中需要查詢的關鍵字也就越多，因此IO次數也就越低。
B+樹的查詢效率更加穩定，由於B+樹內部節點並不是指向檔案內容的節點，而只是葉子節點關鍵字的索引，索引任何一個資料的查詢都必須是：任何關鍵字查詢都是從根節點到葉子節點的查詢路線，因此每個資料的查詢效率都是穩定一致的。
B+樹跟有利於對資料的掃描，B-tree在解決磁碟IO效能同時並沒有解決元素遍歷效率低下問題，而B+樹只需要遍歷葉子節點就可以實現對所有關鍵字的掃描，所有對資料庫頻繁的範圍查詢是有著更高的查詢效能。

到此這篇關於MySQL B-tree與B+tree索引資料結構剖析的文章就介紹到這了,更多相關MySQL B-tree與B+tree內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！