Hi,
I have a question about how the bitmap mechanism of Interbase (IB)
is working.
More exact :
I want to estimate worst case costs (in block accesses) for a
search-query for equality on a non-unique key value (f.e. a foreign
key) of a table in a certain database state.

As far as I know Interbase organizes indexed values in a variant of
the B*-Tree.
So IB has to run through the nodes of the B*-tree until reaching the
leaf that contains the specified search value.
(So I have to consider how many blocks need to be accessed for the
walk through the tree, if they a currently not in the cache.
Say the costs for the walk would be k.)

In the leaf, as the index is not unique, there might exist n different
reference entries, one for each row of the table that equals the
search value (by the way is there another indirection between the leaf
and the list of references ?).

The n matching rows may be distributed over m different blocks.

I read somewhere that IB will build up a bitmap from the
query-matching
table rows (more exact: their reference entries) before reading them
in, so that the sequence for physical access is optimized, i.e. they
will be read in in their physical (block-)order from the database
file.

So I draw the conclusion that none of the m blocks will be accessed
more than once, even if more than one matching row reside in one
block.

Then m would be the maximum block access for reading in
all rows (assuming that each row resides on max. one block)?

And (k+m) blocks would be the worst case cost for the whole query?

Can somebody tell me whether im right ?

Many thanks in advance,
Michael