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.
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