總目錄：地址如下看總綱
1、二叉樹所存在的問題：
1、二叉樹需要加載到內(nèi)存的，如果二叉樹的節(jié)點(diǎn)少，沒有什么問題，但是如果二叉樹的節(jié)點(diǎn)很多(比如1億)， 就存在如下問題:
- 問題一：在構(gòu)建二叉樹時，需要多次進(jìn)行i/o操作(海量數(shù)據(jù)存在數(shù)據(jù)庫或文件中)，節(jié)點(diǎn)海量，構(gòu)建二叉樹時，速度有影響
問題2：節(jié)點(diǎn)海量，也會造成二叉樹的高度很大，會降低操作速度
image.png
2、多叉樹
1、在二叉樹中，每個節(jié)點(diǎn)有數(shù)據(jù)項，最多有兩個子節(jié)點(diǎn)。如果允許每個節(jié)點(diǎn)可以有更多的數(shù)據(jù)項和更多的子節(jié)點(diǎn)，就是多叉樹（multiway tree）
2、2-3樹，2-3-4樹都是多叉樹，多叉樹通過重新組織節(jié)點(diǎn)，減少樹的高度，能對二叉樹進(jìn)行優(yōu)化。
3、以下的 2-3 樹 ，既是一顆多叉樹
image.png
3、B樹的基本介紹
1、概要：
B樹通過重新組織節(jié)點(diǎn)，降低樹的高度，并且減少i/o讀寫次數(shù)來提升效率。
2、舉例詳解：
1、如下圖B樹通過重新組織節(jié)點(diǎn)， 降低了樹的高度
2、文件系統(tǒng)及數(shù)據(jù)庫系統(tǒng)的設(shè)計者利用了磁盤預(yù)讀原理，將一個節(jié)點(diǎn)的大小設(shè)為等于一個頁(頁得大小通常為4k)，這樣每個節(jié)點(diǎn)只需要一次I/O就可以完全載入
3、將樹的度M設(shè)置為1024，在600億個元素中最多只需要4次I/O操作就可以讀取到想要的元素, B樹(B+)廣泛應(yīng)用于文件存儲系統(tǒng)以及數(shù)據(jù)庫系統(tǒng)中
image.png
4、2-3樹介紹
1、2-3樹是最簡單的B樹結(jié)構(gòu), 具有如下特點(diǎn)：
（1）2-3樹的所有葉子節(jié)點(diǎn)都在同一層.(只要是B樹都滿足這個條件)
（2）有兩個子節(jié)點(diǎn)的節(jié)點(diǎn)叫二節(jié)點(diǎn)，二節(jié)點(diǎn)要么沒有子節(jié)點(diǎn)，要么有兩個子節(jié)點(diǎn).
（3）有三個子節(jié)點(diǎn)的節(jié)點(diǎn)叫三節(jié)點(diǎn)，三節(jié)點(diǎn)要么沒有子節(jié)點(diǎn)，要么有三個子節(jié)點(diǎn).
（4）2-3樹是由二節(jié)點(diǎn)和三節(jié)點(diǎn)構(gòu)成的樹。
2、2-3樹的構(gòu)建過程
（1）插入規(guī)則：
1、2-3樹的所有葉子節(jié)點(diǎn)都在同一層.(只要是B樹都滿足這個條件)
2、有兩個子節(jié)點(diǎn)的節(jié)點(diǎn)叫二節(jié)點(diǎn)，二節(jié)點(diǎn)要么沒有子節(jié)點(diǎn)，要么有兩個子節(jié)點(diǎn)
3、有三個子節(jié)點(diǎn)的節(jié)點(diǎn)叫三節(jié)點(diǎn)，三節(jié)點(diǎn)要么沒有子節(jié)點(diǎn)，要么有三個子節(jié)點(diǎn)
4、當(dāng)按照規(guī)則插入一個數(shù)到某個節(jié)點(diǎn)時，不能滿足上面三個要求，就需要拆，先向上拆，如果上層滿，則拆本層，拆后仍然需要滿足上面3個條件。
5、對于三節(jié)點(diǎn)的子樹的值大小仍然遵守(BST 二叉排序樹)的規(guī)則
（2）圖解過程：原圖可以見 git地址
2-3樹插入過程1.png
2-3樹插入過程2.png
2-3樹插入過程3.png
（3）除了23樹，還有234樹等，概念和23樹類似，也是一種B樹。 如圖:
image.png
5、B樹展開說明
我們在學(xué)習(xí)Mysql時，經(jīng)常聽到說某種類型的索引是基于B樹或者B+樹的，如圖：
1、B樹的階：節(jié)點(diǎn)的最多子節(jié)點(diǎn)個數(shù)。比如2-3樹的階是3，2-3-4樹的階是4
2、B樹的搜索，從根結(jié)點(diǎn)開始，對結(jié)點(diǎn)內(nèi)的關(guān)鍵字（有序）序列進(jìn)行二分查找，如果命中則結(jié)束，否則進(jìn)入查詢關(guān)鍵字所屬范圍的兒子結(jié)點(diǎn)；重復(fù)，直到所對應(yīng)的兒子指針為空，或已經(jīng)是葉子結(jié)點(diǎn)
3、關(guān)鍵字集合分布在整顆樹中, 即葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)都存放數(shù)據(jù)
4、搜索有可能在非葉子結(jié)點(diǎn)結(jié)束
5、其搜索性能等價于在關(guān)鍵字全集內(nèi)做一次二分查找
image.png
6、B+樹展開說明
B+樹是B樹的變體，也是一種多路搜索樹
1、B+樹的搜索與B樹也基本相同，區(qū)別是B+樹只有達(dá)到葉子結(jié)點(diǎn)才命中（B樹可以在非葉子結(jié)點(diǎn)命中），其性能也等價于在關(guān)鍵字全集做一次二分查找
2、所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中（即數(shù)據(jù)只能在葉子節(jié)點(diǎn)【也叫稠密索引】），且鏈表中的關(guān)鍵字(數(shù)據(jù))恰好是有序的。
3、不可能在非葉子結(jié)點(diǎn)命中
4、非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引），葉子結(jié)點(diǎn)相當(dāng)于是存儲（關(guān)鍵字）數(shù)據(jù)的，所以數(shù)據(jù)層更適合文件索引系統(tǒng)
5、B樹和B+樹各有自己的應(yīng)用場景，不能說B+樹完全比B樹好，反之亦然
image.png
7、B*樹展開說明
B*樹是B+樹的變體，在B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針
1、B*樹定義了非葉子結(jié)點(diǎn)關(guān)鍵字個數(shù)至少為(2/3)*M，即塊的最低使用率為2/3，而B+樹的塊的最低使用率為B+樹的1/2。
2、從第1個特點(diǎn)我們可以看出，B*樹分配新結(jié)點(diǎn)的概率比B+樹要低，空間使用率更高
image.png
