>What do you mean by dense indexes? How do they solve the problem?
>
>Jim Starkey
>

I used the term dense, to contrast it from sparse. Like dense is the antonym
of sparse, right?

(Also, I was thinking in terms of sparse index - where one pointer to one
record is kept for a key value, and duplicates are traversed in a linked
list fashion relative to that first record, versus a dense index where
duplicates do not have to be traversed in a linked list fashion, because
there is a pointer to (almost) every record / key combination (thus dense)
but is much larger than sparse index in size. Not that this sparse/dense is
applicable to this discussion. But it's just to explain the use of the word
dense.)

But the main thing is,
1. Is it not the case that the present Indexing system (sparse) has a worst
case problem with multiple duplicate keys? I'm thinking in terms of
algorithm analysis, where some algorithms have a very big gap between its
best case vis-a-vis its worst case. And its like this with the IB Index
algorithm - very good with its best case (unique keys with no selectivity
problems), and very poor with its worst case (keys with many many duplicate
values - which can occur in the real world with implementing referential
integrity constraints with foreign keys, where the referenced table size is
very small compared to the 'referencing' table). Example: implementing a
referential integrity constraint between a maillist table with millions of
records to a zipcode table.

2. Would it be possible to conceive of an alternative index system, which
we'll label as dense - to contrast it with sparse, which will have a pretty
constant performance (a very small gap between its best case and worst case
performance), which developers can all on, if they know that their table
keys will have selectivity problems. (Honestly, I'm thinking of XBase index
performance where seek performance is pretty constant).

One consideration is, IB is quite an old database system. (There is no
negative element in the label old, and I love IB). The hardware
considerations which existed then, like rattling slow disk head movements
and small hard disk size, might not be such a big deal anymore at this
stage, given the advances in hard disk technologies. So, the index
algorithms which might not be applicable at that time might be applicable
now.

So, the main question / vision is:

Is it possible for IB to have another index system, in addition to the
present one, so that indexes won't have selectivity issues and would be more
forgiving to the poor database designers who might have no idea at all what
'selectivity' means?

Joseph Alba
jalba@...