other indexes

hash indexes

The multi-level index is the most commonly used index type. Several additional index types are used less often but supported by many databases:

• Hash index

• Bitmap index

• Logical index

• Function index

In ahash index, index entries are assigned to buckets. Abucketis a block or group of blocks containing index entries. Initially, each bucket has one block. As an index grows, some buckets eventually fill up, and additional blocks are allocated and linked to the initial block.

The bucket containing each index entry is determined by a hash function, which computes a bucket number from the value of the indexed column. To locate a row containing a column value, the database:

1. Applies the hash function to the column value to compute a bucket number.

2. Reads the index blocks for the bucket number.

3. Finds the index entry for the column value and reads the table block pointer.

4. Reads the table block containing the row.

A hash index is similar to a hash table, described in another section. However, a hash index storesindex entriesin each bucket, while a hash table storestable rowsin each bucket.

bitmap indexes

A bitmap index is a grid of bits:

• Each index row corresponds to a unique table row. If the table's primary key is an integer, the index row number might be the primary key value. Alternatively, the index row number might be an internal table row number, maintained by the database.

• Each index column corresponds to a distinct table value. Ex: If the index is on AirportCode, each index column corresponds to a different three-letter airport code. The mapping of index column numbers to table values is computed with a function or stored in an internal 'lookup' table.

Bitmap indexes contain ones and zeros. 'One' indicates that the table row corresponding to the index row number contains the table value corresponding to the index column number. 'Zero' indicates the row does not contain the value.

To locate rows containing a table value, the database:

1. Determines the index column corresponding to the table value.

2. Reads the index column and finds index rows that are set to 'one'.

3. Determines table rows corresponding to the index rows.

4. Determines pointers to blocks containing the table rows.

5. Reads the blocks containing the table rows.

An efficient bitmap index has two characteristics:

• The database can quickly determine the block containing a table row from the index row number (steps 3 and 4). Ex: The index row number is the hash key for a hash table. The block is determined by applying the hash function to the row number. Ex: The index row number is the table primary key. The block is determined with a primary index.

• The indexed column contains relatively few distinct values, typically tens or hundreds. If the indexed column contains thousands of distinct values, the bitmap index is large and inefficient.

Bitmap indexes with the above characteristics enable fast reads. Ex: A table with 10 million rows has a bitmap index on a column with 100 distinct values. The index contains 125 million bytes (10 million rows × 100 column values × 1 bit per index entry / 8 bits per byte) and can easily be retained in memory.

logical indexes

A single- or multi-level index normally contains pointers to table blocks and is called a physical index.

A logical index is a single- or multi-level index in which pointers to table blocks are replaced with primary key values. Logical indexes are always secondary indexes and require a separate primary index on the same table. To locate a row containing a column value, the database:

1. Looks up the column value in the logical index to find the primary key value.

2. Looks up the primary key value in the primary index to find the table block pointer.

3. Reads the table block containing the row.

Logical indexes change only when primary key values are updated, which occurs infrequently. Physical indexes change whenever a row moves to a new block, which occurs in several ways:

• A row is inserted into a full block. To create space for the new row, the block splits and some rows move to a new block.

• The sort column is updated. When the sort column is updated, the row may move to a new block to maintain sort order.

• The table is reorganized. Occasionally, a database administrator may physically reorganize a table to recover deleted space or order blocks contiguously on magnetic disk.

If a table has several indexes, the time required to update physical indexes is significant, and logical indexes are more efficient.

On read queries, a logical index requires an additional read of the primary index and is slower than a physical index. However, the primary index is often retained in memory, mitigating the cost of the additional read.

functional indexes

In some cases, values specified in a WHERE clause may be in a different format or units than values stored in the column. Ex:

• The WHERE clause specifies values in upper case, but the column contains mixed upper and lower case characters.

• The WHERE clause specifies values as percentages, from 0 to 100, but the column contains values from 0 to 1.

In the above examples, index entries do not match values in the WHERE clause, so the database cannot use the index to execute the query.

To address this problem, some databases support function indexes. In a function index, the database designer specifies a function on the column value. Index entries contain the result of the function applied to column values, rather than the column values.

Ex: Column values are stored as decimal numbers between 0 and 1, but users specify percentages as integers between 0 and 100 in queries. The database designer specifies a function index that multiplies column values by 100 and converts the result to an integer. The index contains integers between 0 and 100, so the database can use the function index to process queries.

In principle, functions can be used with any index type, including single-level, multi-level, hash, bitmap, and logical indexes. In practice, support varies by database.