Profiling and Optimizing the Javascript B+ Tree, Update 1

In the previous post, I neglected to demonstrate one important performance consideration, which is the type of key used to insert elements into the B+ tree. The baseline code was using string keys, as were all improved versions discussed. If instead numeric keys are used, the performance improves significantly. Insertion/removal/insertion times are now 2037ms/2161ms/2522ms, which is a further 40% improvement over the fastest previous version, and 70% faster than the baseline.

Additionally, there was a design flaw in the range retrieval method (as well as a bug introduced while optimizing the code, which has been fixed). The design flaw had significant impact on performance, resulting in range retrievals taking several seconds per invocation for ranges that returned 10k or 100k rows or more. Essentially, the use of Array.concat was the culprit, you can compare the current code to the baseline to see the changes. After fixing this, range retrieval is again very fast. Retrieval of over 500k elements in a range of 1M takes ~10ms.

Advertisements

2 Comments

  1. Nabil Stendardo

    Hi, I am interested in using your B+TREE code for a specific application (the application in question is collision detection for a game, accessing only relevant bounding boxes with range retrieval). This will however require to be able to have multiple elements per key, and being able to delete elements based on an identifier (or the value itself, but that will be hard for B+Tree). A simple solution (without changing your code) can be to have element keys as strings of type “sortable-key unique-id”, where sortable-key is the main key (real number) we want to sort with (all in the same format), and unique-id is just an identifier for the object. We just need to remember the key in question when deleting, and for range retrieval, we add a + (or whatever character with a pointcode higher than space) in order to start/end the range just after that key (just include the key as a string, with nothing trailing to be able to search just before it), thus being able to define inclusive/exclusive ranges. My guess is that replacing this by a list (and defining functions for them using lexicographical order) would even be slower than that 40% we gain by comparing strings.

    • Santanu

      If I understand the use case correctly, would it be possible to just index all your game elements using one B+ tree per dimension? To compute collisions would then be a matter of taking the result sets from each dimensions bounding boxes range query, and doing a set intersection operation on the result. Assuming your collision radius was relatively small, the input sets to this intersection operation would be fairly small as well, I think. There’s some code in the common.js file which you can use for set intersection. Hope it’s useful for you!

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

%d bloggers like this: