Oracle: Difference between b-tree and bitmap index

Question:  What is the difference between a btree and a bitmap index?  I need to understand the structural differences between a btree and a bitmap index and understand then to use a b-tree versus a bitmap index on a table column.
Answer:  Internally, a bitmap and a btree indexes are very different, but functionally they are identical in that they serve to assist Oracle in retrieving rows faster than a full-table scan.  The basic differences between b-tree and bitmap indexes include:

1:  Syntax differences:  The bitmap index includes the "bitmap" keyword.  The btree index does not say "bitmap".

2: Cardinality differences:  The bitmap index is generally for columns with lots of duplicate values (low cardinality), while b-tree indexes are best for high cardinality columns.

3: Internal structure differences:  The internal structures are quite different.  A b-tree index has index nodes (based on data block size), it a tree form:

A bitmap index looks like this, a two-dimensional array with zero and one (bit) values:

The Oracle b-tree index

The oldest and most popular type of Oracle indexing is a standard b-tree index, which excels at servicing simple queries. The b-tree index was introduced in the earliest releases of Oracle and remains widely used with Oracle. B-tree indexes are used to avoid large sorting operations. For example, a SQL query requiring 10,000 rows to be presented in sorted order will often use a b-tree index to avoid the very large sort required to deliver the data to the end user.

Oracle offers several options when creating an index using the default b-tree structure. It allows you to index on multiple columns (concatenated indexes) to improve access speeds. Also, it allows for individual columns to be sorted in different orders. For example, we could create a b-tree index on a column called last_name in ascending order and have a second column within the index that displays the salary column in descending order.

create index
    name_salary_idx
on
   person

(
   last_name asc,
   salary desc);

While b-tree indexes are great for simple queries, they are not very good for the following situations:

• Low-cardinality columns - Columns with less than 200 distinct values do not have the selectivity required in order to benefit from standard b-tree index structures.
• No support for SQL functions - B-tree indexes are not able to support SQL queries using Oracle's built-in functions. Oracle provides a variety of built-in functions that allow SQL statements to query on a piece of an indexed column or on any one of a number of transformations against the indexed column.

Prior to the introduction of Oracle function-based indexes (FBI), the Oracle cost-based SQL optimizer had to perform time-consuming long-table, full-table scans due to these shortcomings. Consequently, it was no surprise when Oracle introduced more robust types of indexing structures.

Bitmapped indexes

Oracle bitmap indexes are very different from standard b-tree indexes. In bitmap structures, a two-dimensional array is created with one column for every row in the table being indexed. Each column represents a distinct value within the bitmapped index. This two-dimensional array represents each value within the index multiplied by the number of rows in the table. At row retrieval time, Oracle decompresses the bitmap into the RAM data buffers so it can be rapidly scanned for matching values. These matching values are delivered to Oracle in the form of a Row-ID list, and these Row-ID values may directly access the required information.

The real benefit of bitmapped indexing occurs when one table includes multiple bitmapped indexes. Each individual column may have low cardinality. The creation of multiple bitmapped indexes provides a very powerful method for rapidly answering difficult SQL queries.

For example, assume there is a motor vehicle database with numerous low-cardinality columns such as car_color, car_make, car_model, and car_year. Each column contains less than 100 distinct values by themselves, and a b-tree index would be fairly useless in a database of 20 million vehicles. However, combining these indexes together in a query can provide blistering response times a lot faster than the traditional method of reading each one of the 20 million rows in the base table. For example, assume we wanted to find old blue Toyota Corollas manufactured in 1981.

select
   license_plat_nbr
from
   vehicle
and
   make = 'toyota'
and
   year = 1981;

Oracle uses a specialized optimizer method called a bitmapped index merge to service this query. In a bitmapped index merge, each Row-ID, or RID, list is built independently by using the bitmaps, and a special merge routine is used in order to compare the RID lists and find the intersecting values. Using this methodology, Oracle can provide subsecond response time when working against multiple low-cardinality columns.

Summary

1. B-Tree and Bitmap are two types of indexes used in Oracle.
2. Bitmap is a method of indexing, offering performance benefits and storage savings.
3. B-Tree index is an index that is created on columns that contain very unique values.
4. B-Tree works best with many distinct indexed values.
5. Bitmap works best with many distinct indexed values.
6. B-tree indexes are the default index type of the CREATE INDEX statement, but to create a bitmap index you need to specify CREATE BITMAP INDEX.
7. B-tree indexes are suitable for columns with a high number of distinct values. Bitmap indexes are suitable for columns with a  low number of distinct values.