12.1二叉樹和B樹

12.1.1二叉樹的問題分析

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

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

2)????? 問題1:在構(gòu)建二叉樹時(shí)，需要多次進(jìn)行io操作(海量數(shù)據(jù)存在數(shù)據(jù)庫或文件中)，節(jié)點(diǎn)海量，構(gòu)建二叉樹時(shí)，速度有影響

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

12.1.2多叉樹

1)????? 在二叉樹中，每個(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)????? 后面我們講解的2-3樹，2-3-4樹就是多叉樹，多叉樹通過重新組織節(jié)點(diǎn)，減少樹的高度，能對二叉樹進(jìn)行優(yōu)化。

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

12.1.3B樹的基本介紹

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

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

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

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

12.2 2-3樹

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

1)????? 2-3樹的所有葉子節(jié)點(diǎn)都在同一層.(只要是B樹都滿足這個(gè)條件)

2)????? 有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)叫二節(jié)點(diǎn)，二節(jié)點(diǎn)要么沒有子節(jié)點(diǎn)，要么有兩個(gè)子節(jié)點(diǎn)

3)????? 有三個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)叫三節(jié)點(diǎn)，三節(jié)點(diǎn)要么沒有子節(jié)點(diǎn)，要么有三個(gè)子節(jié)點(diǎn)

4)????? 2-3樹是由二節(jié)點(diǎn)和三節(jié)點(diǎn)構(gòu)成的樹。

12.2.2 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樹的過程.)

說明

1.當(dāng)插入10時(shí)，應(yīng)當(dāng)在10-12-14這個(gè)位置，但是這時(shí)滿了，因此向上層看，16-26也滿了

2.因此將10-12-14拆成10<-12->14,因?yàn)槠渌鸱?不能滿足二節(jié)點(diǎn)或三節(jié)點(diǎn)的要求,

3.但是這時(shí)，葉子節(jié)點(diǎn)沒有全部在同一層,需要調(diào)整26這個(gè)值到下面如圖

插入規(guī)則:

1)????? 2-3樹的所有葉子節(jié)點(diǎn)都在同一層.(只要是B樹都滿足這個(gè)條件)

2)????? 有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)叫二節(jié)點(diǎn)，二節(jié)點(diǎn)要么沒有子節(jié)點(diǎn)，要么有兩個(gè)子節(jié)點(diǎn)

3)????? 有三個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)叫三節(jié)點(diǎn)，三節(jié)點(diǎn)要么沒有子節(jié)點(diǎn)，要么有三個(gè)子節(jié)點(diǎn)

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

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

12.2.3其他說明

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

12.3 B樹、B+樹和B*樹

12.3.1 B樹的價(jià)紹

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

12.3.2 B樹的介紹

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

對上圖的說明

1)????? B樹的階:節(jié)點(diǎn)的最多子節(jié)點(diǎn)個(gè)數(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)????? 其搜索性能等價(jià)于在關(guān)鍵字全集內(nèi)做一次二分查找

12.3.3 B+樹的介紹

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

對上圖的說明

1)????? B+樹的搜索與B樹也基本相同，區(qū)別是B+樹只有達(dá)到葉子結(jié)點(diǎn)才命中(B樹可以在非葉子結(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)于是存儲(關(guān)鍵寧)數(shù)據(jù)的數(shù)據(jù)層

5)????? 更適合文件索引系統(tǒng)

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

12.3.4 B*樹的介紹

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

B*樹的說明:

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

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

學(xué)就完事了兄弟們！加油！奧力給！