bptree-node-test.js

var Class = require('./class').Class; // tested with v0.3.0-3-e1e4628 @ http://github.com/visionmedia/class.js

var LeafNode = new Class({
 
	constructor: function(order){
		this.order = order;
		this.isLeafNode = true;
		this.isInternalNode = false;
 
		this.parentNode = null;
		this.nextNode = null;
		this.prevNode = null;
 
		this.data = [];
	},
 
	split: function(){
		var tmp = new LeafNode(this.order);
		var m = Math.ceil(this.data.length / 2);
		var k = this.data[m-1].key;
 
		// Copy & shift data
		for(var i=0; i<m; i++){
			tmp.data[i] = this.data.shift();
		}
		tmp.parentNode = this.parentNode;
		tmp.nextNode = this;
		tmp.prevNode = this.prevNode;
		if(tmp.prevNode) tmp.prevNode.nextNode = tmp;
		this.prevNode = tmp;
 
		if(!this.parentNode){
			var p = new InternalNode(this.order);
			this.parentNode = tmp.parentNode = p;
		}
 
		return this.parentNode.insert(k, tmp, this);
	},
 
	insert: function(key, value){
		var pos = 0;
		for(; pos<this.data.length; pos++){
			if(this.data[pos].key == key) {
				this.data[pos].value = value;
				return null;
			}
			if(this.data[pos].key > key) break;
		}
 
		if(this.data[pos]) this.data.splice(pos, 0, {"key": key, "value": value});
		else this.data.push({"key": key, "value": value});
 
		// Split
		if(this.data.length > this.order) return this.split();
		return null;
	}
 
});
 
var InternalNode = new Class({
 
	constructor: function(order){
		this.order = order;
		this.isLeafNode = false;
		this.isInternalNode = true;
 
		this.parentNode = null;
 
		this.data = [];
	},
 
	split: function(){
		var m = null;
		if(this.order % 2){
			var m = (this.data.length-1)/2 - 1;
		}else{
			var m = (this.data.length-1)/2;
		}
 
		var tmp = new InternalNode(this.order);
		tmp.parentNode = this.parentNode;
		for(var i=0; i<m; i++){
			tmp.data[i] = this.data.shift();
		}
		for(var i=0; i<tmp.data.length; i+=2){
			tmp.data[i].parentNode = tmp;
		}
		var key = this.data.shift();
 
		if(!this.parentNode){
			this.parentNode = tmp.parentNode = new InternalNode(this.order);
		}
 
		return this.parentNode.insert(key, tmp, this);
	},
 
	insert: function(key, node1, node2){
		if(this.data.length){
			var pos = 1;
			for(; pos < this.data.length; pos+=2){
				if(this.data[pos] > key) break;
			}
 
			if(this.data[pos]) {
				pos--;
				this.data.splice(pos, 0, key);
				this.data.splice(pos, 0, node1);
			}else{
				this.data[pos-1] = node1;
				this.data.push(key);
				this.data.push(node2);
			}
 
			if(this.data.length > (this.order*2+1)){
				return this.split();
			}
			return null;
		}else{
			this.data[0] = node1;
			this.data[1] = key;
			this.data[2] = node2;
			return this;
		}
	}
 
});
 
 
var BPlusTree = new Class({
 
	//Implements: [Options],
 
	options: {
		order: 2 // Min 1
	},
 
	constructor: function(options){
		//this.setOptions(options);
		this.options = options;
		this.root = new LeafNode(this.options.order);
	},
 
	set: function(key, value){
		var node = this._search(key);
		var ret = node.insert(key, value);
		if(ret) this.root = ret;
	},
 
	get: function(key){
		var node = this._search(key);
		for(var i=0; i<node.data.length; i++){
			if(node.data[i].key == key) return node.data[i].value;
		}
		return null;
	},
 
	getNode: function(key){
		return this._search(key);
	},
 
	_search: function(key){
		var current = this.root;
		var found = false;
 
		while(current.isInternalNode){
			found = false;
			var len = current.data.length;
			for(var i=1; i<len; i+=2){
				if( key <= current.data[i]) {
					current = current.data[i-1];
					found = true;
					break;
				}
			}
 
			// Follow infinity pointer
			if(!found) current = current.data[len - 1];
		}
 
		return current;
	},
 
	// B+ tree dump routines
	walk: function(node, level, arr){
		var current = node;
		if(!arr[level]) arr[level] = [];
 
		if(current.isLeafNode){
			for(var i=0; i<current.data.length; i++){
				arr[level].push("<"+current.data[i].key+">");
			}
			arr[level].push(" -> ");
		}else{
 
			for(var i=1; i<node.data.length; i+=2){
				arr[level].push("<"+node.data[i]+">");
			}
			arr[level].push(" -> ");
			for(var i=0; i<node.data.length; i+=2) {
				this.walk(node.data[i], level+1, arr);
			}
 
		}
		return arr;
	},
 
	dump: function(){
		var arr = [];
		this.walk(this.root, 0, arr);
		for(var i=0; i<arr.length; i++){
			var s = "";
			for(var j=0; j<arr[i].length; j++){
				s += arr[i][j];
			}
			console.log(s);
		}
	}
});

