1. 二叉樹存在的問題：

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

2. 怎么解決？

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

3. 常見多叉樹：

(1). 2-3樹：

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

2-3樹是最簡單的B樹，它有以下特點：

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

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

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

• 有三個子節(jié)點的節(jié)點叫三節(jié)點，三節(jié)點要么有三個子節(jié)點，要么沒有子節(jié)點；

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

(2). 2-3-4樹：

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

4. B樹：

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

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

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

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

5. B+樹：

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

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

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

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

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

6. B*樹：

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