二叉查找樹(BST)，平衡二叉查找樹(AVL)，紅黑樹(RBT)，B~/B+樹(B-tree）

動态查找樹：二叉查找樹(BST)、平衡二叉查找樹(AVL)、紅黑樹(RBT)、B~/B+樹(B-tree)

1、都是動态結構。在删除，插入操作的時候，都不需要徹底重建原始的索引樹。最多就是執行一定量的旋轉，變色操作來有限的改變樹的形态。而這些操作所付出的代價都遠遠小于重建一棵樹。

2、查找的時間複雜度大體維持在O(log(N))數量級。可能有些結構在最差的情況下效率将會下降很快，比如BST。

動态查找樹結構的對比：

1)、平衡二叉樹和紅黑樹[AVL & RBT]

AVL 和RBT 都是二叉查找樹的優化。其性能要遠遠好于二叉查找樹。

結構對比： AVL的結構高度平衡，RBT的結構基本平衡。平衡度AVL > RBT.

查找對比： AVL查找時間複雜度最好，最壞情況都是O(logN)。RBT查找時間複雜度最好為O(logN)，最壞情況下比AVL略差。

插入删除對比：

1、AVL的插入和删除結點很容易造成樹結構的不平衡，而RBT的平衡度要求較低。是以在大量資料插入的情況下，RBT需要通過旋轉變色操作來重新達到平衡的頻度要小于AVL。

2、如果需要平衡處理時，RBT比AVL多一種變色操作，而且變色的時間複雜度在O(logN)數量級上。但是由于操作簡單，是以在實踐中這種變色仍然是非常快速的。

3、當插入一個結點都引起了樹的不平衡，AVL和RBT都最多需要2次旋轉操作。但删除一個結點引起不平衡後，AVL最多需要logN 次旋轉操作，而RBT最多隻需要3次。是以兩者插入一個結點的代價差不多，但删除一個結點的代價RBT要低一些。

4、AVL和RBT的插入删除代價主要還是消耗在查找待操作的結點上。是以時間複雜度基本上都是與O(logN) 成正比的。

大量資料實踐證明，RBT的總體統計性能要好于平衡二叉樹。

2)、B~樹和B+樹[B~Tree & B+Tree]

B+樹是B~樹的一種變體，在磁盤查找結構中，B+樹更适合檔案系統的磁盤存儲結構。

結構對比：

B~樹是平衡多路查找樹，所有結點中都包含了待查關鍵字的有效資訊(比如檔案磁盤指針)。每個結點若有n個關鍵字，則有n+1個指向其他結點的指針。

B+樹嚴格意義上說已經不是樹，它的葉子結點之間也有指針連結。B+樹的非終結點中并不含有關鍵字的資訊，需要查找的關鍵字的全部資訊都包含在葉子結點上。非終結點中隻作為葉子結點關鍵字的索引而存在。

查找對比：

1、在相同數量的待查資料下，B+樹查找過程中需要調用的磁盤IO操作要少于普通B~樹。由于B樹所在的磁盤存儲背景下，是以B+樹的查找性能要好于B~樹。

2、B+樹的查找效率更加穩定，因為所有葉子結點都處于同一層中，而且查找所有關鍵字都必須走完從根結點到葉子結點的全部曆程。是以同一顆B+樹中，任何關鍵字的查找比較次數都是一樣的。而B樹就不一定了，可能查找到某一個非終結點就結束了。

插入删除對比：

B+樹與B~樹在插入删除操作中的效率是差不多的。

在應用背景下，特别是檔案結構存儲中。B+樹的應用要更多，其效率也要比B~樹好。

繼續閱讀