Subject RE: [IB-Architect] Index Selectivity Question (RFC)
Author Jim Starkey
At 09:18 PM 7/20/01 +0400, Dmitry Yemanov wrote:
>I cannot be considered as an engine guru, but I was always thinking that in
>InterBase the internal index implementation somehow combines elements from
>both b-tree and bitmap technologies. Am I wrong?

I don't think there is any connection with JRD bitmap index handling
and Oracle bitmap indexes.

A JRD index node contains a single record number. On retrieval,
the index is scanned in a single operation setting bits in a
bitmap reflecting index node selected. Retrieval is then driven
by the bitmap order.

My understand of an Oracle bitmap index is that an index node
contains of bitmaps of records containing that value. I don't
know whether Oracle uses those record numbers to create a single
bitmap to drive the retrieval.

In JRD, an duplicate index entry always takes 6 bytes (one byte
of prefix, one byte of length, and 4 bytes of record number).
In Oracle bitmaped indexes, the space consumed by a record is
essentially unknowable -- dependent on the number and density
of records represented.

The Oracle scheme has some advantages over the JRD scheme under
some conditions, but there are alternatives available to Firebird
that are better than either the current JRD and Oracle schemes.
Propogating the record number (appended to key) into the upper
levels of the index (which Ann has been beating on me to do in
Netfrastructure) beats both schemes.

Jim Starkey