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.
- Posted in: Uncategorized
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
Thanks. have you experimented with support on IE? From what I understand there should be no problem running this code on that platform?
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.
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.