Re: Optomized Range Searching....

Jan Hidders <hidders_at_wsinis12.win.tue.nl> wrote in message news:8nb9sj$8a2$1_at_news.tue.nl...
> On 14 Aug 2000 23:19:14 -0500, Art Pollard <pollarda_at_lextek.com> wrote:
> >
> >I am wondering if there are any papers on ways
> >to optomize range searching. (Specifically numerical
> >range searching.) For example, if a database user
> >requested all books under $100, it could make for
> >a lot of traversing in the BTree or other index when
> >you consider all decimal places that are possible.
>
> Maybe I am misunderstanding you, but usually you just look up the page
 that
> contains the upperbound and the page that contains the lowerbound. The
 pages
> "in between" will then contain records that fall within the range. So, you
> just have to traverse the tree two times.

That is true. However, it is possible that the span between the low bound and the high bound may be quite large. Thus for example, if someone queried a DB for (as a bad example) pots in Mesopotamia between the years of 100A.D. - 500 A.D. This would catch all instances of all dates for 500 years which would have to be OR'ed together. This, I would presume, could be sped up by having buckets which contained the record IDs for the various dates by century already colated together. Thus you would have 5 buckets to look at and process instead of potentially hundreds.

I am sure there are other optomizations out there for this sort of thing but when it comes to numeric range processing you could run into some real efficiency problems if the range between your low and high contain an extremely large number of enteries.

-Art Received on Tue Aug 15 2000 - 21:35:14 CEST