How do indexes work internally in Oracle?

by neelima
(Hyderabad)

There are several types of index available for use in Oracle databases, the most common ones (in our experience) are B-tree (balanced tree) indexes, function-based indexes and bitmap indexes. B-tree indexes are more common in databases supporting OLTP systems and bitmap indexes are more commonly used in datawarehouses.


Oracle B-tree indexes


B-tree indexes are ordered lists of values divided into ranges with a key associated with a row or range of rows, thereby providing excellent retrieval performance for queries such as exact match and range searches.

This type of index contains 3 types of blocks - the root block, one or more branch blocks and one or more leaf blocks. The root block holds keys and pointers to the branch blocks which in turn hold pointers to the leaf blocks which contain the key (data) values that have been indexed and the rowids of the rows in the Oracle database table associated with each key value.

Branch blocks hold the minimum key prefix needed to be able to choose the required branch and a pointer to the child block containing the key. The number of keys and pointers is limited by the block size.

Index leaf blocks are double linked - each block contains pointers to the next and previous leaf blocks.

B-tree indexes are always balanced because the height of the index (the number of levels in the index) is the same throughout the index. In other words, the number of blocks that have to be read to find the rowid associated with any particular index value is not dependent on that value. For example if you had an index on the last_name column of the employee table in the sample Oracle database the number or blocks that would need to be read to find the rowid associated with "Ernst" would be the same as for "King".

The height of a b-tree index is the number of blocks required to go from the root block to a leaf block. For an index with one level of branch blocks the height is 3 (1 root block + 1 branch block + 1 leaf block).

For a more detailed technical discussion of b-tree index internals see this document by Richard Foot.

Oracle bitmap indexes


Bitmap indexes are completely different to b-tree indexes. Whereas b-tree indexes are ideal for storing highly selective/unique values (high cardinality), bitmap indexes are designed to store values of low cardinality (i.e. few distinct values) where the same value can be found in a large proportion of the table. An example of this might be the part number column in the sales table, or gender in the employee table.

With this type of index, each distinct value of the column is associated with a set of bits representing the rows in the table (one bit for each row in the table). Each bit has a value of 0 or 1. If the bit is set then then the row associated with that bit has that value in the column.

Bitmap indexes are expensive to maintain as the whole bitmap has to be rebuilt after any DML operation (insert/update/delete) on the table.

The Oracle Database Concepts is worth reading for background information about indexes.

Also see our Oracle training page for information about formal training courses both on-line and in person.

Comments for How do indexes work internally in Oracle?

Average Rating starstarstarstarstar

Click here to add your own comments

Aug 19, 2017
Rating
starstarstarstarstar
Good explanation about index NEW
by: Anonymous

Yes, I like your explanation.

Jan 18, 2016
Rating
starstarstarstarstar
Useful
by: Anonymous

Links to the detailed explanations aren't working.

Sep 07, 2015
Rating
starstarstarstarstar

by: John

Madhu,

To answer your question you can't have more than one index on exactly the same set of coulmns although you can have indexes that overlap. WHat happens in this case is that the Oracle cost-based optimizer picks the best vailable index to use (the one with the lowest cost).

Aug 20, 2015
Rating
starstarstarstarstar

by: Madhu

The content was very nice and very userful. But it is better to add more indexes definitions and usages of indexes. I have one question here if one column contain two indexes which index have first preference. How Clusted index will work in this case. Please explain this also, Appriciate your patientence. :) :)

Jul 27, 2015
Rating
starstarstarstarstar
excellent
by: aysha

I have read your post throughly with full interest. I have found a lot of good points in this post which are useful for everyone. This site have different categories and I have interest in education because I'm 7th grade student and looking australian assignment buy essay which must be good and according to my direction.

Jan 19, 2015
Rating
starstarstarstarstar
About Indexes
by: Naitik Shah

Very Nice Explanation which helps to know very well about indexes.

Mar 11, 2014
Rating
starstarstarstar
Nice Exp
by: Ayush Gokhru

Nice Explanation ...need some more about indexes..

How to create and syntax of diff indexes....

Some diagrams or flowcharts ....

Dec 18, 2012
Rating
starstarstarstarstar
Index
by: Sudhansu

Good One

Sep 19, 2012
Rating
starstarstarstarstar
Good explanation
by: Raghu

It is simple and nice explanation.Thankyou.

Click here to add your own comments

Join in and write your own page! It's easy to do. How? Simply click here to return to Oracle Questions.