Bulk-loading results in invalid trees
db7 opened this issue · 1 comments
db7 commented
Often, bulk-loading a tree results in trees with more children than MaxChildren
and more levels than returned by Rtree.Depth()
. The searches seem to be unaffected, but that may cause issues when inserting or deleting entries after bulk load.
There are several issues in the OMT bulk-load implementation that cause the invalid trees:
- the calculated height by the algorithm does not match the depth reached during recursion
- the splitting of vertical slices results in not fully packed leaves
- the same problem results in non-leaf nodes containing more children than
MaxChildren
We found this problem while trying to reduce the allocations in the KNN search, see issue #24.
dhconnelly commented
Assuming your pull request fixed this. Thanks for the contribution!