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.
var BSharpTree = Class.create( { 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:
var bst = new BSharpTree(); 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!
I’m not sure what the difference is between a B+Tree and your B#Tree, but if you want a pure JavaScript version with deletion, skipping etc try out my one at:
http://goneill.co.nz/btree.php
I think you’ll find it performs much faster than a framework based one.
Thanks a lot for the link. I actually wrote this a long time ago for a very specific set of data and worked better than any other implementation I could find at that time. This tree was optimized for partial string search specifically, using lots of memory. Your implementation seems rather nice, I’ll sure give it a try.