var num = 500000;
var key = "key"+250000;
var key1 = "key"+200000;
var key2 = "key"+300000;

var searchCount = 1000;

// Populate time
var start = (new Date()).getTime();
var tree = new BPlusTree({order: 100});
for(var i=0; i<num; i++){
	tree.set("key"+i, i+" - value");
}
var end = (new Date()).getTime();
console.log("Populate B+-tree elapsed time: " + (end - start));

start = (new Date()).getTime();
var obj = {};
for(var i=0; i<num; i++){
	obj["key"+i] = i+" - value";
}
end = (new Date()).getTime();
console.log("Populate object elapsed time: " + (end - start));

start = (new Date()).getTime();
var arr = [];
for(var i=0; i<num; i++){
	arr[i] = {"key": "key"+i, "value":(i+" - value")};
}
end = (new Date()).getTime();
console.log("Populate array elapsed time: " + (end - start));

// Search
start = (new Date()).getTime();
for(var i=0; i<searchCount;i++){
	var x = tree.get(key);
}
end = (new Date()).getTime();
console.log("Search B+-tree elapsed time: " + (end - start));

start = (new Date()).getTime();
for(var i=0; i<searchCount;i++){
	var x = obj[key];
}
end = (new Date()).getTime();
console.log("Search object elapsed time: " + (end - start));

start = (new Date()).getTime();
for(var i=0; i<searchCount;i++){
	for(var j=0; j<num; j++){
		if(arr[j].key == key) {
			var x = arr[i].value;
			break;
		}
	}
}

end = (new Date()).getTime();
console.log("Search array elapsed time: " + (end - start));	

// Range search
start = (new Date()).getTime();
var node = tree.getNode(key1);
var flag = true;
while(flag){
	for(var i=0; i<node.data.length;i++){
		if(key1 <= node.data[i].key && node.data[i].key <= key2){
			var x = node.data[i].value;
		}else{
			flag = false;
			break;
		}
	}
	node = node.nextNode;
}
end = (new Date()).getTime();
console.log("Range search B+-tree elapsed time: " + (end - start));

start = (new Date()).getTime();
for(var p in obj){
	if(key1 <= p && p <= key2){
		var x = obj[p];
	}
}
end = (new Date()).getTime();
console.log("Range search object elapsed time: " + (end - start));

start = (new Date()).getTime();
for(var i=0; i<arr.length; i++){
	if(key1 <= arr[i].key && arr[i].key <= key2) {
		var x = arr[i].data;
	}
}
end = (new Date()).getTime();
console.log("Range search array elapsed time: " + (end - start));

gistfile2.txt

Chrome v3.0.195.21 (V8 v1.2.14.17) (from: http://blog.conquex.com/?p=84)
------------------
Populate B+-tree elapsed time: 19585
Populate object elapsed time: 841
Populate array elapsed time: 510
Search B+-tree elapsed time: 7
Search object elapsed time: 0
Search array elapsed time: 9775
Range search B+-tree elapsed time: 0
Range search object elapsed time: 296
Range search array elapsed time: 586

node v0.1.100 (V8 v2.2.21)
-------------
Populate B+-tree elapsed time: 2090
Populate object elapsed time: 509
Populate array elapsed time: 211
Search B+-tree elapsed time: 1
Search object elapsed time: 0
Search array elapsed time: 3671
Range search B+-tree elapsed time: 0
Range search object elapsed time: 128
Range search array elapsed time: 13

node v0.1.101-02746ed (V8 v2.3.0)
---------------------
Populate B+-tree elapsed time: 2088
Populate object elapsed time: 497
Populate array elapsed time: 199
Search B+-tree elapsed time: 1
Search object elapsed time: 0
Search array elapsed time: 4138
Range search B+-tree elapsed time: 0
Range search object elapsed time: 129
Range search array elapsed time: 12