On Wed, May 09, 2007 at 14:45:33 +0000, [EMAIL PROTECTED] wrote:
> You need an R-Tree index to do something like this. The
> public-domain version of SQLite only supports B-Tree indices.
> So, no, indices are not going to help you here.
Alternatively to R-tree index, you may simply partition the space into
NxM cells, with, say, left and bottom border belonging to the cell
itself (while right and upper borders belonging to the right and upper
cells as their left and bottom borders respectively), and enumerate
these cells row-by-row like
10|11|12|13|14
---+--+--+--+---
5| 6| 7| 8| 9
---+--+--+--+---
0| 1| 2| 3| 4
This way every point belongs to exactly one cell. Then you create
CREATE TABLE map (
x INTEGER,
y INTEGER,
name TEXT,
cell_no INTEGER
);
CREATE INDEX map_cell_no ON map (cell_no);
When inserting a point, you compute its cell_no (something like
cell_no(x, y) = y / cell_height * cells_in_row + x / cell_width;
). When doing a region query, you compute a set of cell numbers that
intersect with a query window, accumulate them in a (memory) table
selected_cells, and then do
SELECT map.*
FROM mem.selected_cells sc CROSS JOIN map ON sc.cell_no = map.cell_no;
Better yet to compute two sets: those cells that reside completely
within the query window, and those that intersect window border.
Points from the latter cells should be filtered further.
Reasonable cell dimensions based on typical query window size and
points distribution will give quite reasonable performance.
--
Tomash Brechko
-----------------------------------------------------------------------------
To unsubscribe, send email to [EMAIL PROTECTED]
-----------------------------------------------------------------------------
