一、產(chǎn)生的背景

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

1.1 進化要求

• 每個結(jié)點能存儲多個元素
• 摒棄二叉樹結(jié)構(gòu)，采用多叉樹

二、B-tree

B-Tree是一種多叉的平衡搜索樹（并不一定是二叉的），以一個三階B-tree為例子來分析，每個儲存塊都包含：關(guān)鍵字和指向孩子結(jié)點的指針，最多有M個孩子，M的大小主要取決于每個存儲塊的容量和數(shù)據(jù)庫的配置，M表示M階數(shù)的意思。

2.1 B-tree特性

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

假設每個非葉子節(jié)點包含n個關(guān)鍵字信息，其中：

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

假設需要查詢數(shù)據(jù)15，查詢步驟：

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

三、B+tree

3.1 B+tree特性

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

• 非葉子結(jié)點的子樹指針與關(guān)鍵字的個數(shù)相同；
• 非葉子結(jié)點的子樹指針P[i]，指向關(guān)鍵字值 [K[i],K[i+1])的子樹，左閉右開區(qū)間；
• 非葉子結(jié)點僅用于索引，數(shù)據(jù)都保存在葉子結(jié)點中；
• 所有的葉子結(jié)點均有一個鏈指針指向下一個葉子結(jié)點；
• B+樹非葉子結(jié)點僅用來存放索引，能存儲更多的關(guān)鍵字，使得B+樹相對于B樹來說更矮壯，能存儲更多數(shù)據(jù)。
• 所有的數(shù)據(jù)都存儲在葉子結(jié)點。

四、結(jié)論

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

• B+樹的磁盤讀寫代價更低，B+樹內(nèi)部節(jié)點不存放數(shù)據(jù)，只存放索引信息，因此其內(nèi)部節(jié)點相對B-tree會更小，所以同一個盤快就能存儲更多的關(guān)鍵字，一次性讀入內(nèi)存中需要查找的關(guān)鍵字也就越多，因此IO次數(shù)也就越低。
• B+樹的查詢效率更加穩(wěn)定，由于B+樹內(nèi)部節(jié)點并不是指向文件內(nèi)容的節(jié)點，而只是葉子節(jié)點關(guān)鍵字的索引，索引任何一個數(shù)據(jù)的查詢都必須是：任何關(guān)鍵字查詢都是從根節(jié)點到葉子節(jié)點的查詢路線，因此每個數(shù)據(jù)的查詢效率都是穩(wěn)定一致的。
• B+樹跟有利于對數(shù)據(jù)的掃描，B-tree在解決磁盤IO性能同時并沒有解決元素遍歷效率低下問題，而B+樹只需要遍歷葉子節(jié)點就可以實現(xiàn)對所有關(guān)鍵字的掃描，所有對數(shù)據(jù)庫頻繁的范圍查詢是有著更高的查詢性能。

到此這篇關(guān)于MySQL B-tree與B+tree索引數(shù)據(jù)結(jié)構(gòu)剖析的文章就介紹到這了,更多相關(guān)MySQL B-tree與B+tree內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論