Indexes

“An index makes the query fast” is the most basic explanation of an index .
An Oracle B-Tree index has a doubly linked list and a search tree. Each row in an indexed table corresponds to a leaf node, which is stored in a database block or page. All index blocks are of the same size and the database sorts and stores as many index entries as possible in each block. Databases use doubly linked lists to connect the so-called index leaf nodes. To identify a specific node out of the millions of index leaf nodes quickly, database creates a balanced search tree as shown below:

 

The Oracle database has three distinct operations that describe a basic index lookup:

INDEX UNIQUE SCAN 

The INDEX UNIQUE SCAN performs the tree traversal only. The Oracle database uses this operation if a unique constraint ensures that the search criteria will match no more than one entry.

INDEX RANGE SCAN 

The INDEX RANGE SCAN performs the tree traversal and follows the leaf node chain to find all matching entries. This is the fallback operation if multiple entries could possibly match the search criteria.

TABLE ACCESS BY INDEX ROWID 

The TABLE ACCESS BY INDEX ROWID operation retrieves the row from the table. This operation is (often) performed for every matched record from a preceding index scan operation.

The important point is that an INDEX RANGE SCAN can potentially read a large part of an index. If there is one more table access for each row, the query can become slow even when using an index.

A primary key does not necessarily need a unique index—you can use a non-unique index as well. In that case the Oracle database does not use an INDEX UNIQUE SCAN but instead the INDEX RANGE SCAN operation. 

If the primary key is composite, the database creates an index on all primary key columns—a so-called concatenated index. The column order of a concatenated index has great impact on its usability so it must be chosen carefully.