前面寫了好幾篇關(guān)于二叉樹的學習和研究，有興趣的同學可以看看，溫故而知新，可以對比下，B樹與二叉樹的區(qū)別，能夠解決那些問題:

赫夫曼樹

http://www.itdecent.cn/p/3ef0e10400a6

平衡二叉樹

http://www.itdecent.cn/p/f556f7fa6f35

二叉排序樹整理與學習
http://www.itdecent.cn/p/ad82541c577e

今天開始研究B樹，同理，在研究B樹之前，我們還可以繼續(xù)分析一下，關(guān)于二叉樹存在的問題，B樹就是為了進一步解決二叉樹存在的問題的。

二叉樹的操作效率較高，但是也存在問題, 請看下面的二叉樹

二叉樹需要加載到內(nèi)存的，如果二叉樹的節(jié)點少，沒有什么問題，但是如果二叉樹的節(jié)點很多(比如1億)， 就存在如下問題:

問題1：在構(gòu)建二叉樹時，需要多次進行i/o操作(海量數(shù)據(jù)存在數(shù)據(jù)庫或文件中)，節(jié)點海量，構(gòu)建二叉樹時，速度有影響

問題2：節(jié)點海量，也會造成二叉樹的高度很大，會降低操作速度.

多叉樹

在二叉樹中，每個節(jié)點有數(shù)據(jù)項，最多有兩個子節(jié)點。如果允許每個節(jié)點可以有更多的數(shù)據(jù)項和更多的子節(jié)點，就是多叉樹（multiway tree），其實就是B樹。

后面我們講解的2-3樹，2-3-4樹就是多叉樹，多叉樹通過重新組織節(jié)點，減少樹的高度，能對二叉樹進行優(yōu)化。

舉例說明(下面2-3樹就是一顆多叉樹)

B樹

B樹通過重新組織節(jié)點，降低樹的高度，并且減少i/o讀寫次數(shù)來提升效率

如圖B樹通過重新組織節(jié)點， 降低了樹的高度.

文件系統(tǒng)及數(shù)據(jù)庫系統(tǒng)的設(shè)計者利用了磁盤預(yù)讀原理，將一個節(jié)點的大小設(shè)為等于一個頁(頁得大小通常為4k)，這樣每個節(jié)點只需要一次I/O就可以完全載入。

將樹的度M設(shè)置為1024，在600億個元素中最多只需要4次I/O操作就可以讀取到想要的元素,B樹(B+)廣泛應(yīng)用于文件存儲系統(tǒng)以及數(shù)據(jù)庫系統(tǒng)中。

2-3樹

2-3樹是最簡單的B樹結(jié)構(gòu), 具有如下特點:

2-3樹的所有葉子節(jié)點都在同一層.(只要是B樹都滿足這個條件)
有兩個子節(jié)點的節(jié)點叫二節(jié)點，二節(jié)點要么沒有子節(jié)點，要么有兩個子節(jié)點.

有三個子節(jié)點的節(jié)點叫三節(jié)點，三節(jié)點要么沒有子節(jié)點，要么有三個子節(jié)點.
2-3樹是由二節(jié)點和三節(jié)點構(gòu)成的樹。

2-3樹應(yīng)用案例

將數(shù)列{16, 24, 12, 32, 14, 26, 34, 10, 8, 28, 38, 20} 構(gòu)建成2-3樹，并保證數(shù)據(jù)插入的?大小順序。(演示一下構(gòu)建2-3樹的過程.)

插入規(guī)則:
2-3樹的所有葉子節(jié)點都在同一層.(只要是B樹都滿足這個條件)
有兩個子節(jié)點的節(jié)點叫二節(jié)點，二節(jié)點要么沒有子節(jié)點，要么有兩個子節(jié)點.

有三個子節(jié)點的節(jié)點叫三節(jié)點，三節(jié)點要么沒有子節(jié)點，要么有三個子節(jié)點。

當按照規(guī)則插入一個數(shù)到某個節(jié)點時，不能滿足上面三個要求，就需要拆，先向上拆，如果上層滿，則拆本層，拆后仍然需要滿足上面3個條件。

對于三節(jié)點的子樹的值大小仍然遵守(BST 二叉排序樹)的規(guī)則

除了23樹，還有234樹等，概念和23樹類似，也是一種B樹。 如圖:

B樹、B+樹和B*樹

B樹的介紹

B-tree樹即B樹，B即Balanced，平衡的意思。有人把B-tree翻譯成B-樹，容易讓人?產(chǎn)生誤解。會以為B-樹是一種樹，而B樹又是另一種樹。實際上，B-tree就是指的B樹。

B樹的介紹

前面已經(jīng)介紹了2-3樹和2-3-4樹，他們就是B樹(英語：B-tree 也寫成B-樹)，這里我們再做一個說明，我們在學習Mysql時，經(jīng)常聽到說某種類型的索引是基于B樹或者B+樹的，如圖:

B樹的說明:
B樹的階：節(jié)點的最多子節(jié)點個數(shù)。比如2-3樹的階是3，2-3-4樹的階是4

B-樹的搜索，從根結(jié)點開始，對結(jié)點內(nèi)的關(guān)鍵字（有序）序列進行二分查找，如果命中則結(jié)束，否則進入查詢關(guān)鍵字所屬范圍的兒子結(jié)點；重復(fù)，直到所對應(yīng)的兒子指針為空，或已經(jīng)是葉子結(jié)點

關(guān)鍵字集合分布在整顆樹中,即葉子節(jié)點和非葉子節(jié)點都存放數(shù)據(jù).搜索有可能在非葉子結(jié)點結(jié)束其搜索性能等價于在關(guān)鍵字全集內(nèi)做一次二分查找。

B+樹的介紹

B+樹是B樹的變體，也是一種多路搜索樹。

B+樹的說明:

B+樹的搜索與B樹也基本相同，區(qū)別是B+樹只有達到葉子結(jié)點才命中（B樹可以在非葉子結(jié)點命中），其性能也等價于在關(guān)鍵字全集做一次二分查找

所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點的鏈表中（即數(shù)據(jù)只能在葉子節(jié)點【也叫稠密索引】），且鏈表中的關(guān)鍵字(數(shù)據(jù))恰好是有序的。不可能在非葉子結(jié)點命中

非葉子結(jié)點相當于是葉子結(jié)點的索引（稀疏索引），葉子結(jié)點相當于是存儲（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層
更適合文件索引系統(tǒng)

B樹和B+樹各有自己的應(yīng)用場景，不能說B+樹完全比B樹好，反之亦然.

B*樹的介紹

B*樹是B+樹的變體，在B+樹的非根和非葉子結(jié)點再增加指向兄弟的指針。

B*樹的說明:

B樹定義了非葉子結(jié)點關(guān)鍵字個數(shù)至少為(2/3)M，即塊的最低使用率為2/3，而B+樹的塊的最低使用率為B+樹的1/2。

從第1個特點我們可以看出，B*樹分配新結(jié)點的概率比B+樹要低，空間使用率更高