Bitmap and BTree Indexes

According to conventional wisdom, Bitmap index is a preferred indexing technique for cases where the indexed attributes have few distinct values (i.e., low cardinality). The query response time is expected to degrade as the cardinality of indexed columns increase due to a larger index size. On the other hand, B-tree index is good if the column values are of high cardinality due to its indexing and retrieving mechanisms.

In summary, bitmap indexes are best suited for DSS regardless of cardinality for these reasons:

  • With bitmap indexes, the optimizer can efficiently answer queries that include AND, OR, or XOR. (Oracle supports dynamic B-tree-to-bitmap conversion, but it can be inefficient.)
  • With bitmaps, the optimizer can answer queries when searching or counting for nulls. Null values are also indexed in bitmap indexes (unlike B-tree indexes).
  • Most important, bitmap indexes in DSS systems support ad hoc queries, whereas B-tree indexes do not. More specifically, if you have a table with 50 columns and users frequently query on 10 of them—either the combination of all 10 columns or sometimes a single column—creating a B-tree index will be very difficult. If you create 10 bitmap indexes on all these columns, all the queries can be answered by these indexes, whether they are queries on all 10 columns, on 4 or 6 columns out of the 10, or on a single column. This limit is not imposed with bitmap indexes.

In contrast, B-tree indexes are well suited for OLTP applications in which users’ queries are relatively routine (and well tuned before deployment in production), as opposed to ad hoc queries, which are much less frequent and executed during nonpeak business hours. Because data is frequently updated in and deleted from OLTP applications, bitmap indexes can cause a serious locking problem in these situations.

Structure of a B-Tree Index

At the top of the index is the root, which contains entries that point to the next level in the index. At the next level are branch blocks, which in turn point to blocks at the next level in the index. At the lowest level are the leaf nodes, which contain the index entries that point to rows in the table. The leaf blocks are doubly linked to facilitate scanning the index in an ascending as well as descending order of key values.

Format of Index Leaf Entries
An index entry is made up of the following components:

• An entry header, which stores number of columns and locking information
• Key values consisting of length and value pairs for each key column
• ROWID of a row, which contains the key values

Index Leaf Entry Characteristics
In a B-tree index on a nonpartitioned table:
• Key values are repeated if there are multiple rows that have same key value.
• There is no index entry corresponding to a row that has all key columns that are NULL. Therefore a WHERE clause specifying NULL will always result in a full table scan.
• Restricted ROWID is used to point to the rows of the table, since all rows belong to the same segment.

Effect of DML Operations on an Index
The Oracle server maintains all the indexes when DML operations are carried out on the table. Here is an explanation of the effect of a DML command on an index:
• Insert operations result in the insertion of index entry in appropriate block.
• Deleting a row results only in a logical deletion of the index entry. The space used by the deleted row is not available for new entries until all the entries in the block are deleted.
• Updates to the key columns result in a logical delete and an insert to the index. The PCTFREE setting has no effect on the index except at the time of creation. A new entry may be added to an index block even if it has less space than that specified by PCTFREE.

Structure of a Bitmap Index

A bitmap index is also organized as a B-tree, but the leaf node stores a bitmap for each key value instead of a list of ROWIDs. Each bit in the bitmap corresponds to a possible ROWID, and if the bit is set, it means that the row with the corresponding ROWID contains the key value.

The leaf node of a bitmap index contains the following:
• An entry header, containing the number of columns and lock information
• Key values consisting of length and value pairs for each key column
• Start ROWID and End ROWID

• A bitmap segment consisting of a string of bits (The bit is set when the corresponding row contains the key value and is unset when the row does not contain the key value. The Oracle server uses a patented compression technique to store bitmap segments.)

The start ROWID is the ROWID of the first row pointed to by the bitmap segment of the bitmap—that is, the first bit of the bitmap corresponds to that ROWID, the second bit of the bitmap corresponds to the next row in the block, and the end ROWID is a pointer to the last row in the table covered by the bitmap segment. Bitmap indexes use restricted ROWIDs.

Using a Bitmap Index
The B-tree is used to locate the leaf nodes that contain bitmap segments for a given value of the key. Start ROWID and the bitmap segments are used to locate the rows that contain the key value.
When changes are made to the key column in the table, bitmaps must be modified. This results in locking of the relevant bitmap segments. Because locks are acquired on the whole bitmap segment, a row that is covered by the bitmap cannot be updated by other transactions until the first transaction ends.

B-Tree Index

Bitmap Index

Suitable for high-cardinality columns Suitable for low-cardinality columns
Updates on Keys relatively easy Updates on Key columns very expensive
Inefficient for queries using OR predicates Efficient for queries using OR predicates
Useful for OLTP Useful for datawarehousing

2 responses to this post.

  1. Posted by Tushar on November 17, 2010 at 10:09 am

    Could you please provide the detailed structure of a B-tree index leaf block?
    I am not able to understand the sentence “Key Column length-value pairs, which define size of column in the key followed by the value for the column”

    What exactly this Key column lenth-value pais are?


    • Posted by mohibalvi on November 27, 2010 at 12:48 am

      I have changed the line “Key Column length-value pairs, which define size of column in the key followed by the value for the column” to
      “Key values consisting of length and value pairs for each key column” which is easier to understand meaning that not only the value of the index key column but the length of the column is also stored in the index leaf block as a pair along.

      For further details you can read this document
      Understanding Indexes By Tim Gorman


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: