tiling shape files, or shptree

[Tim Tsai]

On Wed, Apr 27, 2005 at 09:55:47AM -0700, Schuyler Erle wrote:
> * On 27-Apr-2005 at  2:44AM PDT, Tim Tsai said:
> >   Is there a significant performance difference between using
> > shptree/tileindex and shp2tile/tile2index?  Since shptree already uses
> > quadtrees, I imagine the main performance difference is to minimize
> > seeks on the data?
>
> My experience is that MapServer doesn't scale well with large
> shapefiles, even when quadtrees are built. I would like to know why
> that is, personally, but I can attest that shp2tile + tileindex scales
> much better with large datasets.

  Thanks.  I am curious about that too.  So far, I have not run into
performance problems with shptree alone but I might try shp2tile and
see if there's a noticeable difference.

  My guess would be similar to the difference between a pure b-tree
and a balanced b-tree or even a b+-tree.  Shp2tile keeps geographically
related items together so you take advantage of the cluster effect and
minimize the average seek times.  A balanced tree will give you much
more deterministic response where an unbalanced tree could potentially
have very bad performance in degenerate cases.

  Thanks,

  Tim