Different Types of Indexes and Their Uses

An index is, typically, a tree structure that allows a query to directly access a row in a table. Indexes can be classified based on their logical design or on the physical implementation.

Logical Index Classifications

The logical classification groups indexes together based on an application perspective of the index. The following list describes the various logical classification indexes:

• Single column Has only one column in the index key; for example, claim_number might be the key for a claim table.

• Concatenated Also known as composite indexes, these are indexes created on multiple columns in a table. The columns that are concatenated do not need to be in the same order as the columns appear in the table, nor do they need to be adjacent in the table. The maximum number of columns permitted to be in a composite key is considered to be 32; however, the combined size of all the columns in the index cannot exceed roughly one-third of the size of the data block.

• Unique index Guarantees that no two rows of a table have duplicate values in the column or columns that define the index. Therefore, an index key in a unique index can point to one and only one row in the table.

• Nonunique index In this index, a single key can point to one or to multiple rows associated with it.

• Function based Created whenever you are using functions or expressions that involve one or more than one column in a table that is being indexed. Function-based indexes precompute the values of the function or expression on which they are based and store that value in the index. They can be created either as a B-tree index or a bitmap index.

  Function-based indexes allow you to create more powerful sorts by allowing you to perform sorts that are not case sensitive by creating indexes with the UPPER and LOWER functions along with the descending order sorts with the DESC keyword. You can even create linguistic sort based indexes with the NLSSORT function. You can precompute the values of computationally intensive functions and store the value in the index for expressions used often on a given column or columns. In this way, you can access the index to access the value and not force the recomputation of the value, greatly improving query execution performance.

  The following initialization parameters need to be defined if you are going to create function-based indexes:

  • QUERY_REWRITE_INTEGRITY needs to be set to trUSTED.

  • QUERY_REWRITE_ENABLED needs to be set to trUE.

  • COMPATIBLE needs to be set to at least 8.1.0.0.0 or greater.

• Domain Application-specific indexes (for example, Spatial) that are created, managed, and accessed by routines supplied by an index type. It is known as a domain index because it indexes data in application-specific domains. As yet, only single-column domain indexes are supported and can be built on columns that have scalar, object, or LOB data types.

Physical Index Classifications

The physical classification of an index is based on the way the indexes are stored. The next few sections cover physical index classifications in more detail.

Partitioned

Partitioned indexes are used for large tables as a means to store the index entries corresponding to an index in several segments. Partitioning of indexes allows an index to be spread across several different tablespaces, thereby decreasing contention for index lookup and increasing manageability. An index partition can be created on a one-to-one basis with a table partition.

Nonpartitioned

Nonpartitioned indexes are the norm and are created in a single tablespace. They are covered in the remainder of this chapter.

B-Tree

Although the vast majority of indexes use a B-tree structure, the term B-tree (short for binary tree) is typically associated with indexes that store a list of ROWIDs for each key.

The top of the B-tree index is the root, which contains entries that point to the next level in the index. One level farther down are branch blocks that in turn point to blocks at the next level in the index. This continues until the lowest level is reached, where there are leaf nodes, each containing index entries that point to rows in the table. Leaf blocks are doubly linked to facilitate scanning the index in an ascending or descending fashion. Ascending is the typical means of storing and accessing.

Figure 13.1 shows, graphically, what a B-tree structure would look like. Although this is a simple example, you can see how each leaf is doubly linked in order, so you can traverse the tree in obverse and inverse order.

Figure 13.1. A typical B-tree structure.

Leaves contain the index entries that have the following components:

• An entry header that stores the number of columns and locking information for the index.

• Key column length value pairs. These pairs define the size of the column in the key followed by the value for that column. The number of pairs equates to the number of columns in the index.

• ROWID of a row that contains the key values for the index.

• Key values in a B-tree index are repeated if there are multiple rows with the same key value.

• There is no index entry for rows that have all key columns that are NULL; therefore, WHERE clauses that specify NULL or NOT NULL will always result in a full table scan.

• Restricted ROWID is used to point to the rows of the table. This is possible because all the rows belong to the same segment in the same tablespace.

Oracle maintains all the indexes whenever DML operations are carried out on the table.

Whenever there is an insertion of an index due to an insertion of a new index value in the table, the index entry is inserted into the appropriate block.

If deletions occur in the table that result in a deletion in the index, the index entry is logically deleted. The space consumed by the index entry will not be available for reuse until all the entries in the given block have been deleted.

Updates that occur to key columns result in a logical delete and a physical insert to the index. PCTFREE for dictionary managed tablespaces has no effect on the index except at the time of creation. New entries may be added to index blocks even if the amount of space remaining is less than that specified by PCTFREE.

B-tree indexes are highly suited for high cardinality columns. Updates on B-tree indexes are relatively inexpensive; however, they are somewhat inefficient for queries that use the OR operator in the predicate. B-tree indexes are useful for OLTP environments.

Bitmap

It is often the case that bitmap indexes are more advantageous than B-tree indexes, depending on the situation.

If a table has millions of rows but the key columns have a low cardinality (very few distinct values in relation to the number of rows), bitmap indexes may be preferable to B-tree indexes. For example, values such as gender, marital status, or region of the country may all be good candidates for bitmap indexes.

Examples of times when bitmap indexes are appropriate are as follows:

• Whenever queries often use a certain combination of WHERE conditions involving the OR operator, bitmap indexes may be a good idea.

• If there is read-only or low update activity on key columns, bitmap indexes are often a wise choice.

• Unique indexes are not good candidates because cardinality is one-to-one.

The structure of a bitmap index is organized in a B-tree fashion; however, the leaf nodes each store a bitmap for each key value instead of a listing of ROWIDs. Each bit in the bitmap corresponds to one possible ROWID, and if the bit corresponding to the ROWID is set, the row with that ROWID contains the key value.

Each leaf node contains an entry header that contains the number of columns and lock information. It also contains key values consisting of length and value pairs for each key column; a start ROWID, which contains a file number, a block number, and a row number; and an end ROWID with similar information. Finally, it contains a bitmap segment consisting of a string of bits with the corresponding bit being set whenever the corresponding row contains a key value for that bit and unset when the row does not contain a key value. Oracle has patented the compression algorithm used to store these bitmaps.

The bitmap's B-tree is used to locate the leaf nodes that contain bitmap segments for a given value of the key. The start ROWID and the bitmap segments are used together to locate the rows that contain the given key value. Whenever changes are made to the key columns of the table, the associated bitmaps must be altered correspondingly. These alterations result in the relevant bitmap segments being locked. These locks are acquired on the entire bitmap segment, and that means that any row that happens to be covered by any segment in the bitmap cannot be updated by any other transactions until the locking transaction ends.

Bitmap indexes are useful for low cardinality columns. Updates to key columns are expensive; however, bitmap indexes are efficient for queries that use the OR operator in the predicate. Oracle can use two bitmap segments to facilitate a bitwise Boolean comparison and get a resulting bitmap; this means that Oracle can use bitmaps efficiently in queries that use Boolean in the predicate. They are useful for data warehouse environments because the update of the bitmap occurs so infrequently.

Now that we have covered the kinds of indexes, it is time to look at what is involved in creating them.