atlioddsson wrote:

> The subject pretty much sums up the question, "How to know when an
> index has become unbalanced?"
>

The short answer is that Firebird indexes basically don't go out
of balance. If you took a really bad data structures course in
the early dark ages of computer science, you may have seen indexes
that grew at the bottom and developed some branches that were
much longer than others. Professional indexes haven't worked
like that in the last 30 years. They grow from the bottom up
and all branches are always the same length. Until 1987 or so,
InterBase indexes would get unbalanced in a way if you stored
keys in ascending order (e.g. generator or timestamp based) and
deleted the old rows. All branches would be the same length,
but there would be large hollow areas of empty pages on the
left hand (low) side. But in 1987 or 1988, we added index
recompression, so that doesn't happen any more.

Until Firebird, building an index in ascending order (like
generator or timestamp keys) would create an index that was
balanced but only half full. When an index page is about to
overflow, Firebird splits it. Normally, half the rows go into
the new page and half remain in the old page so new entries
can be accommodated. But with an ascending key, new entries
are always bigger than existing entries, so empty space in
the old page is never used and the index is built half full.
Now Firebird notices that a split comes at the end of the
index, and puts only the newest entry in the new page, so
ascending indexes are built very nearly full.

However, random deletions and modification can lead to
partly filled indexes. The tool for identifying such
problems is gstat. It reports the fill level in index
pages - if it is below 70%, you should probably rebuild
the index unless the keys are very large - large keys
don't pack well into pages.


Regards,


Ann