前面寫了好幾篇關(guān)于二叉樹的學(xué)習(xí)和研究况毅，有興趣的同學(xué)可以看看分蓖，溫故而知新，可以對(duì)比下尔许，B樹與二叉樹的區(qū)別么鹤，能夠解決那些問題:
赫夫曼樹
http://www.reibang.com/p/3ef0e10400a6
平衡二叉樹
http://www.reibang.com/p/f556f7fa6f35
二叉排序樹整理與學(xué)習(xí)
http://www.reibang.com/p/ad82541c577e
今天開始研究B樹，同理味廊，在研究B樹之前蒸甜，我們還可以繼續(xù)分析一下，關(guān)于二叉樹存在的問題余佛，B樹就是為了進(jìn)一步解決二叉樹存在的問題的柠新。
二叉樹的操作效率較高，但是也存在問題, 請(qǐng)看下面的二叉樹
二叉樹需要加載到內(nèi)存的辉巡，如果二叉樹的節(jié)點(diǎn)少恨憎，沒有什么問題，但是如果二叉樹的節(jié)點(diǎn)很多(比如1億)红氯， 就存在如下問題:
問題1：在構(gòu)建二叉樹時(shí)框咙，需要多次進(jìn)行i/o操作(海量數(shù)據(jù)存在數(shù)據(jù)庫(kù)或文件中)，節(jié)點(diǎn)海量痢甘，構(gòu)建二叉樹時(shí)喇嘱，速度有影響
問題2：節(jié)點(diǎn)海量，也會(huì)造成二叉樹的高度很大塞栅，會(huì)降低操作速度.
多叉樹
在二叉樹中者铜，每個(gè)節(jié)點(diǎn)有數(shù)據(jù)項(xiàng)，最多有兩個(gè)子節(jié)點(diǎn)放椰。如果允許每個(gè)節(jié)點(diǎn)可以有更多的數(shù)據(jù)項(xiàng)和更多的子節(jié)點(diǎn)作烟，就是多叉樹（multiway tree），其實(shí)就是B樹砾医。
后面我們講解的2-3樹拿撩，2-3-4樹就是多叉樹，多叉樹通過重新組織節(jié)點(diǎn)如蚜，減少樹的高度压恒，能對(duì)二叉樹進(jìn)行優(yōu)化。
舉例說(shuō)明(下面2-3樹就是一顆多叉樹)
B樹
B樹通過重新組織節(jié)點(diǎn)错邦，降低樹的高度探赫，并且減少i/o讀寫次數(shù)來(lái)提升效率
如圖B樹通過重新組織節(jié)點(diǎn)， 降低了樹的高度.
文件系統(tǒng)及數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)者利用了磁盤預(yù)讀原理撬呢，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè)(頁(yè)得大小通常為4k)伦吠，這樣每個(gè)節(jié)點(diǎn)只需要一次I/O就可以完全載入。
將樹的度M設(shè)置為1024魂拦，在600億個(gè)元素中最多只需要4次I/O操作就可以讀取到想要的元素,B樹(B+)廣泛應(yīng)用于文件存儲(chǔ)系統(tǒng)以及數(shù)據(jù)庫(kù)系統(tǒng)中毛仪。
2-3樹
2-3樹是最簡(jiǎn)單的B樹結(jié)構(gòu), 具有如下特點(diǎn):
2-3樹的所有葉子節(jié)點(diǎn)都在同一層.(只要是B樹都滿足這個(gè)條件)
有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)叫二節(jié)點(diǎn)，二節(jié)點(diǎn)要么沒有子節(jié)點(diǎn)芯勘，要么有兩個(gè)子節(jié)點(diǎn).
有三個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)叫三節(jié)點(diǎn)潭千，三節(jié)點(diǎn)要么沒有子節(jié)點(diǎn)，要么有三個(gè)子節(jié)點(diǎn).
2-3樹是由二節(jié)點(diǎn)和三節(jié)點(diǎn)構(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é)點(diǎn)都在同一層.(只要是B樹都滿足這個(gè)條件)
有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)叫二節(jié)點(diǎn)路翻，二節(jié)點(diǎn)要么沒有子節(jié)點(diǎn)狈癞，要么有兩個(gè)子節(jié)點(diǎn).
有三個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)叫三節(jié)點(diǎn)，三節(jié)點(diǎn)要么沒有子節(jié)點(diǎn)茂契，要么有三個(gè)子節(jié)點(diǎn)蝶桶。
當(dāng)按照規(guī)則插入一個(gè)數(shù)到某個(gè)節(jié)點(diǎn)時(shí)，不能滿足上面三個(gè)要求掉冶，就需要拆真竖，先向上拆脐雪，如果上層滿，則拆本層恢共，拆后仍然需要滿足上面3個(gè)條件战秋。
對(duì)于三節(jié)點(diǎn)的子樹的值大小仍然遵守(BST 二叉排序樹)的規(guī)則
除了23樹，還有234樹等讨韭，概念和23樹類似脂信，也是一種B樹。 如圖:
B樹透硝、B+樹和B*樹
B樹的介紹
B-tree樹即B樹狰闪，B即Balanced，平衡的意思濒生。有人把B-tree翻譯成B-樹埋泵，容易讓人?產(chǎn)生誤解。會(huì)以為B-樹是一種樹罪治，而B樹又是另一種樹秋泄。實(shí)際上，B-tree就是指的B樹规阀。
B樹的介紹
前面已經(jīng)介紹了2-3樹和2-3-4樹恒序，他們就是B樹(英語(yǔ)：B-tree 也寫成B-樹)，這里我們?cè)僮鲆粋€(gè)說(shuō)明谁撼，我們?cè)趯W(xué)習(xí)Mysql時(shí)歧胁，經(jīng)常聽到說(shuō)某種類型的索引是基于B樹或者B+樹的，如圖:
B樹的說(shuō)明:
B樹的階：節(jié)點(diǎn)的最多子節(jié)點(diǎn)個(gè)數(shù)厉碟。比如2-3樹的階是3喊巍，2-3-4樹的階是4
B-樹的搜索，從根結(jié)點(diǎn)開始箍鼓，對(duì)結(jié)點(diǎn)內(nèi)的關(guān)鍵字（有序）序列進(jìn)行二分查找崭参，如果命中則結(jié)束，否則進(jìn)入查詢關(guān)鍵字所屬范圍的兒子結(jié)點(diǎn)款咖；重復(fù)何暮，直到所對(duì)應(yīng)的兒子指針為空，或已經(jīng)是葉子結(jié)點(diǎn)
關(guān)鍵字集合分布在整顆樹中,即葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)都存放數(shù)據(jù).搜索有可能在非葉子結(jié)點(diǎn)結(jié)束其搜索性能等價(jià)于在關(guān)鍵字全集內(nèi)做一次二分查找铐殃。
B+樹的介紹
B+樹是B樹的變體海洼，也是一種多路搜索樹。
B+樹的說(shuō)明:
B+樹的搜索與B樹也基本相同富腊，區(qū)別是B+樹只有達(dá)到葉子結(jié)點(diǎn)才命中（B樹可以在非葉子結(jié)點(diǎn)命中）坏逢，其性能也等價(jià)于在關(guān)鍵字全集做一次二分查找
所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中（即數(shù)據(jù)只能在葉子節(jié)點(diǎn)【也叫稠密索引】），且鏈表中的關(guān)鍵字(數(shù)據(jù))恰好是有序的。不可能在非葉子結(jié)點(diǎn)命中
非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引）是整，葉子結(jié)點(diǎn)相當(dāng)于是存儲(chǔ)（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層
更適合文件索引系統(tǒng)
B樹和B+樹各有自己的應(yīng)用場(chǎng)景肖揣，不能說(shuō)B+樹完全比B樹好，反之亦然.
B*樹的介紹
B*樹是B+樹的變體浮入，在B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針龙优。
B*樹的說(shuō)明:
B樹定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)M，即塊的最低使用率為2/3舵盈，而B+樹的塊的最低使用率為B+樹的1/2。
從第1個(gè)特點(diǎn)我們可以看出球化，B*樹分配新結(jié)點(diǎn)的概率比B+樹要低秽晚，空間使用率更高
