一、2-3-4樹的定義
2-3-4樹就是一種4階的多叉樹，它像紅黑樹一樣是平衡樹，可以保證在O(lgn)的時間内完成查找、插入和删除操作，容易實作，但是效率比紅黑樹稍差。
2-3-4樹每個節點最多有四個位元組點和三個資料項，名字中 2,3,4 的數字含義是指一個節點可能含有的子節點的個數。對于非葉節點有三種可能的情況：
- 有一個資料項的節點總是有兩個子節點；
- 有二個資料項的節點總是有三個子節點；
- 有三個資料項的節點總是有四個子節點。
簡而言之，非葉節點的子節點數總是比它含有的資料項多1。如果子節點個數為L，資料項個數為D，那麼：L = D + 1。
二、操作
建構一個數組為{7,1,2,5,6,9,8,4,3}的2-3-4樹的過程：
2-3-4樹的插入：
2-3-4樹的删除：
三、效率
分析2-3-4樹我們可以和紅黑樹作比較分析。紅-黑樹的層數（平衡二叉樹）大約是log2(N+1)，而2-3-4樹每個節點可以最多有4個資料項，如果節點都是滿的，那麼高度和log4N。是以在所有節點都滿的情況下，2-3-4樹的高度大緻是紅-黑樹的一半。不過他們不可能都是滿的，是以2-3-4樹的高度大緻在log2(N+1)和log2(N+1)/2。減少2-3-4樹的高度可以使它的查找時間比紅-黑樹的短一些。
但是另一方面，每個節點要檢視的資料項就多了，這會增加查找時間。因為節點中用線性搜尋來檢視資料項，使得查找時間的倍數和M成正比，即每個節點資料項的平均數量。總的查找時間和M*log4N成正比。
四、2-3樹
2-3樹是一棵自平衡的多路查找樹，它并不是一棵二叉樹，具有如下性質：
- 每個節點有1個或2個key，對應的子節點為2個子節點或3個子節點；
- 所有葉子節點到根節點的長度一緻；
- 每個節點的key從左到右保持了從小到大的順序，兩個key之間的子樹中所有的key一定大于它的父節點的左key，小于父節點的右key。
2-3-4樹隻是在2-3樹的基礎上進行了擴充，任一節點隻能是1個或2個或3個key，對應的子節點為2個子節點或3個子節點或4個子節點。
五、2-3-4樹跟紅黑樹的轉化
Java HashMap的紅黑樹是普通的紅黑樹，既可以左旋也可以右旋的。紅黑樹從根到葉子節點的最長路徑不會超過最短路徑的二倍。紅黑樹是黑色平衡的，即從根節點到所有葉子節點的路徑，經過的黑色的節點數是相等的。 本質上來說，紅黑樹這個資料結構的基本思想源自于階數為4的B樹(也就是2-3-4樹)。
等同于
2-3-4 樹是紅黑樹的一種等同，這意味着它們是等價的資料結構。換句話說，對于每個 2-3-4 樹，都存在着至少一個資料元素是相同次序的紅黑樹。在 2-3-4 樹上的插入和删除操作也等價于在紅黑樹中的顔色翻轉和旋轉。這使得它成為了解紅黑樹背後的邏輯的重要工具。
是以對于紅黑樹的插入等操作，可以類比4階B樹的相關操作。
1. 要将一個節點A插入，首先要将該節點的key值與樹中的節點Key值相比較，最後找到一個正确的null節點位置，然後替換此null節點。此時節點A的顔色為紅色。
2. if A節點父節點為黑色，那麼插入過程結束，因為紅色的節點不會影響紅黑樹的平衡
if A節點父節點為紅色，那麼此時要看A節點的父節點的兄弟節點，也就是A節點的叔叔節點：
if A節點沒有叔叔節點，則進行紅黑樹的旋轉操作（左旋或右旋），最後的情況是，A節點的爺爺節點的位置由A節點的父節點替換了，A節點原來的爺爺節點在旋轉後成為了A節點的父節點的子節點，也就是A節點的爺爺節點成為了A節點的兄弟節點。注意，旋轉的過程中，不光A節點的父節點與爺爺節點的位置要變換，兩個節點的顔色也要變：
插入14 →
a
if A節點有叔叔節點（可知A節點的叔叔節點顔色應該與A節點的父節點相同，即為紅色） 則将A節點的父節點和叔叔節點顔色全部置為黑色，而将A節點的爺爺節點的顔色置為紅色，以保證整個紅黑樹仍然是黑色平衡的。 此時A節點的爺爺節點為紅色，可能會導緻不再滿足紅黑樹的限制，是以要對變成紅色的爺爺節點進行與插入A節點時相同的操作，來維持整個紅黑樹的平衡，這個過程可能是一個遞歸的過程。
插入9 →
六、總結
2-3樹和2-3-4樹都是多路查找樹。每一個結點的孩子數可以多于兩個，且每一個結點處可以存儲多個元素。由于它是查找樹，所有元素之間存在某種特定的排序關系。
2-3-4 樹是紅黑樹的一種等同，這意味着它們是等價的資料結構。