B+樹索引是B+樹在資料庫中的一種實現,是最常見也是資料庫中使用最為頻繁的一種索引。B+樹中的B代表平衡(balance),而不是二叉(binary),因為B+樹是從最早的平衡二叉樹演化而來的。在講B+樹之前必須先了解二叉查找樹、平衡二叉樹(AVLTree)和平衡多路查找樹(B-Tree),B+樹即由這些樹逐步優化而來。
二叉樹具有以下性質:左子樹的鍵值小於根的鍵值,右子樹的鍵值大於根的鍵值。
對該二叉樹的節點進行查找發現深度為1的節點的查找次數為1,深度為2的查找次數為2,深度為n的節點的查找次數為n,因此其平均查找次數為 (1+2+2+3+3+3) / 6 = 2.3次
二叉查找樹可以任意地構造,同樣是2,3,5,6,7,8這六個數字,也可以按照下圖的方式來構造:
平衡二叉樹(AVL樹)在符合二叉查找樹的條件下,還滿足任何節點的兩個子樹的高度最大差為1。下面的兩張圖片,左邊是AVL樹,它的任何節點的兩個子樹的高度差<=1;右邊的不是AVL樹,其根節點的左子樹高度為3,而右子樹高度為1;
如果在AVL樹中進行插入或刪除節點,可能導致AVL樹失去平衡,這種失去平衡的二叉樹可以概括為四種姿態:LL(左左)、RR(右右)、LR(左右)、RL(右左)。它們的示意圖如下:
這四種失去平衡的姿態都有各自的定義:
RR:RightRight,也稱「右右」。插入或刪除一個節點後,根節點的右孩子(Right Child)的右孩子(Right Child)還有非空節點,導致根節點的右子樹高度比左子樹高度高2,AVL樹失去平衡。
LR:LeftRight,也稱「左右」。插入或刪除一個節點後,根節點的左孩子(Left Child)的右孩子(Right Child)還有非空節點,導致根節點的左子樹高度比右子樹高度高2,AVL樹失去平衡。
RL:RightLeft,也稱「右左」。插入或刪除一個節點後,根節點的右孩子(Right Child)的左孩子(Left Child)還有非空節點,導致根節點的右子樹高度比左子樹高度高2,AVL樹失去平衡。
AVL樹失去平衡之後,可以通過旋轉使其恢復平衡。下面分別介紹四種失去平衡的情況下對應的旋轉方法。
LL的旋轉。LL失去平衡的情況下,可以通過一次旋轉讓AVL樹恢復平衡。步驟如下:
LL旋轉示意圖如下:
RR的旋轉:RR失去平衡的情況下,旋轉方法與LL旋轉對稱,步驟如下:
RR旋轉示意圖如下:
LR的旋轉:LR失去平衡的情況下,需要進行兩次旋轉,步驟如下:
LR的旋轉示意圖如下:
RL的旋轉:RL失去平衡的情況下也需要進行兩次旋轉,旋轉方法與LR旋轉對稱,步驟如下:
RL的旋轉示意圖如下:
B-Tree是為磁碟等外存儲設備設計的一種平衡查找樹。因此在講B-Tree之前先了解下磁碟的相關知識。
系統從磁碟讀取數據到內存時是以磁碟塊(block)為基本單位的,位於同一個磁碟塊中的數據會被一次性讀取出來,而不是需要什麼取什麼。
InnoDB存儲引擎中有頁(Page)的概念,頁是其磁碟管理的最小單位。InnoDB存儲引擎中默認每個頁的大小為16KB,可通過參數innodb_page_size將頁的大小設置為4K、8K、16K,在MySQL中可通過如下命令查看頁的大小:
mysql> show variables like innodb_page_size;
而系統一個磁碟塊的存儲空間往往沒有這麼大,因此InnoDB每次申請磁碟空間時都會是若干地址連續磁碟塊來達到頁的大小16KB。InnoDB在把磁碟數據讀入到磁碟時會以頁為基本單位,在查詢數據時如果一個頁中的每條數據都能有助於定位數據記錄的位置,這將會減少磁碟I/O次數,提高查詢效率。
B-Tree結構的數據可以讓系統高效的找到數據所在的磁碟塊。為了描述B-Tree,首先定義一條記錄為一個二元組[key, data] ,key為記錄的鍵值,對應表中的主鍵值,data為一行記錄中除主鍵外的數據。對於不同的記錄,key值互不相同。
一棵m階的B-Tree有如下特性:
2. 除了根節點和葉子節點外,其它每個節點至少有Ceil(m/2)個孩子。
B-Tree中的每個節點根據實際情況可以包含大量的關鍵字信息和分支,如下圖所示為一個3階的B-Tree:
每個節點佔用一個盤塊的磁碟空間,一個節點上有兩個升序排序的關鍵字和三個指向子樹根節點的指針,指針存儲的是子節點所在磁碟塊的地址。兩個關鍵詞劃分成的三個範圍域對應三個指針指向的子樹的數據的範圍域。以根節點為例,關鍵字為17和35,P1指針指向的子樹的數據範圍為小於17,P2指針指向的子樹的數據範圍為17~35,P3指針指向的子樹的數據範圍為大於35。
模擬查找關鍵字29的過程:
分析上面過程,發現需要3次磁碟I/O操作,和3次內存查找操作。由於內存中的關鍵字是一個有序表結構,可以利用二分法查找提高效率。而3次磁碟I/O操作是影響整個B-Tree查找效率的決定因素。B-Tree相對於AVLTree縮減了節點個數,使每次磁碟I/O取到內存的數據都發揮了作用,從而提高了查詢效率。
B+Tree是在B-Tree基礎上的一種優化,使其更適合實現外存儲索引結構,InnoDB存儲引擎就是用B+Tree實現其索引結構。
從上一節中的B-Tree結構圖中可以看到每個節點中不僅包含數據的key值,還有data值。而每一個頁的存儲空間是有限的,如果data數據較大時將會導致每個節點(即一個頁)能存儲的key的數量很小,當存儲的數據量很大時同樣會導致B-Tree的深度較大,增大查詢時的磁碟I/O次數,進而影響查詢效率。在B+Tree中,所有數據記錄節點都是按照鍵值大小順序存放在同一層的葉子節點上,而非葉子節點上只存儲key值信息,這樣可以大大加大每個節點存儲的key值數量,降低B+Tree的高度。
B+Tree相對於B-Tree有幾點不同:
將上一節中的B-Tree優化,由於B+Tree的非葉子節點只存儲鍵值信息,假設每個磁碟塊能存儲4個鍵值及指針信息,則變成B+Tree後其結構如下圖所示:
通常在B+Tree上有兩個頭指針,一個指向根節點,另一個指向關鍵字最小的葉子節點,而且所有葉子節點(即數據節點)之間是一種鏈式環結構。因此可以對B+Tree進行兩種查找運算:一種是對於主鍵的範圍查找和分頁查找,另一種是從根節點開始,進行隨機查找。
可能上面例子中只有22條數據記錄,看不出B+Tree的優點,下面做一個推算:
InnoDB存儲引擎中頁的大小為16KB,一般表的主鍵類型為INT(佔用4個位元組)或BIGINT(佔用8個位元組),指針類型也一般為4或8個位元組,也就是說一個頁(B+Tree中的一個節點)中大概存儲16KB/(8B+8B)=1K個鍵值(因為是估值,為方便計算,這裡的K取值為〖10〗^3)。也就是說一個深度為3的B+Tree索引可以維護10^3 * 10^3 * 10^3 = 10億 條記錄。
實際情況中每個節點可能不能填充滿,因此在資料庫中,B+Tree的高度一般都在2~4層。mysql的InnoDB存儲引擎在設計時是將根節點常駐內存的,也就是說查找某一鍵值的行記錄時最多只需要1~3次磁碟I/O操作。
資料庫中的B+Tree索引可以分為聚集索引(clustered index)和輔助索引(secondary index)。上面的B+Tree示例圖在資料庫中的實現即為聚集索引,聚集索引的B+Tree中的葉子節點存放的是整張表的行記錄數據。輔助索引與聚集索引的區別在於輔助索引的葉子節點並不包含行記錄的全部數據,而是存儲相應行數據的聚集索引鍵,即主鍵。當通過輔助索引來查詢數據時,InnoDB存儲引擎會遍歷輔助索引找到主鍵,然後再通過主鍵在聚集索引中找到完整的行記錄數據。
(完)
推薦閱讀: