Subject Re: Index structures
Author Alexander Klenin
>> > >It is not possible with the current index-structure.
>> > >So my idea is for unique-index-key-lengths <= 8 (or
>>user can force to use
>> > >them) to store the full key in the index. This way we
>>can do faster

>The problem I have with your analysis is that while your
>algorithm may be faster
>to find a given node on a page, your index keys are significantly larger
>than the existing scheme, leading to a less dense index and
>increased page reads.

Well, I am NOT familiar with Firebird internals, but out
of general considerations, two solutions come to mind:

1) create "partially compressed" indexes along the lines
of MPEG algorithm, where every Nth index value is stored
completely, and values in between are compressed. The
search should find the nearest uncompressed value, then
scan next N values in linear time. By adjusting N one can
balance search performance vs memory increase.

2) create additional separate tree-like data structure for
every page, again covering not all values but down to
blocks of some predetermined size. Not sure if this scheme
has any advantages, just mentioned it for the sake of
completeness ;)

Professional hosting for everyone -