btree.js

var gid = (function (i) {
    return function () {
      return i++;
    }
  })(0);

function searchPos(arr, key) {
for (var i = 0; i < arr.length; i++) {
 if (arr[i]>key) return i;
}
return arr.length;
}

var _slice = Array.prototype.slice;
function arrayInsert(arr, index, value) {
var tmp = _slice.call(arr, 0, index);
tmp.push(value); 
return tmp.concat(_slice.call(arr, index));
}

function checkBalance(node,level) {
level = level || 0;
if (node.childs.length === 0) {
return level;
}
var curLevel, curChild, maxLevel=-1;
for(var i = 0; i < node.childs.length; i++) {
curChild = node.childs[i];
curLevel = checkBalance(curChild, level+1);
if (curLevel === false) return false;
if (maxLevel < curLevel) maxLevel = curLevel;
if (Math.abs(maxLevel - curLevel) > 1) return false;
}
return maxLevel;
}

function BTreeNode(parent) {
this.id=gid();
this.childs=[];
this.keys=[];
this.parent=parent;
};
BTreeNode.MINIMAL_DEGREE = 3;
BTreeNode.createRoot = function() { return new BTreeNode(null); }
BTreeNode.addKeyAndGetRoot = function(root, key) { root.addKey(key); return root.parent !== null ? root.parent : root; }

BTreeNode.prototype.addKey = function(key) {console.log('addKey', this.id, key);
if (this.keys.length === 0) { console.log('simple');this.keys.push(key); return true; }
// if (key < this.keys[0] || key > this.keys[this.keys.length-1]) { console.log('!in range'); return false;}
if (this.filled()) this._divide();
var i=searchPos(this.keys, key);
console.log('index', i);
if (this.childs.length === 0) { console.log('insert in this'); this.keys = arrayInsert(this.keys, i, key); return this; }
console.log('insert in #', i);
return this.childs[i].addKey(key);
}

BTreeNode.prototype.filled = function() { return this.keys.length >= (2 * BTreeNode.MINIMAL_DEGREE - 1); }
BTreeNode.prototype._insertKeyAndCreateRightChild = function(key) {
var i = searchPos(this.keys, key);
this.keys = arrayInsert(this.keys, i, key);
this.childs = arrayInsert(this.childs, i+1, new BTreeNode(this));
return this;
}
BTreeNode.prototype._divide = function() {
if (this.parent === null) { this.parent = new BTreeNode(null); this.parent.childs.push(this); }
var rightNode = this.parent._insertKeyAndCreateRightChild(this.keys[BTreeNode.MINIMAL_DEGREE]);
rightNode.keys = this.keys.slice(BTreeNode.MINIMAL_DEGREE + 1);
this.keys = this.keys.slice(0, BTreeNode.MINIMAL_DEGREE - 1);
}
function BTree() {
this.root = BTreeNode.createRoot();
}
BTree.prototype.addKey = function(key) { this.root = BTreeNode.addKeyAndGetRoot(this.root, key); }

t = new BTree();
keys = [1,2,3,4,17,31,7,9,11,13,16,19,26,27,96,97,99];
for (var i = 0; i<keys.length; i++) { t.addKey(keys[i]); }
// see http://habrahabr.ru/post/114154/
// test failed!!!