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

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

1.1 進(jìn)化要求

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

二、B-tree

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

2.1 B-tree特性

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

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

• Ki(i=1,2..,n)為關(guān)鍵字，且關(guān)鍵字按順序升序排序K(i-1)< Ki；
• 關(guān)鍵字的個(gè)數(shù)n必須滿足：[ceil(m/2)-1]<=n<=m-1（非葉子結(jié)點(diǎn)的關(guān)鍵字 = 指向孩子的指針個(gè)數(shù)-1）；
• 非葉子結(jié)點(diǎn)的指針：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è)需要查詢數(shù)據(jù)15，查詢步驟：

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

三、B+tree

3.1 B+tree特性

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

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

四、結(jié)論

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

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

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

最新評(píng)論