A 50% improvement could be massively significant if processing a huge data-set on thousands of nodes and it is still taking days/weeks/more of wall-clock time. Given the choice between waiting longer, buying more computer power, or using a more complex algorithm, the best of those choices will depend a lot on the circumstances of the project. If it is a one-off then waiting or paying for power will likely win out. Of course in some circumstances paying for more power won't help: you can only get so much out of each node and for some processes factors like interconnect throughput & latency might eat into the ROI significantly as the number of nodes grow.
In some cases a 10% or less boost might be worth the extra complexity. And if the algorithm can be generalised and packages as a library, you aren't actually having to deal with that complexity each time the method is useful.
The thing is a self-balancing binary tree is so much faster than the alternatives for large chunks of data that you really have to use it. Here, I'm not so sure.
Anyway, thinking about this lead me to this discussion about fractal trees and LSM trees.
https://www.quora.com/What-are-the-major-differences-between...
Another question here is how will this play out if the high-performance DB is going to be moving to a GPU where cache levels and scans would be quite different.