摘要：因為是大于，因此放右子樹的結點中。第二層右子樹會變成，，第三層的，再分裂，將加到最右邊。合并子樹的根與上層結點決定哪個子樹要添加如果待插入的節點不是節點，那么直接在該節點插入

function Node(key, parent){
   this.parent = null;
   this.keys = [key];
   this.children = []
}

插入2

if(!this.root){
   this.root = new Node(2)
}

插入3

var node = this.search(3);
node.keys.push(3)
node.keys.sort()

插入1

注意這里會排序

var node = this.search(3);
node.keys.push(3)
node.keys.sort()

插入4

var keys = node.keys
if(keys.length === 3){
    var top = new Node(keys[1])
    var left = new Node(keys[0], top);
    var right = new Node(keys[2], top);
    top.children.push(left, right)
    var add = key < keys[1] ? left: right;
    add.keys.push(key)
    add.keys.sort()
}

這時節點已經滿4個key，為4結點（實際上4始終沒有放進去這個節點中），需要進行分裂，首先，根據原來的3結點，取得中間值2，新生成一個Node，將剩下的兩個key，成為它的左右子樹，然后4插入到右子樹中。因為4是大于2，因此放右子樹的結點中。

插入5

這時找到右子樹，成為3結點，key為［3，4，5］

var parent = node.parent;
pushToParent(parent, keys[1])
var children = parent.children;
var index = children.indexOf(node)
var left = new Node(keys[0],parent)
var right = new Node(keys[1],parent)
children.splice(index,1, left, right)

插入6

這次也放右邊，但是已經滿了，需要將4，放到其父親，變成 2，4. 然后當前結點分裂成2個， 現在有3個孩子，6放到最右邊。

插入7

插入8

與上面一樣，沒有驚喜

插入9

插入10

這時，[7,8,9]已經滿了，需要將8放上去，這時發現，［2,4,6］也滿了，只好將4抽出來，變成新的根。第二層右子樹會變成［6，8］，第三層的［7，9］再分裂，將10加到最右邊。

因此我們需要修改putKeyToParent方法，如果返回兩個節點，那么它們就會平分孩子。

插入11

插入12

插入13

插入14

完整的代碼如下：

   class Node {
      constructor(key, parent) {
        this.keys = [key]
        this.children = []
        this.parent = parent
      }
      isLeaf(){
          return !this.children[0]
      }
      addKeys(key){
          this.keys.push(key)
          this.keys.sort(function(a, b){
              return a - b
          })
      }
    }
    class Tree234{
        constructor(){
            this.root = null
        }
        search(node, key){
            if(node.isLeaf()){
                return node
            }
            var keys = node.keys
            for(var i = 0, n = keys.length; i < n; i++){
                if(key < keys[i]){
                   return this.search(node.children[i], key)
                }
            }
            return this.search(node.children[i], key)
        }
        insert(key){
            if(!this.root){//沒有根節點
                this.root = new Node(key)
            }else{
                var node = this.search(this.root, key)
                insertNode(node, key, this)
            }
        }
     
    }
    function insertNode(node, key, tree){
        var keys = node.keys;
        if( keys.length === 3){
            var middle = keys[1], parent = node.parent, p
            //步驟1，確認新的父節點
            if(!parent){ 
                p = tree.root = new Node(middle)
                p.children = [node] //用于步驥2
            }else{
                p = insertNode(parent, middle, tree)
            }
             //步驟2，將目標節點拆成兩個節點，它們的key為原keys[0], keys[1]
            var children = p.children
            var left = new Node(keys[0],p)
            var right = new Node(keys[2],p)
            children.splice(children.indexOf(node),1, left, right)//原位置替換
            //步驟3 將目標節點的children均勻分成 新生成的節點（只有在4結點的情況才這樣做）
            if(node.children.length === 4){
                node.children[0].parent = left
                node.children[1].parent = left
                left.children = [ node.children[0], node.children[1]]
                node.children[2].parent = right
                node.children[3].parent = right
                right.children = [ node.children[2], node.children[3]]
            }
            //步驟4，添加新key
            var target = key < keys[0] ? left : right
            target.addKeys(key)
            return target
        }else{
            node.addKeys(key)
            return node
        }
    }
    var t = new Tree234()
    t.insert(2)
    t.insert(3)
    t.insert(1)
    t.insert(4)
    t.insert(5)
    t.insert(6)
    t.insert(7)
    t.insert(8)
    t.insert(9)
   
    t.insert(10)
    t.insert(11)
    t.insert(12)
    t.insert(13)
    t.insert(14)
    console.log(t)

