https://bugs.openldap.org/show_bug.cgi?id=9099

--- Comment #2 from Markus markus@objectbox.io ---

Right, rebalancing would become quite a pain.

Regarding re-balancing, maybe a pragmatic solution could be two phase range-delete:

1) First, delete only those pages in the given range that will not trigger re-balancing. 2) Second, delete the remaining nodes in the range as is (causing re-balancing).

Another simplification might be to limit the page deletions to leaf pages. I'd guess the speed-up would already be quite significant.

If you are interested, I could give it a shot. Just let me know. Without more efficient range-deletes, we may have to look into workarounds. Thus, I'd be happy to invest some time to solve that at the "core".