A Javascript B+ Tree

This post describes a Javascript implementation of the B+ tree data structure.  If you’re just here for the code, and don’t want to read any of this jibber jabber, here’s the github link: https://github.com/santanubasu/BPlusJS.

Ok, so now a bit more about this.  First off, here’s a link to a page on wikipedia describing a B+ tree.  Speaking with a complete lack of rigor, the following are key features of this data structure:

  • Lookup by key is very fast
  • Retrieval of key ranges is almost as fast
  • Insertion and deletion aren’t too slow

This data structure is pretty common in computer science.  The filesystem on your OS probably uses some variation of this.  If you’re willing to trade off some space for some time, and you’ll be doing retrievals more often than insertions, a B+ tree can be useful.

So why do something like this in Javascript?  The idea came to mind because I was thinking about what it would take to build a simple client side in memory queryable database in Javascript.  The practicality or usefulness of this can be left to another blog post, but one of the items that underlies such a database is a B+ tree.  It can form the basis of database indices, and is one way some actual filesystem and databases organize their data.

I’ve written a rough cut at the B+ tree structure itself.  It does insertion, deletion, key lookup, and range retrieval.  For the purpose of visualizing the tree structure, there is a toString function in the top level BTree class that will pretty print all current data, illustrating the left/right child fan out.  The demo.html page shows some examples of how to use the tree class.  Random node insertion and deletion showing a return to an empty structure, as well as some rough performance metrics are printed to console.

On my laptop (quad core i7, 2.2 GHz, 8 GB of memory), using Chromium, the performance is decent (for a JS app anyways).  Insertion of 500,000 random objects takes about 10 seconds, deletion of the same takes about 5 seconds.  Retrieval of an object by it’s key or a range of 1000 contiguous objects is almost instantaneous.  I’ll post some performance data in a more structured format in a future post.

About these ads

6 Comments

  1. Martin

    I’ve looked at your B+Tree implementation and it looks nice, but I would like to run it. The github code tries to load something called “../CommonJavascript/common.js” which is not in the repository.

    • Hi Martin, common.js is is a bit of code that is used by different projects of mine, you can find the file in this project: https://github.com/santanubasu/CommonJavascript

      • Martin

        Thanks. have you experimented with support on IE? From what I understand there should be no problem running this code on that platform?

  2. max

    Thanks for he code, but after testing i had found that range retrieval sometimes work incorrectly, returning less items or no at all than was added in the range.

    • Hi Max, can you post or send me a test case to see this behaviour? I will take a look when I get a chance and find the bug.

      • Max

        Hi Santanu, I can’t do it because i tried the code with my application, to cache details records for main records. I just checked count of the retrieved records with btree range and my previous working method. Mostly there were equal count, but in some cases the range method returned less or no records from the supplied interval.
        I think it can be tested checking range retrieval of records with known counts of records. Seems the range method fails in some marginal cases.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: