Re: Optomized Range Searching....

On 15 Aug 2000 14:35:14 -0500, Art Pollard <pollarda_at_lextek.com> wrote:
>
>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.

As far as I know this is true in most types of B-tree anyway, such as Knuth's version or in VSAM. Here the pages of the trees are divided in something like a sequence set (the bottom layer of the tree) and the index set (the rest of the tree). The sequence set is a linked list of pages that contains pointers to the actual records clustered on the indexed attributes. (I think this is what you would call buckets.) The index set is the actual tree and contains no pointers to records but only to other pages in the index set and pages in the sequence set.

Kind regards,

• Jan Hidders