在算法邏輯上，二叉樹的查找效率和比較次數(shù)都是最小的，但是在實際問題中，還要考慮磁盤IO.

數(shù)據(jù)庫索引是存儲在磁盤上的，當(dāng)數(shù)據(jù)量比較大時，索引可能幾個G。

當(dāng)我們利用索引查詢的時候，不能將整個索引全部加載到內(nèi)存中，能做的只能是逐一加載每一個磁盤頁，這里的磁盤頁對應(yīng)索引樹的節(jié)點。

二叉查找數(shù)、平衡二叉樹、紅黑樹是典型的二叉查找數(shù)結(jié)構(gòu)，其查找的時間復(fù)雜度為O(log2N)與樹的深度有關(guān)，所以降低樹的深度自然能提高查找效率。

在實際場景中：大規(guī)模數(shù)據(jù)存儲中，實現(xiàn)索引查詢這樣一個實際場景下，樹節(jié)點存儲的元素數(shù)量是有限的(如果元素數(shù)量非常多的話，查找退化成節(jié)點內(nèi)部的線性查找了)，這樣導(dǎo)致二叉查找樹結(jié)構(gòu)由于樹的深度過大而造成磁盤I/O讀寫過于頻繁，進而降低查詢效率低下，所以就思考如何降低樹的深度(當(dāng)然不能減少查詢的數(shù)據(jù)量)，一個基本的想法是：采用多叉樹結(jié)構(gòu)

B樹和B+樹是平衡的多路查找樹

一、B樹

簡單來說：B樹是一種多路平衡查找樹，它的每一個節(jié)點最多包含k個孩子，k也稱為階樹。

k的大小取決于磁盤頁的大小

概念：B樹和平衡二叉樹稍有不同的是B樹屬于多叉樹又名平衡多路查找樹(查找路徑不只兩個)，數(shù)據(jù)庫索引技術(shù)里大量使用者B樹和B+樹的數(shù)據(jù)結(jié)構(gòu)，讓我們來看看他有什么特點;

規(guī)則：

(1)排序方式：所有節(jié)點關(guān)鍵字是按遞增次序排列，并遵循左小右大原則；

(2)子節(jié)點數(shù)：非葉節(jié)點的子節(jié)點數(shù)>1，且<=M ，且M>=2，空樹除外(注：M階代表一個樹節(jié)點最多有多少個查找路徑，M=M路,當(dāng)M=2則是2叉樹,M=3則是3叉)；

(3)關(guān)鍵字數(shù)：枝節(jié)點的關(guān)鍵字數(shù)量大于等于ceil(m/2)-1個且小于等于M-1個(注：ceil()是個朝正無窮方向取整的函數(shù) 如ceil(1.1)結(jié)果為2);

(4)所有葉子節(jié)點均在同一層、葉子節(jié)點除了包含了關(guān)鍵字和關(guān)鍵字記錄的指針外也有指向其子節(jié)點的指針只不過其指針地址都為null對應(yīng)下圖最后一層節(jié)點的空格子;

用途：

文件系統(tǒng)和部分數(shù)據(jù)庫索引，比如著名的非關(guān)系型數(shù)據(jù)庫MongoDB

最后我們用一個圖和一個實際的例子來理解B樹(這里為了理解方便我就直接用實際字母的大小來排列C>B>A)

高度每下降一級，即讀取一次磁盤(一次I/O)；當(dāng)一個磁盤頁數(shù)據(jù)讀取到內(nèi)存，對一個節(jié)點內(nèi)數(shù)據(jù)查找，速度很快，幾乎可以忽略。所以樹的高度足夠低，I/O次數(shù)足夠少，就能提升性能。

B樹的查詢流程：

如上圖我要從上圖中找到E字母，查找流程如下

(1)獲取根節(jié)點的關(guān)鍵字進行比較，當(dāng)前根節(jié)點關(guān)鍵字為M，E

(2)拿到關(guān)鍵字D和G，D

(3)拿到E和F，因為E=E 所以直接返回關(guān)鍵字和指針信息(如果樹結(jié)構(gòu)里面沒有包含所要查找的節(jié)點則返回null)；

考題：M階B-樹中含有N個關(guān)鍵字，最大深度為：

至于為什么不能葉節(jié)點不能存儲關(guān)鍵字，查看如下原因：

葉子結(jié)點是不存在的，指向這些結(jié)點的指針為空，引入葉子結(jié)點的目的是為了方便分析B-樹的查找性能

一棵3階B-樹中含有2047個關(guān)鍵字,包含葉結(jié)點層,該樹的最大深度為(12)

