Lesson 3	Types of indexes
Objective	Understand the types of indexes supported by Oracle.

Oracle Index Types

All indexes serve the same purpose which is to speed the execution of SQL statements. You can declare an index to be either unique, which means that all values in the index occur only once, or non-unique, which allows repeating values. The UNIQUE and PRIMARY KEY constraints use unique indexes to implement the constraint. Oracle supports two basic types of index structures which are the B*-tree index and the bitmapped index.

B*-tree Index

The B*-tree index organizes data in an inverted tree structure. Each level in the structure is referred to as a node, and the bottom level in the B*-tree structure is called the leaf block.
Starting at the top node, each block in the node contains a series of comparison values. Depending on where the value for an entry in the index falls in comparison to the values in the node, a user query travels to another node in the next level of the tree. This type of navigation is shown in the MouseOver below.

Using a Different Index Type

There are several index types available, and each index has benefits for certain situations. The following list gives performance ideas associated with each index type.

B-Tree Indexes: These are the standard index type, and they are excellent for primary key and highly-selective indexes. Used as concatenated indexes, B-tree indexes can be used to retrieve data sorted by the index columns.
Bitmap Indexes: These are suitable for low cardinality data. Through compression techniques, they can generate a large number of rowids with minimal I/O.Combining bitmap indexes on non-selective columns allows efficient AND and OR operations with a great number of rowids with minimal I/O. Bitmap indexes are particularly efficient in queries with COUNT(), because the query can be satisfied within the index.
Function-based Indexes: These indexes allow access through a B-tree on a value derived from a function on the base data. Function-based indexes have some limitations with regards to the use of nulls, and they require that you have the query optimizer enabled. Function-based indexes are particularly useful when querying on composite columns to produce a derived result or to overcome limitations in the way data is stored in the database. An example of this is querying for line items in an order exceeding a certain value derived from (sales price - discount) x quantity, where these were columns in the table. Another example is to apply the UPPER function to the data to allow case-insensitive searches.
Partitioned Indexes: Partitioning a global index allows partition pruning to take place within an index access, which results in reduced I/Os. By definition of good range or list partitioning, fast index scans of the correct index partitions can result in very fast query times.
Reverse Key Indexes: These are designed to eliminate index hot spots on insert applications. These indexes are excellent for insert performance, but they are limited in that they cannot be used for index range scans.

B*-tree index

Diagram that shows a hierarchy of names displayed in a b-tree index.

Top node: The topmost node provides an entry point. If the desired value is less than “Jones”, the retrieval proceeds to the left. If the desired value is greater than “Jones”, the retrieval proceeds to the right.
Middle nodes: Each node contains comparison values that direct the retrieval to another level of nodes or to the leaf blocks.
Leaf blocks: The leaf blocks contain the actual index values and the ROWIDs for the associated nodes. Each leaf block only contains a few values.
Expanded leaf block: The actual data in the leaf block consists of the value for the index and the ROWID of the row of the data table that contains it.

B*-tree index Structure

The B*-tree index structure has several advantages:

The branching structure dramatically reduces the amount of I/O to get to a particular block.
Because all the index entries are located in the leaf blocks, and all leaf blocks are the same number of levels below the starting node, retrieval for all rows takes the same amount of overhead, regardless of where the entry falls in the table.

Bitmapped index

A bitmapped index is organized by index values, and each bit in the bitmap points back to a particular ROWID. If the bit has a value of 1, the corresponding row contains that value, as shown in the MouseOver below.

Bitmap Values Green — Each value contains a series of bits, each of which point to a particular row.

If a bit is set to 1, it means that the associated row contains that value.

The bit is associated with the ROWID of a row

Each value contains a series of bits, each of which point to a particular row

Bitmap Indexes on Index-Organized Tables

Bitmap indexes are best suited for low-cardinality columns^[1], where the number of distinct values is relatively small compared to the total number of rows in the table. This makes them ideal for columns with a limited set of values, such as gender or employment status.
A Bitmap index uses a bitmap to represent each distinct value in the indexed column. Each bitmap consists of a string of bits, where each bit corresponds to a row in the table. A set bit indicates the presence of the indexed value in the corresponding row.
Bitmap indexes allow for efficient query processing, especially for complex combinations of predicates (AND, OR, NOT). These indexes are particularly useful in data warehousing and decision support systems, where ad-hoc queries and complex reporting are common.

Index-Organized Tables (IOTs)

Index-Organized Tables are a type of table storage organization in Oracle that combines the features of a table and a B-tree index. They are specifically designed for efficient storage and retrieval of data, particularly for primary-key-based queries.
In an IOT, the table data is stored within the index structure itself, unlike conventional heap-organized tables where the data and index are separate. This leads to reduced storage requirements and faster primary-key-based queries, as both the index and data can be accessed together.
IOTs are best suited for applications that require fast access to data based on the primary key, such as online transaction processing (OLTP) systems. They are also useful for storing dimension tables in data warehouses.

The relationship between Bitmap Indexes and Index-Organized Tables is as follows: Although Bitmap Indexes and IOTs are different in nature and serve different purposes, they can coexist within the same Oracle database. For instance, you can create Bitmap Indexes on columns of an Index-Organized Table if necessary. However, it is essential to analyze the specific requirements of your application and the nature of the data before deciding which object to use.
In summary, Bitmap Indexes and Index-Organized Tables are distinct database objects in Oracle that cater to different use cases. While Bitmap Indexes are ideal for low-cardinality columns and complex query processing, IOTs are designed for efficient primary-key-based data storage and retrieval. Understanding their characteristics and relationship can help developers optimize database performance and resource utilization.

A secondary index on an index-organized table can be a bitmap index. A bitmap index stores a bitmap for each index key. When bitmap indexes exist on an index-organized table, all the bitmap indexes use a heap-organized mapping table. The mapping table stores the logical rowids of the index-organized table. Each mapping table row stores one logical rowid for the corresponding index-organized table row. The database accesses a bitmap index using a search key. If the database finds the key, then the bitmap entry is converted to a physical rowid. With heap-organized tables, the database uses the physical rowid to access the base table. With index-organized tables, the database uses the physical rowid to access the mapping table, which in turn yields a logical rowid that the database uses to access the index-organized table. Figure 5-3 illustrates index access for a query of the departments_iot table.

Figure 5-3 Bitmap Index on index-organized Table — Figure 5-3: Bitmap Index on an index-organized table, which stores a bitmap for each index key

Bitmapped index

Index values: Each value contains a series of bits, each of which point to a particular row.
Bit values: If a bit is set to 1, it means that the associated row contains that value.
Row: The bit is associated with the ROWID of a row.

Bitmapped indexes are not stored in sorted order, but they can be very powerful in data warehouse applications, where there are many selection conditions. Oracle can line up the bitmaps for each condition and quickly select the appropriate rows.

Oracle Index Types - Quiz

Click the quiz link below to answer a few questions about index types.
Index Types - Quiz
The next lesson shows how to create an index.

[1]low-cardinality columns: Low-cardinality columns in Oracle indexes are columns that have a relatively small number of distinct values. For example, a column that stores the gender of a customer might have only two possible values, male and female. This would be considered a low-cardinality column.