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.
- Posted in: Uncategorized