1. 二叉樹存在的問題：

二叉樹雖然操作效率比較高，但是如果數(shù)據(jù)一多，就會有好多好多的節(jié)點(diǎn)，需要進(jìn)行好多次的I/O操作，構(gòu)建出來的二叉樹就會很高很高，也會降低操作速度。

2. 怎么解決？

二叉樹因?yàn)槊總€(gè)節(jié)點(diǎn)只能有兩個(gè)子節(jié)點(diǎn)，所以數(shù)據(jù)一多構(gòu)建出來的樹的高度會很高。所以就出現(xiàn)了多叉樹，顧名思義，每個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)，這樣來降低樹的高度。

3. 常見多叉樹：

(1). 2-3樹：

第二層左邊的節(jié)點(diǎn)，有兩個(gè)元素，7和5，它又有3個(gè)子節(jié)點(diǎn)，這就叫做2-3樹，其中節(jié)點(diǎn)7 5稱為3節(jié)點(diǎn)，節(jié)點(diǎn)9稱為2節(jié)點(diǎn)。

2-3樹是最簡單的B樹，它有以下特點(diǎn)：

• 首先它也要滿足排序樹的特點(diǎn)，即左子節(jié)點(diǎn)都比父節(jié)點(diǎn)小，右子節(jié)點(diǎn)都比父節(jié)點(diǎn)大，如果3節(jié)點(diǎn)，那么中間那個(gè)元素要介于左節(jié)點(diǎn)和右節(jié)點(diǎn)之間，即6是介于4和11之間的；

• 所有的葉子節(jié)點(diǎn)都在同一層(B樹都滿足這個(gè)條件)；

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

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

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

(2). 2-3-4樹：

和2-3樹的區(qū)別就是，它還允許節(jié)點(diǎn)有三個(gè)元素且有四個(gè)子節(jié)點(diǎn)。

4. B樹：

B是balance，平衡的意思，所以，B樹首先是一棵平衡樹，而平衡樹首先得是一棵排序樹。所以B樹就是一棵平衡的、排序的多叉樹。B的相關(guān)說明如下：

• B樹的階：節(jié)點(diǎn)的最多子節(jié)點(diǎn)個(gè)數(shù)叫做階。比如2-3樹的階就是3，2-3-4樹的階就是4；

• B樹的搜索：從根節(jié)點(diǎn)開始，對節(jié)點(diǎn)內(nèi)的元素進(jìn)行二分查找，如果找到就結(jié)束，否則進(jìn)入查找元素所屬范圍的子節(jié)點(diǎn)再進(jìn)行二分查找，直到找到或者到達(dá)葉子節(jié)點(diǎn)；

• B樹的所有節(jié)點(diǎn)都會存放數(shù)據(jù)；

5. B+樹：

B+樹是B樹的變體，和B樹的區(qū)別就是，B+樹所有數(shù)據(jù)都存放在葉子節(jié)點(diǎn)。

• B+樹所有的數(shù)據(jù)都存放在葉子節(jié)點(diǎn)的鏈表中，且鏈表中的數(shù)據(jù)也是有序的；

• 非葉子節(jié)點(diǎn)中存放的是索引，而不是要操作的數(shù)據(jù)，每個(gè)非葉子節(jié)點(diǎn)都會存放葉子節(jié)點(diǎn)的索引，也叫稀疏索引；

• B+樹要進(jìn)行搜素時(shí)，從根節(jié)點(diǎn)開始，通過與根節(jié)點(diǎn)索引的比較，就知道要往左子樹查找還是往中間查找還是往右子樹查找，到了子樹的時(shí)候再通過與子樹中存放的索引比較，又可以直到要往那一邊查找。

• B+樹一般用于文件系統(tǒng)；

6. B*樹：

B*樹又是B+樹的變體，就是在B+樹的基礎(chǔ)上，在非根非葉子節(jié)點(diǎn)之間增加了指向兄弟節(jié)點(diǎn)的指針。