另一個思路，碰到4結點就先拆成三個2結點，然后讓這個子樹的根與上面的結點進行合并。

      class Node {
            constructor(key, parent) {
                this.keys = [key]
                this.children = []
                this.parent = parent
            }
            isLeaf() {
                return !this.children[0]
            }
            addKeys(key) {
                //(1)如果2-3-4樹中已存在當前插入的key，則插入失敗，
                //否則最終一定是在葉子節點中進行插入操作
                if (!this.keys.includes(key)) {
                    this.keys.push(key)
                    this.keys.sort(function (a, b) {
                        return a - b
                    })
                }

            }
        }
        class Tree234 {
            constructor() {
                this.root = null
            }
            search(node, key) {
                if (node.isLeaf()) {
                    return node
                }
                var keys = node.keys
                for (var i = 0, n = keys.length; i < n; i++) {
                    if (key < keys[i]) {
                        return this.search(node.children[i], key)
                    }
                }
                return this.search(node.children[i], key)
            }
            insert(key) {
                if (!this.root) {//沒有根節點
                    this.root = new Node(key)
                } else {
                    var node = this.search(this.root, key)
                    insertNode(node, key, this)
                }
            }
        }

        function split(keys) { //將4結點的三個key分裂成三個2結吉
            var middle = keys[1]
            var top = new Node(middle)//一個臨時結點
            var left = new Node(keys[0], top)
            var right = new Node(keys[2], top)
            return [top, left, right]
        }
        function insertNode(node, key, tree) {
            var keys = node.keys;
            if (keys.length === 3) {
                var [top, left, right] = split(keys)
                top.children = [left, right]
                var parent = node.parent
                //(3)如果待插入的節點是個4節點，那么應該先分裂該節點然后再插入。
                //一個4節點可以分裂成一個根節點和兩個子節點（這三個節點各含一個key）
                if (node.children.length === 4) {//是4節點
                    node.children[0].parent = left
                    node.children[1].parent = left
                    left.children = [node.children[0], node.children[1]]
                    node.children[2].parent = right
                    node.children[3].parent = right
                    right.children = [node.children[2], node.children[3]]
                }
                if (!parent) {
                    tree.root = top
                } else {
                    //我們把分裂形成的根節點中的key看成向上層插入的key，然后重復第2步和第3步。
                    var newParent = insertNode(parent, top.keys[0], tree)
                    left.parent = newParent
                    right.parent = newParent
                    //合并子樹的根(top)與上層結點（node）
                    var index = newParent.children.indexOf(node)
                    newParent.children.splice(index, 1, left, right)
                }
                //決定哪個子樹要添加key
                node = key < keys[0] ? left : right
            }
            //(2)如果待插入的節點不是4節點，那么直接在該節點插入
            node.addKeys(key)
            return node

        }
        var t = new Tree234()
        t.insert(2)
        t.insert(3)
        t.insert(1)
        t.insert(4)
        t.insert(5)
        t.insert(6)
        t.insert(7)

        t.insert(8)
        t.insert(9)

        t.insert(10)
        t.insert(11)
        t.insert(12)
        t.insert(13)
        t.insert(14)
        console.log(t)