1. 2-3-4樹的定義
2-3-4樹是一種階為4的B樹。它是一種自平衡的數(shù)據(jù)結(jié)構(gòu)，可以保證在O(lgn)的時間內(nèi)完成查找、插入和刪除操作。它主要滿足以下性質(zhì)：
（1）每個節(jié)點每個節(jié)點有1、2或3個key，分別稱為2（孩子）節(jié)點，3（孩子）節(jié)點，4（孩子）節(jié)點。
（2）所有葉子節(jié)點到根節(jié)點的長度一致（也就是說葉子節(jié)點都在同一層）。
（3）每個節(jié)點的key從左到右保持了從小到大的順序，兩個key之間的子樹中所有的
key一定大于它的父節(jié)點的左key，小于父節(jié)點的右key。
2. 插入操作
（1）如果2-3-4樹中已存在當前插入的key，則插入失敗，否則最終一定是在葉子節(jié)點中進行插入操作
（2）如果待插入的節(jié)點不是4節(jié)點，那么直接在該節(jié)點插入
（3）如果待插入的節(jié)點是個4節(jié)點，那么應該先分裂該節(jié)點然后再插入。一個4節(jié)點可以分裂成一個根節(jié)點和兩個子節(jié)點（這三個節(jié)點各含一個key）然后在子節(jié)點中插入，我們把分裂形成的根節(jié)點看成向上層插入的節(jié)點，然后重復第2步和第3步。
如果是在4節(jié)點中進行插入，每次插入會多出一個分支，如果插入操作導致根節(jié)點分裂，則2-3-4樹會生長一層。