二、B+樹

B+樹的性能比B樹更高

1.與B樹區(qū)別：

①有n棵子樹的節(jié)點含有n個關(guān)鍵碼

②所有的葉節(jié)點中包含了全部關(guān)鍵碼的信息，以及指向含有這些關(guān)鍵碼記錄的指針，且葉子節(jié)點本身依關(guān)鍵字大小自小而大順序連接

③所有的非終端節(jié)點可以看成是索引部分，節(jié)點中僅含有其子樹根節(jié)點中最大(小)的關(guān)鍵字

對③理解

衛(wèi)星數(shù)據(jù)：索引元素所指向的數(shù)據(jù)記錄，比如數(shù)據(jù)庫中的某一行。在B樹中，無論是中間節(jié)點還是葉子節(jié)點都有衛(wèi)星數(shù)據(jù)。

而B+樹中，只有葉子節(jié)點帶有衛(wèi)星數(shù)據(jù)，其余中間節(jié)點僅僅是索引，沒有任何數(shù)據(jù)關(guān)聯(lián)

在B+樹中，通常有兩個頭指針，一個指向根節(jié)點，另一個指向關(guān)鍵字最小的葉節(jié)點。因此，可以對B+數(shù)進行兩種查找運算：一種是從最小關(guān)鍵字開始順序查找，另一種是從根節(jié)點進行隨機查找。

查找過程與B樹類似，但是有兩點不同(也是查找效率更優(yōu)的原因)

①B+樹的中間節(jié)點，沒有衛(wèi)星數(shù)據(jù)，所以同樣大小的磁盤頁可以容納更多的節(jié)點元素【?“更矮胖”，查詢時IO次數(shù)更少】

②B+樹必須查找到葉子節(jié)點，而B樹只要找到匹配元素即可，無論匹配元素處于中間節(jié)點還是葉子節(jié)點

因此B樹查找性能并不穩(wěn)定(最好，只查根節(jié)點，最壞情況是查到葉子節(jié)點)。而B+樹的每一次查找都是穩(wěn)定的，都要到葉子節(jié)點

2.B+樹的優(yōu)勢

單一節(jié)點存儲更多元素，io更少

所有查詢都要查找到葉子節(jié)點，查找性能穩(wěn)定

所有葉子節(jié)點形成有序鏈表，便于范圍查詢

3.B+樹應(yīng)用場合

大部分的關(guān)系數(shù)據(jù)庫，如Mysql

三、為什么B+樹比B樹更適合實際應(yīng)用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫索引

因為數(shù)據(jù)表的索引比較大，不能常駐內(nèi)存，所以以文件形式存儲在磁盤中。當(dāng)查詢數(shù)據(jù)的時候就需要I/O操作。高效率查詢的目標(biāo)是較少的I/O次數(shù)。一次I/O一般是讀取一頁大小的數(shù)據(jù)。當(dāng)申請一個節(jié)點時，就以頁的大小來申請。也就是說一次I/O可以讀取一個節(jié)點的數(shù)據(jù)。這樣，B樹也可以作為索引數(shù)據(jù)結(jié)構(gòu)，但是最終還是選擇了B+樹。

①B+樹的內(nèi)部節(jié)點并沒有指向關(guān)鍵字具體信息。因此可以存儲更多的數(shù)據(jù)。索引樹更加矮胖，I/O次數(shù)更少

②B+樹的查詢效率更加穩(wěn)定

由于非終節(jié)點并不是最終指向文件內(nèi)容的節(jié)點，而只是葉子節(jié)點中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須從根節(jié)點到葉子節(jié)點。所有關(guān)鍵字查詢路徑長度相同，導(dǎo)致每一個數(shù)據(jù)的查詢效率相當(dāng)。

③范圍查找簡單：B+樹不需要中序遍歷，遍歷鏈表即可。

四、hash比B+樹更快，為啥mysql還用B+樹來存索引

和具體的業(yè)務(wù)場景有關(guān)，如果只選一個數(shù)據(jù)，那確實hash更快。但是數(shù)據(jù)庫中經(jīng)常會選擇多條，這時B+樹索引就更快了。

而且數(shù)據(jù)庫中索引一般放在磁盤中，數(shù)據(jù)量大的情況，無法一次裝入內(nèi)存，B+數(shù)的設(shè)計可以允許數(shù)據(jù)分批加載，同時樹的高度較低，提高查找效率。

總結(jié)

以上是生活随笔為你收集整理的mysql 节点查根_（三）B数、B+树及在数据库索引中应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。