Re: Date range searches

From: Mikito Harakiri <mikharakiri_nospaum_at_yahoo.com>
Date: 5 Jun 2006 15:17:02 -0700
Message-ID: <1149545821.950710.13120_at_i40g2000cwc.googlegroups.com>


eselk_at_surfbest.net wrote:
> I have a record with a start date and an end date field. If I want to
> find all records which are in the year 2006, what is the best way to
> index this data?
>
> I'm not using a client/server database engine, it is a custom flat-file
> database.
>
> The SQL for the query would look something like this (if this was an
> SQL database):
>
> START_DATE <= #12/31/2006# AND END_DATE >= #1/1/2006#
>
> Lets say the index is by start date. If every record in the database
> starts before 12/31/2006, then my search had to scan the entire index,
> even if all of the records end dates were before 1/1/2006. So my
> search takes a long time, even though it doesn't find anything.
>
> If I reverse the index and make it by end date. If every record ends
> after 1/1/2006, then my search had to scan the entire index, even if
> all of the records start dates were after 12/31/2006. So I have the
> same problem, just reversed.
>
> I guess if I had an index that would contain multiple keys per record,
> one key for each day the record lands on, then the search would be
> fast. However, it would take a long time to build and maintain this
> index, because it could have 1000s of keys for one record (update 1000
> keys just to save a record!).
>
> My indexes are B-tree format, kind of (with some slight variations).
> Is there another index format that works better. If so, could you help
> me understand why? I found one poster saying an R-tree might work
> better, and I read some info about an R-tree, but I can't see how that
> would work in my situation.

Your query is spacial. It is essentially the same as

X > ax and Y > ay

Gemetrically, these constraints describe a cone on X,Y-plane.

R-Tree is an incremental evaluation structure designed for spacial queries. Received on Tue Jun 06 2006 - 00:17:02 CEST

Original text of this message