B# tree and Array intersection in javascript

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!

2 Responses

  1. Graham
    Graham May 3, 2013 at 7:32 pm |

    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.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.