How index works in oracle

Hi,
Few days back kavita commented on my post to write about indexes so I found some time to write about indexes.We all know how important are these indexes specially when you have huge data and lot of trasactions are going on and how important they are when it comes to selecting the execution plan for the SQL statements and How important they are for changing the execution plan which optimizer chooses for giving you the desired result in least response time as possible,in order to enhance the performance of your applications.In this brief post I'm discussing how index works in oracle and how can we make use of these indexes to our maximum benefit.

Let me describe the indexes provided by oracle,
Oracle Database provides several indexing schemes.But,
In short there are only 2 types
1)B-tree(Balanced-tree) indexes
2)Bitmap indexes
These 2 types are subdivided as follows:

1)B-tree(Balanced-tree) indexes:

Features of B-tree(Balanced-tree) indexes are as follows:
-----------------------------------------------------------------------------------
These indexes are the standard index type. They are excellent for primary key and highly-selective indexes. Used as concatenated indexes, B-tree indexes can retrieve data sorted by the indexed columns. B-tree indexes have the following subtypes:
*Index-organized tables
An index-organized table differs from a heap-organized because the data is itself the index.

*Reverse key indexes
In this type of index, the bytes of the index key are reversed, for example, 103 is stored as 301. The reversal of bytes spreads out inserts into the index over many blocks.

*Descending indexes
This type of index stores data on a particular column or columns in descending order.

*B-tree cluster indexes
This type of index is used to index a table cluster key. Instead of pointing to a row, the key points to the block that contains rows related to the cluster key.

How B-tree indexes work:
-----------------------------------------
It is very important to know how this indexes actually work to use them to maximum benefit.The mechanism followed by balanced-tree indexes is as follows:

B-tree index has 3 parts:
1)Root
2)Branch blocks
3)Leaf blocks

*Root is the centre-point from where all the branch blocks and leaf blocks is connected.
=>A B-tree index has two types of blocks
1)Branch blocks
2)Leaf blocks

*Branch blocks for searching and leaf blocks that store values.
*Branch blocks store the minimum key prefix needed to make a branching decision between two keys. This technique enables the database to fit as much data as possible on each branch block.
*The branch blocks contain a pointer to the child block containing the key.
The number of keys and pointers is limited by the block size.

*The leaf blocks contain every indexed data value and a corresponding rowid used to locate the actual row. Each entry is sorted by (key, rowid). Within a leaf block, a key and rowid is linked to its left and right sibling entries.

*The branch blooks in one sense is for storing the key value and the leaf block is for sorting as per rowid(As in case of lock if the key is exact the lock will open fast or else it will take time and sorting with rowid is the fastest method to sort data in compare to rownum).

*If the database scans the index for a value, then it will find this value in n I/Os where n is the height of the B-tree index(The height of the index is the number of blocks required to go from the root block to a leaf block).
This is the basic principle behind Oracle Database indexes.

2)Bitmap indexes:

Feautures of Bitmap indexes:
-------------------------------------------------------------------------

*Bitmap and bitmap join indexes
=>In a bitmap index, an index entry uses a bitmap to point to multiple rows.
In contrast, a B-tree index entry points to a single row.This is major difference between
the B-tree and Bitmap indexes.
=>A bitmap join index is a bitmap index for the join of two or more tables.

*Function-based indexes
This type of index includes columns that are either transformed by a function, such as the UPPER function, or included in an expression.
B-tree or bitmap indexes can be function-based.

*Application domain indexes
This type of index is created by a user for data in an application-specific domain. The physical index need not use a traditional index structure and can be stored either in the Oracle database as tables or externally as a file.

How Bitmap indexes work:
--------------------------------------------

*In the Bitmap index the values are stored in the form of 0's and 1's as you see below:

Eg:Bitmap structure might look like this:

Value Row 1 Row 2 Row 3 Row 4 Row 5 Row 6 Row 7
M 1 0 1 1 1 0 0
F 0 1 0 0 0 1 1

Where M:male and F:Female represent status for gender

*Each bit in the bitmap corresponds to a possible rowid. If the bit is set, then the row with the corresponding rowid contains the key value.
*A mapping function converts the bit position to an actual rowid, so the bitmap index provides the same functionality as a B-tree index
although it uses a different internal representation.

*Bitmap indexing efficiently merges indexes that correspond to several conditions in a WHERE clause.
*Rows that satisfy some, but not all, conditions are filtered out before the table itself is accessed. This technique improves response time in case of Bitmap indexes.


Difference between B-tree(Balanced tree) and Bitmap indexes:
-------------------------------------------------------------------------------------

1) B-tree indexes index entry points to a single row
Where as,In case of Bitmap indexes index entry point to multiple rows.

2)B-tree indexes are more suitable for high cardinality columns(i.e the number of distinct values is large compared to the number of table rows) eg:ename.
Where as,Bitmap indexes are more suitable for low cardinality columns(i.e the number of distinct values is small compared to the number of table rows) eg:Male or female status for gender.

3)B-tree indexes are used in OLTP environment (eg:Banking Database where there will be huge trasactions taking place).
Where as,Bitmap indexes are primarily designed for data warehousing or environments in which queries reference many columns in an ad hoc fashion(eg:Datawarehouse Database of huge size).

4)In the B-tree indexes actually values are stored in leaves(which is a part of B-tree indexstructure).
Where as,In Bitmap indexes the values are stored in Bits(0's and 1's).

5)In the OLTP environment where there are lot of DML activities are happening it is more advantageous to use B-tree indexes.
Where as,In the OLAP(Datawarehousing) environment or DSS(Decision support system) where we have to perform read only(selecting the data) activities Bitmap indexes are more recommended.

This document is prepared to use indexes to their Best.Hope it helps.


Best regards,

Rafi.