[Community] Designing new types of Rtree indexes

[Howard Butler]

On Jul 30, 2009, at 6:14 AM, Sean Gillies wrote:
>
> Let's separate the search index rtree was originally designed to be
> from this new storage bucket you're proposing. I think they'll have
> very different users. Separate classes, different (though related)
> interfaces. No unnecessary constraints on each other. I'm not opposed
> to their being in the same namespace, but different modules like
> rtree.index and rtree.storage would be good, IMO.
>

An index doesn't need to be exclusively data-storage or no-data- 
storage.  You can mix index entry insertion with some entries having  
data (pickles in our case) while others don't.  If you wanted to  
refactor the code and tests so these two are separate, I guess I don't  
have a problem with it, but from my perspective, they're conceptually  
the same.

>> What do you mean by reindexing?  I don't have bulk insertion done  
>> yet,
>> but the C API will work by using callbacks.  If there were a
>> straightforward and common tree-walking query that people need, this
>> could be implemented as well.
>
> Say I've bulk loaded, but then reindex items here and there over time.
> If I understand it, this eventually degrades the index. I'd like to be
> able to reindex everything with the same efficiency as a bulk load.
>

We should ask Marios, but I didn't think rtrees degrade.  Are you  
seeing problems?  Do you have any code that might demonstrate it?

What you are asking for is a query strategy that walks the entire tree  
and sequentially returns all of the items in it.  This is fairly  
straightforward to do (but kind of slow).


> I'm not sure how you want to use callbacks. Wouldn't you just pass an
> iterator to the bulk loading function?

Bulk loading operates by having the libspatialindex C++ code call in  
to your application code to fetch items.  libspatialindex presumes  
bulk loading happens with a class that supports an iterator- 
like .next() method, but we can't do such a thing from C.  Callback- 
style code will allow us to have libspatialindex call into Python to  
fetch items, with the assumption that it must be an iterable in a  
certain form (the formatting of the iterator would be controlled by  
the ctypes code).