I was in need for a solution to search a very large set of data in a javascript application. I thought of a b+ tree. Looking for a javascript implementation of it, google didn’t help much. So, I just gave up and decided to implement it myself. This is the result: not really a B+ tree but a variation that works better in this case. I call it a B# tree. It depends on the prototype framework but I’m planning on making some changes to it so it would work stand-alone.
root: null,
initialize: function(comparator) {
this.root = $A();
this.comparator = comparator || function(x) {
return x
};
},
add: function(text, object, node) {
var node = node || this.root;
node.objects = node.objects || $A();
if (node != this.root) {
node.objects.push(object);
}
if (text.length > 0) {
var chr = text.charCodeAt(0) - 32;
var next = node[chr] = chr == 0 ? this.root : node[chr] || $A();
this.add(text.substring(1), object, next);
}
},
search: function(text, objects) {
var node = this.root;
var result = null;
while (text.length > 0) {
var chr = text.charCodeAt(0) - 32;
text = text.substring(1);
if (char == 0) {
result = this.search(text, result);
break;
} else {
node = node[chr];
if (!node) {
return $A();
}
result = node.objects;
}
}
if (objects) {
if (node == this.root) {
return objects;
} else {
return this.intersect(result, objects);
}
} else {
if (node == this.root) {
return $A();
} else {
return result;
}
}
},
intersect: function(a, b) {
var i = 0;
var j = 0
var intersect = $A();
a = a.sortBy(this.comparator);
b = b.sortBy(this.comparator);
while (i < a.length && j < b.length) {
if (this.comparator(a[i]) == this.comparator(b[j])) {
intersect.push(a[i]);
i++;
j++;
} else if (this.comparator(a[i]) > this.comparator(b[j])) {
j++;
} else {
i++;
}
}
return intersect;
}
});
It contains a very efficient intersect method. To use it just do something like this:
bst.add("some string", "my object");
bst.add("some other string", "other object");
bst.add("last string", "last object");
bst.search("string"); // returns ["my object", "other object", "last object"]
bst.search("some string"); // returns ["my object", "other object"]
You can set any object as the second parameter to the BSharpTree#add method but then you might need to pass a comparator function to the BSharpTree constructor. Use it as you may see fit!
No related posts.