[[391530]]

 二叉樹(shù)的問(wèn)題分析

二叉樹(shù)的操作效率高，但是也存在問(wèn)題，請(qǐng)看下面的二叉樹(shù)

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

1. 在構(gòu)建二叉樹(shù)時(shí)，需要多次進(jìn)行I/O操作(海量數(shù)據(jù)存在數(shù)據(jù)庫(kù)或文件中)，節(jié)點(diǎn)海量，構(gòu)建樹(shù)時(shí)，速度有影響。
2. 節(jié)點(diǎn)海量，也會(huì)造成二叉樹(shù)的高度很大，會(huì)降低操作速度。

多叉樹(shù)

1. 在二叉樹(shù)中，每個(gè)節(jié)點(diǎn)有數(shù)據(jù)項(xiàng)，最多有兩個(gè)子節(jié)點(diǎn)。如果允許每個(gè)節(jié)點(diǎn)可以有更多的數(shù)據(jù)項(xiàng)和更多的節(jié)點(diǎn)，就是多叉樹(shù)(multiway tree).
2. 如2-3樹(shù)，2-3-4樹(shù)就是多叉樹(shù)，多叉樹(shù)通過(guò)重新組織節(jié)點(diǎn)，減少樹(shù)的高度，能對(duì)二叉樹(shù)進(jìn)行優(yōu)化。
3. 舉例說(shuō)明(下面的2-3樹(shù))就是一顆多叉樹(shù)

B樹(shù)的基本介紹

B-Tree 樹(shù)即B樹(shù)，B即Balanced，平衡的意思。在mysql中說(shuō)某種類型的索引是基于B樹(shù)或者B+樹(shù)，如下圖：

B樹(shù)說(shuō)明：

1. B樹(shù)的階：節(jié)點(diǎn)的最多子節(jié)點(diǎn)個(gè)數(shù)，比如2-3樹(shù)的階是3，2-3-4樹(shù)的階是4.
2. B樹(shù)的搜索：從根節(jié)點(diǎn)開(kāi)始，對(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)。
3. 關(guān)鍵字集合分布在整棵樹(shù)中，即葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)都存放數(shù)據(jù)。
4. 搜索可能在非葉子節(jié)點(diǎn)結(jié)束
5. 其搜索性能等價(jià)于在關(guān)鍵字內(nèi)全集做一次二分查找。

B樹(shù)通過(guò)重新組織節(jié)點(diǎn)，降低樹(shù)的高度，并減少I/O讀寫(xiě)次數(shù)來(lái)提升效率。

1. 如圖B樹(shù)通過(guò)重新組織節(jié)點(diǎn)，降低了樹(shù)的高度。
2. 文件系統(tǒng)及數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)者利用了磁盤(pán)預(yù)讀原理，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè)(頁(yè)的大小通常為4k)，這樣每個(gè)節(jié)點(diǎn)只需一次I/O就可以完全載入。
3. 將樹(shù)的度M(樹(shù)中某個(gè)父節(jié)點(diǎn)含有最多子節(jié)點(diǎn)的個(gè)數(shù))設(shè)置為1024，在600億個(gè)元素中，最多只需4次I/O操作就可以讀取到想要的元素，B樹(shù)廣泛用于文件存儲(chǔ)系統(tǒng)及數(shù)據(jù)庫(kù)系統(tǒng)中。

B+樹(shù)基本介紹

B+樹(shù)是B樹(shù)的變體，也是一種多路查找樹(shù)

B+樹(shù)說(shuō)明：

1. B+樹(shù)的搜索與B樹(shù)也基本相同，區(qū)別是B+樹(shù)只有達(dá)到葉子節(jié)點(diǎn)才能命中(B樹(shù)可以在非葉子節(jié)點(diǎn)命中)，其性能也等價(jià)于在關(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)于是存儲(chǔ)(關(guān)鍵字)數(shù)據(jù)的數(shù)據(jù)層。
5. 更適合文件索引系統(tǒng)。
6. B樹(shù)和B+樹(shù)各有自己的場(chǎng)景，不能說(shuō)B+樹(shù)完全比B樹(shù)好，反之亦然。

B*樹(shù)基本介紹

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

B 樹(shù)說(shuō)明：*

1. B*樹(shù)定義了非葉子節(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)*M，即塊的最低使用率為2/3，而B(niǎo)+樹(shù)的塊的最低使用率1/2。
2. 從第一個(gè)特點(diǎn)可以看出，B*樹(shù)分配新節(jié)點(diǎn)的概率要比B+樹(shù)要低，空間使用率更高。

2-3樹(shù)基本介紹(最簡(jiǎn)單的B樹(shù))

2-3樹(shù)是最簡(jiǎn)單的B-樹(shù)結(jié)構(gòu)，具有如下特點(diǎn)：

1. 2-3樹(shù)的所有葉子節(jié)點(diǎn)都在同一層。(只要是B樹(shù)都滿足這個(gè)條件)
2. 有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)叫做二節(jié)點(diǎn)，二節(jié)點(diǎn)要么沒(méi)有子節(jié)點(diǎn)，要么有兩個(gè)子節(jié)點(diǎn)。
3. 有三個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)叫做三節(jié)點(diǎn)，三節(jié)點(diǎn)要么沒(méi)有子節(jié)點(diǎn)，要么有三個(gè)子節(jié)點(diǎn)。
4. 2-3是由二節(jié)點(diǎn)和三節(jié)點(diǎn)構(gòu)成的樹(shù)。

2-3樹(shù)的插入規(guī)則：

1. 2-3樹(shù)的所有葉子節(jié)點(diǎn)都在同一層。(只要是B樹(shù)都滿足這個(gè)條件)。
2. 有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)叫做二節(jié)點(diǎn)，二節(jié)點(diǎn)要么沒(méi)有子節(jié)點(diǎn)，要么有兩個(gè)子節(jié)點(diǎn)。
3. 有三個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)叫做三節(jié)點(diǎn)，三節(jié)點(diǎn)要么沒(méi)有子節(jié)點(diǎn)，要么有三個(gè)子節(jié)點(diǎn)。
4. 當(dāng)按照規(guī)則插入一個(gè)數(shù)到某個(gè)節(jié)點(diǎn)時(shí)，不能滿足上面三個(gè)要求，就需要拆，先向上拆，如果上層滿，則拆本層，拆后仍然需要滿足上面三個(gè)條件。
5. 對(duì)于三節(jié)點(diǎn)的子樹(shù)的值大小仍然滿足(BST二叉排序樹(shù))的規(guī)則。