1. 二叉樹的問題分析
二叉樹的操作效率較高钳榨，但是也存在問題, 請(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ì)降低操作速度.
2. 多叉樹
在二叉樹中，每個(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）
后面我們講解的 2-3 樹沉桌，2-3-4 樹就是多叉樹谢鹊，多叉樹通過(guò)重新組織節(jié)點(diǎn)，減少樹的高度留凭，能對(duì)二叉樹進(jìn)行優(yōu)化佃扼。
3. B 樹的基本介紹
B 樹通過(guò)重新組織節(jié)點(diǎn)，降低樹的高度蔼夜，并且減少 i/o 讀寫次數(shù)來(lái)提升效率兼耀。
如圖 B 樹通過(guò)重新組織節(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)中
4. 樹
4.1 樹的特點(diǎn)
樹是最簡(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)成的樹郁季。
4.2. 樹應(yīng)用案例
將數(shù)列{16, 24, 12, 32, 14, 26, 34, 10, 8, 28, 38, 20} 構(gòu)建成 2-3 樹，并保證數(shù)據(jù)插入的大小順序钱磅。
插入規(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ī)則
4.3 其它說(shuō)明
除了 23 樹，還有 234 樹等渴丸，概念和 23 樹類似侯嘀，也是一種 B 樹。
5. B 樹的介紹
B-tree 樹即 B 樹谱轨，B 即 Balanced戒幔，平衡的意思。有人把 B-tree 翻譯成 B-樹土童，容易讓人產(chǎn)生誤解诗茎。會(huì)以為 B-樹是一種樹，而 B 樹又是另一種樹献汗。實(shí)際上敢订，B-tree 就是指的 B 樹
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)做一次二分查找
6. B+樹
B+樹是 B 樹的變體啊易，也是一種多路搜索樹吁伺。
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 樹好，反之亦然
7. B*樹
B*樹是 B+樹的變體呻逆，在 B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針夸赫。
B樹定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)M，即塊的最低使用率為 2/3咖城，而 B+樹的塊的最低使用率為的1/2茬腿。
從第 1 個(gè)特點(diǎn)我們可以看出呼奢，B*樹分配新結(jié)點(diǎn)的概率比 B+樹要低，空間使用率更高
