Subject Re: Re[2]: [Firebird-Architect] Re: Index structures
Author Ann W. Harrison

If I may try to expand on what Jim said slightly. Firebird
indexes are always considered to be inexact. For one thing,
numeric indexes are kept in floating point, so the matching
must include the two edges - slightly higher and slightly
lower than the desired value - to account for the translation
to fixed point.

Every index contains references to new records that are not
yet committed, committed records, and back versions of records.
A single record may appear in the index several times if the
key value has been modified. Even a unique index can have
duplicate values, as long as no transaction can see more than
one of the values.

All the index entries point to the record's "primary version" -
the most recently created version. An old transaction looking
for an old value finds that value in the index, reads the primary
record, recognizes that the version is too new for it, and
follows the back chain until it finds the appropriate version.
That version may or may not have the value that the transaction
requested. If not, the record is rejected.

If my transaction modifies a bunch of records setting the key
value from "cat" to "dog", the old "cat" entries stay in the
index. Concurrent transactions read the "cat" index entry.
The first record version the see has the value "dog", but that
value is in a record version created by an uncommitted transaction,
so the concurrent transactions look at the back version and find
the cat they expected.

>So, AFAIU, this transaction will make the engine use the index for all the
>data (non-commited records included) and after boolean filter this up
>(removing non-commited records).

The filter actually happens a bit earlier as it is part of the
low level code that matches transactions with the appropriate
record version.

>It will be hard to keep a well balanced tree in situations when records are
>post, and most of the time roll-backed.

Actually not. B*trees are built from the bottom up, so they don't
get the "leggy" look of the B trees in computer science texts.
Each node - bottom level on up - can be recompressed individually.
Furthermore, if a node goes below half full, it asks its immediate
neighbor if that neighbor is below half full, and if so the two

>I will wait if Ann can point me out some doc about this, but your post was
>very usefull.

Artur, you have got me in terrible trouble with my husband! He
invented all this - I just explain it.