The Advancing Art of Indexing - High-Performance Web Databases: Design, Development, and Deployment - page 639

The native indexes in relational data bases such as Or-
acle, Informix, Sybase, and other relational data base management systems
(RDBMSs) use a B-tree structure that allows partial key retrievals, sorted
retrievals, and concatenation of columns. B-tree indexing has been effec-
tively used for years but has several drawbacks, including:

B-Tree Indexing.

• Limited to single attribute . There is no efficient way to combine multiple

criteria to narrow a search through thousands and millions of records.

• Limited to support of full key values in left-to-right sequence . Users must

enter the search criteria in the same order the data was entered, in or-
der to attain the most efficient search.

• Limited to exact match of criteria to data stored . Again, users must be

aware of how the data was entered.

Several RDBMSs also have a “hashed” key capability, which is fast but not
flexible. Hashed indexes require a full key lookup and a perfect match, in-
cluding upper or lower case letters, spaces, and punctuation.

Though indexing has been around for as long as the computer file, there
have been great advances in indexing technology. Specialized indexes pro-
vide new and improved solutions to the high-performance needs of deci-
sion support data access. Advanced indexing can deliver true interactive
DSS query capabilities to the knowledge worker.

One advanced indexing technology is bit-map index-
ing. Bit-map indexing represents each unique value in the underlying file
structure as an array of bits, setting the bits ON or OFF. This indexing struc-
ture can provide high-speed index-only processing.

Bit-Map Indexing.

Bit-map indexing has been targeted to be most effective for low cardinal-
ity data (i.e., data with few unique values, such as male/female, yes/no, or
coded data). Its weakness, however, is in its limitation to high cardinality
data (i.e., data with many varying values, such as text data, name fields,
and descriptive fields). The more varying the data, the more bit-maps that
must be created and maintained.

There is a focus on positioning bit-map indexing as the indexing solution
for the data warehouse. This approach often assumes that the data is static
(i.e., lower index maintenance) and that the underlying data can be off-
loaded (i.e., lower online disk utilization).

Another advanced indexing technology is inverted
indexing. Inverted indexes store pointers to the data base as data, and the
data from the data base as keys. Inverted file indexing maintains indexes to
all values contained in an indexed field.

Inverted File Indexing.