B木を作ってみた

　GAEで何かしてみたくてB木を実装してみました。と書きつつPythonでもJavaでもなくJavascriptです。jQuery使ってます。
http://d.hatena.ne.jp/naoya/20090412/btree
ここにPythonによるサンプルコードがあったのでそのままJavascriptに翻訳してみたんですが、なにかおかしい。自分の翻訳が失敗したのか、自分のB木の理解が足りないのか。Pythonのサンプルコード、挿入しようとすると最初にルートのキー数を調べます。とするとたとえば出来上がったB木が、
t=2
ルート：20、30、40
子ノード（小さいほうから）
10
25
35
50、60
だったとします。この場合ノードのキー数は最大でt*2-1で3です。ここで5を挿入しようとすると直感的には10があるノードに挿入されるはずなのに、サンプルコードではルートノードが分割されてしまいます。されないのか？ そもそもB木ってそういうものなのか？
　で、こんがらがってしまったので、サンプルコードを参考にしつつも挿入部分を一から作ってみました。自分の直感には反しないけど、はたして正しいB木なのかは不安。下のリンク先でテストできます。
http://yuribossa.appspot.com/btree
頻繁にノードを分割させたかったので、t=2でやっています。あと、挿入しか実装していません。

var BTree = function(t) {
    this.t = t;
    this.root = new Node(t);
    this.root.isRoot = true;
    this.root.isLeaf = true;
}

BTree.prototype = {
    insert: function(k) {
        this.root = this.root.insert(k);
    },
    delete: function(k) {
    },
    search: function(k) {
        return this.root.search(k);
    },
    show: function() {
        this.root.show(0);
    }
}

var Node = function(t) {
    this.t = t;
    this.keys = [];      // キー配列
    this.children = [];  // 子ノード配列
    this.isRoot = false; // ルートフラグ
    this.isLeaf = false; // 葉っぱフラグ
}

Node.prototype = {
    // キー配列の長さを返す
    len: function() {
        return this.keys.length;
    },
    
    // 検索対象の見つかったノードとその場所を返す
    search: function(k) {
        var i = 0;
        while (i < this.len() && this.keys[i] < k) { i++; }
        
        if (i < this.len() && this.key[i] == k) { return [this, i]; }
        
        if (this.isLeaf) {
            return;
        } else {
            return this.children[i].search(k);
        }
    },
    
    // 子ノードを分割する
    // 親ノードがthis
    splitChild: function(i, leftChild) {
        var t = this.t;
        var rightChild = new Node(t); // 右子ノード
        
        rightChild.isLeaf = leftChild.isLeaf;
        // 分割したいノードの右半分のキーと子ノードを右子ノードに移動
        for (var j=t; j<leftChild.keys.length; j++) { rightChild.keys.push(leftChild.keys[j]); }
        if (!leftChild.isLeaf) {
            for (var j=t; j<leftChild.children.length; j++) { rightChild.children.push(leftChild.children[j]); }
        }
        
        // 親ノードに右子ノードを格納
        for (var j=this.children.length-1; j>=i+1; j--) { this.children[j+1] = this.children[j]; }
        this.children[i+1] = rightChild;
        
        // 親ノードにキーを格納
        for (var j=this.keys.length-1; j>=i; j--) { this.keys[j+1] = this.keys[j]; }
        this.keys[i] = leftChild.keys[t-1];
        
        // 左子ノードから右子ノードへ分割したデータの削除
        var len = leftChild.keys.length;
        for (var j=t-1; j<len; j++) { leftChild.keys.pop(); }
        len = leftChild.children.length;
        for (var j=t; j<len; j++) { leftChild.children.pop(); }
    },
    
    // kが挿入されるべき子ノードの場所を返す
    locateSubtree: function(k) {
        var i = 0;
        while (i < this.len()) {
            if (k < this.keys[i]) {
                return i;
            }
            i++;
        }
        return i;
    },
    
    // B木へのキーの挿入
    // ルートノードを返す
    insert: function(k) {
        if (this.isRoot) {
            if (this.isLeaf) {
                if (this.len() == (2*this.t - 1)) {
                    var s = new Node(this.t);
                    s.children.push(this);
                    s.splitChild(0, this);
                    s.isRoot = true;
                    this.isRoot = false;
                    s.insert(k);
                    return s;
                } else {
                    // キーの挿入
                    for (var i=0; i<this.len(); i++) {
                        if (k < this.keys[i]) {
                            for (var j=this.keys.length-1; j>=i; j--) { this.keys[j+1] = this.keys[j]; }
                            this.keys[i] = k;
                            return this;
                        }
                    }
                    this.keys.push(k);
                }
                return this;
            } else {
                var i = this.locateSubtree(k);
                var c = this.children[i];
                if (!c.insert(k)) {
                    this.splitChild(i, c);
                    if (this.len() > (2*this.t - 1)) {
                        var s = new Node(this.t);
                        s.children.push(this);
                        s.splitChild(0, this);
                        s.isRoot = true;
                        this.isRoot = false;
                        s.insert(k);
                        return s;
                    } else {
                        this.insert(k);
                    }
                }
                return this;
            }
        } else {
            if (this.isLeaf) {
                if (this.len() == (2*this.t - 1)) {
                    // 挿入先ノードが葉っぱノードであり、既にキー配列が満杯のときnullを返す
                    return null;
                } else {
                    // キーの挿入
                    for (var i=0; i<this.len(); i++) {
                        if (k < this.keys[i]) {
                            for (var j=this.keys.length-1; j>=i; j--) { this.keys[j+1] = this.keys[j]; }
                            this.keys[i] = k;
                            return this;
                        }
                    }
                    this.keys.push(k);
                }
                return this;
            } else {
                var i = this.locateSubtree(k);
                var c = this.children[i];
                if (!c.insert(k)) {
                    this.splitChild(i, c);
                    if (this.len() > (2*this.t - 1)) {
                        // 分割して親ノードのキー配列が2t-1より大きくなったら、さらに親ノードを分割するためにnullを返す
                        return null;
                    } else {
                        this.insert(k);
                    }
                }
                return this;
            }
        }
    },
    
    // 階層を空白で表現しB木を表示する
    show: function(pad) {
        var space = "";
        for (var i=0; i<pad; i++) {
            space += "&nbsp; &nbsp; &nbsp;";
        }
        $("#result").append("<p>" + space + this.keys + "</p>");
        if (this.isLeaf) {
            return;
        } else {
            for (var i= 0; i<this.children.length; i++) {
                this.children[i].show(pad+1);
            }
        }
    },
    
    // B木からのキーの削除
    delete: function(k) {
    }
}

tree = new BTree(2);