深入了解 B-Tree 和 B+Tree 的區(qū)別
B-Tree
B-Tree是為磁盤(pán)等外存儲(chǔ)設(shè)備設(shè)計(jì)的一種平衡查找樹(shù)。
系統(tǒng)從磁盤(pán)讀取數(shù)據(jù)到內(nèi)存時(shí)是以磁盤(pán)塊（block）為基本單位的，位于同一個(gè)磁盤(pán)塊中的數(shù)據(jù)會(huì)被一次性讀取出來(lái)，而不是需要什么取什么。
InnoDB 存儲(chǔ)引擎中有頁(yè)（Page）的概念，頁(yè)是其磁盤(pán)管理的最小單位。InnoDB 存儲(chǔ)引擎中默認(rèn)每個(gè)頁(yè)的大小為16KB，可通過(guò)參數(shù)?innodb_page_size?將頁(yè)的大小設(shè)置為 4K、8K、16K，在 MySQL 中可通過(guò)如下命令查看頁(yè)的大?。?code style="margin-right: 2px;margin-left: 2px;padding: 2px 4px;max-width: 100%;font-size: 14px;border-radius: 4px;font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;word-break: break-all;color: rgb(244, 138, 0);background-color: rgba(27, 31, 35, 0.047);box-sizing: border-box !important;overflow-wrap: break-word !important;">show variables like 'innodb_page_size';
而系統(tǒng)一個(gè)磁盤(pán)塊的存儲(chǔ)空間往往沒(méi)有這么大，因此 InnoDB 每次申請(qǐng)磁盤(pán)空間時(shí)都會(huì)是若干地址連續(xù)磁盤(pán)塊來(lái)達(dá)到頁(yè)的大小 16KB。InnoDB 在把磁盤(pán)數(shù)據(jù)讀入到磁盤(pán)時(shí)會(huì)以頁(yè)為基本單位，在查詢(xún)數(shù)據(jù)時(shí)如果一個(gè)頁(yè)中的每條數(shù)據(jù)都能有助于定位數(shù)據(jù)記錄的位置，這將會(huì)減少磁盤(pán)I/O次數(shù)，提高查詢(xún)效率。
B-Tree 結(jié)構(gòu)的數(shù)據(jù)可以讓系統(tǒng)高效的找到數(shù)據(jù)所在的磁盤(pán)塊。為了描述 B-Tree，首先定義一條記錄為一個(gè)二元組[key, data] ，key為記錄的鍵值，對(duì)應(yīng)表中的主鍵值，data 為一行記錄中除主鍵外的數(shù)據(jù)。對(duì)于不同的記錄，key值互不相同。
一棵m階的B-Tree有如下特性：
每個(gè)節(jié)點(diǎn)最多有m個(gè)孩子 除了根節(jié)點(diǎn)和葉子節(jié)點(diǎn)外，其它每個(gè)節(jié)點(diǎn)至少有Ceil(m/2)個(gè)孩子。 若根節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則至少有2個(gè)孩子 所有葉子節(jié)點(diǎn)都在同一層，且不包含其它關(guān)鍵字信息 每個(gè)非終端節(jié)點(diǎn)包含n個(gè)關(guān)鍵字信息（P0,P1,…Pn, k1,…kn） 關(guān)鍵字的個(gè)數(shù)n滿足：ceil(m/2)-1 <= n <= m-1 ki(i=1,…n)為關(guān)鍵字，且關(guān)鍵字升序排序 Pi(i=1,…n)為指向子樹(shù)根節(jié)點(diǎn)的指針。P(i-1)指向的子樹(shù)的所有節(jié)點(diǎn)關(guān)鍵字均小于ki，但都大于k(i-1)
B-Tree 中的每個(gè)節(jié)點(diǎn)根據(jù)實(shí)際情況可以包含大量的關(guān)鍵字信息和分支，如下圖所示為一個(gè) 3 階的 B-Tree：
每個(gè)節(jié)點(diǎn)占用一個(gè)盤(pán)塊的磁盤(pán)空間，一個(gè)節(jié)點(diǎn)上有兩個(gè)升序排序的關(guān)鍵字和三個(gè)指向子樹(shù)根節(jié)點(diǎn)的指針，指針存儲(chǔ)的是子節(jié)點(diǎn)所在磁盤(pán)塊的地址。兩個(gè)關(guān)鍵詞劃分成的三個(gè)范圍域?qū)?yīng)三個(gè)指針指向的子樹(shù)的數(shù)據(jù)的范圍域。以根節(jié)點(diǎn)為例，關(guān)鍵字為17和35，P1指針指向的子樹(shù)的數(shù)據(jù)范圍為小于17，P2指針指向的子樹(shù)的數(shù)據(jù)范圍為17~35，P3指針指向的子樹(shù)的數(shù)據(jù)范圍為大于35。
模擬查找關(guān)鍵字29的過(guò)程：
根據(jù)根節(jié)點(diǎn)找到磁盤(pán)塊1，讀入內(nèi)存?！敬疟P(pán)I/O操作第1次】 比較關(guān)鍵字29在區(qū)間（17,35），找到磁盤(pán)塊1的指針P2。 根據(jù)P2指針找到磁盤(pán)塊3，讀入內(nèi)存?！敬疟P(pán)I/O操作第2次】 比較關(guān)鍵字29在區(qū)間（26,30），找到磁盤(pán)塊3的指針P2。 根據(jù)P2指針找到磁盤(pán)塊8，讀入內(nèi)存?！敬疟P(pán)I/O操作第3次】 在磁盤(pán)塊8中的關(guān)鍵字列表中找到關(guān)鍵字29。
分析上面過(guò)程，發(fā)現(xiàn)需要3次磁盤(pán)I/O操作，和3次內(nèi)存查找操作。由于內(nèi)存中的關(guān)鍵字是一個(gè)有序表結(jié)構(gòu)，可以利用二分法查找提高效率。而3次磁盤(pán)I/O操作是影響整個(gè)B-Tree查找效率的決定因素。B-Tree相對(duì)于AVLTree縮減了節(jié)點(diǎn)個(gè)數(shù)，使每次磁盤(pán)I/O取到內(nèi)存的數(shù)據(jù)都發(fā)揮了作用，從而提高了查詢(xún)效率。
B+Tree
B+Tree 是在 B-Tree 基礎(chǔ)上的一種優(yōu)化，使其更適合實(shí)現(xiàn)外存儲(chǔ)索引結(jié)構(gòu)，InnoDB 存儲(chǔ)引擎就是用 B+Tree 實(shí)現(xiàn)其索引結(jié)構(gòu)。
從上一節(jié)中的B-Tree結(jié)構(gòu)圖中可以看到每個(gè)節(jié)點(diǎn)中不僅包含數(shù)據(jù)的key值，還有data值。而每一個(gè)頁(yè)的存儲(chǔ)空間是有限的，如果data數(shù)據(jù)較大時(shí)將會(huì)導(dǎo)致每個(gè)節(jié)點(diǎn)（即一個(gè)頁(yè)）能存儲(chǔ)的key的數(shù)量很小，當(dāng)存儲(chǔ)的數(shù)據(jù)量很大時(shí)同樣會(huì)導(dǎo)致B-Tree的深度較大，增大查詢(xún)時(shí)的磁盤(pán)I/O次數(shù)，進(jìn)而影響查詢(xún)效率。在B+Tree中，所有數(shù)據(jù)記錄節(jié)點(diǎn)都是按照鍵值大小順序存放在同一層的葉子節(jié)點(diǎn)上，而非葉子節(jié)點(diǎn)上只存儲(chǔ)key值信息，這樣可以大大加大每個(gè)節(jié)點(diǎn)存儲(chǔ)的key值數(shù)量，降低B+Tree的高度。
B+Tree相對(duì)于B-Tree有幾點(diǎn)不同：
非葉子節(jié)點(diǎn)只存儲(chǔ)鍵值信息； 所有葉子節(jié)點(diǎn)之間都有一個(gè)鏈指針； 數(shù)據(jù)記錄都存放在葉子節(jié)點(diǎn)中
將上一節(jié)中的B-Tree優(yōu)化，由于B+Tree的非葉子節(jié)點(diǎn)只存儲(chǔ)鍵值信息，假設(shè)每個(gè)磁盤(pán)塊能存儲(chǔ)4個(gè)鍵值及指針信息，則變成B+Tree后其結(jié)構(gòu)如下圖所示：
通常在B+Tree上有兩個(gè)頭指針，一個(gè)指向根節(jié)點(diǎn)，另一個(gè)指向關(guān)鍵字最小的葉子節(jié)點(diǎn)，而且所有葉子節(jié)點(diǎn)（即數(shù)據(jù)節(jié)點(diǎn)）之間是一種鏈?zhǔn)江h(huán)結(jié)構(gòu)。因此可以對(duì)B+Tree進(jìn)行兩種查找運(yùn)算：一種是對(duì)于主鍵的范圍查找和分頁(yè)查找，另一種是從根節(jié)點(diǎn)開(kāi)始，進(jìn)行隨機(jī)查找。
可能上面例子中只有22條數(shù)據(jù)記錄，看不出B+Tree的優(yōu)點(diǎn)，下面做一個(gè)推算：
InnoDB存儲(chǔ)引擎中頁(yè)的大小為16KB，一般表的主鍵類(lèi)型為INT（占用4個(gè)字節(jié)）或BIGINT（占用8個(gè)字節(jié)），指針類(lèi)型也一般為4或8個(gè)字節(jié)，也就是說(shuō)一個(gè)頁(yè)（B+Tree中的一個(gè)節(jié)點(diǎn)）中大概存儲(chǔ)16KB/(8B+8B)=1K個(gè)鍵值（因?yàn)槭枪乐担瑸榉奖阌?jì)算，這里的K取值為10^3）。也就是說(shuō)一個(gè)深度為3的B+Tree索引可以維護(hù)10^3 * 10^3 * 10^3 = 10億 條記錄。
實(shí)際情況中每個(gè)節(jié)點(diǎn)可能不能填充滿，因此在數(shù)據(jù)庫(kù)中，B+Tree的高度一般都在2-4層。MySQL的InnoDB存儲(chǔ)引擎在設(shè)計(jì)時(shí)是將根節(jié)點(diǎn)常駐內(nèi)存的，也就是說(shuō)查找某一鍵值的行記錄時(shí)最多只需要1~3次磁盤(pán)I/O操作。
B+Tree性質(zhì)
通過(guò)上面的分析，我們知道IO次數(shù)取決于b+數(shù)的高度h，假設(shè)當(dāng)前數(shù)據(jù)表的數(shù)據(jù)為N，每個(gè)磁盤(pán)塊的數(shù)據(jù)項(xiàng)的數(shù)量是m，則有h=㏒(m+1)N，當(dāng)數(shù)據(jù)量N一定的情況下，m越大，h越?。欢鴐 = 磁盤(pán)塊的大小 / 數(shù)據(jù)項(xiàng)的大小，磁盤(pán)塊的大小也就是一個(gè)數(shù)據(jù)頁(yè)的大小，是固定的，如果數(shù)據(jù)項(xiàng)占的空間越小，數(shù)據(jù)項(xiàng)的數(shù)量越多，樹(shù)的高度越低。這就是為什么每個(gè)數(shù)據(jù)項(xiàng)，即索引字段要盡量的小，比如int占4字節(jié)，要比bigint8字節(jié)少一半。這也是為什么b+樹(shù)要求把真實(shí)的數(shù)據(jù)放到葉子節(jié)點(diǎn)而不是內(nèi)層節(jié)點(diǎn)，一旦放到內(nèi)層節(jié)點(diǎn)，磁盤(pán)塊的數(shù)據(jù)項(xiàng)會(huì)大幅度下降，導(dǎo)致樹(shù)增高。當(dāng)數(shù)據(jù)項(xiàng)等于1時(shí)將會(huì)退化成線性表。 當(dāng)b+樹(shù)的數(shù)據(jù)項(xiàng)是復(fù)合的數(shù)據(jù)結(jié)構(gòu)，比如(name,age,sex)的時(shí)候，b+數(shù)是按照從左到右的順序來(lái)建立搜索樹(shù)的，比如當(dāng)(張三,20,F)這樣的數(shù)據(jù)來(lái)檢索的時(shí)候，b+樹(shù)會(huì)優(yōu)先比較name來(lái)確定下一步的所搜方向，如果name相同再依次比較age和sex，最后得到檢索的數(shù)據(jù)；但當(dāng)(20,F)這樣的沒(méi)有name的數(shù)據(jù)來(lái)的時(shí)候，b+樹(shù)就不知道下一步該查哪個(gè)節(jié)點(diǎn)，因?yàn)榻⑺阉鳂?shù)的時(shí)候name就是第一個(gè)比較因子，必須要先根據(jù)name來(lái)搜索才能知道下一步去哪里查詢(xún)。比如當(dāng)(張三,F)這樣的數(shù)據(jù)來(lái)檢索時(shí)，b+樹(shù)可以用name來(lái)指定搜索方向，但下一個(gè)字段age的缺失，所以只能把名字等于張三的數(shù)據(jù)都找到，然后再匹配性別是F的數(shù)據(jù)了， 這個(gè)是非常重要的性質(zhì)，即索引的最左匹配特性。