Re: [Boost-users] [Geometry] Packing algorithm for r-tree?

Subject: Re: [Boost-users] [Geometry] Packing algorithm for r-tree?
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-10-27 07:16:51

Jeremy Murphy wrote:
> And, on a tangent, how does the packing algorithm cope with having 
> values removed from the index? Does it readjust the packing or does 
> the index become suboptimal?

The packing algorithm is only used during creation of the r-tree, 
elements are processed top-down.
During insertion or removal of an element, splitting algorithm is used, 
elements are processed bottom-up.

So yes, in general case (insert/remove) the index becomes "suboptimal". 
Though removal shouldn't affect the tree that much, since only the nodes 
at the bottom of the tree would be split on underflow. During the 
insertion all nodes on the path from a leaf to the root would have to be 
split on overflow, and the probability of such is high in a rtree 
containing packed elements/nodes.

Regards,
Adam