Let's start with B-tree vs bitmap.
Regular indexes are B-trees. B stands for balanced. This means all the leaf nodes are at the same depth. So all entries take the same amount of work to access.
You can see how B-trees work with this visualization tool:
https://www.cs.usfca.edu/~galles/visualization/BTree.html Bitmap indexes store:
- Indexed values
- Start and end rowid marking a range of rowids
- A series of 1s and 0s to indicate which rows in the range above have the value (1 = the row has the value).
e.g.
Value Start_rowid End_rowid bitmap
VAL1 AAAA ZZZZZ 001000000...
VAL2 AAAA ZZZZZ 110000000...
VAL3 AAAA ZZZZZ 000111100...
The big advantage of bitmap indexes is it's trivial for the optimizer to combine them. So if you have:
create bitmap index b1 on t (c1);
create bitmap index b2 on t (c2);
create bitmap index b3 on t (c3);
And a query with:
where c1 = :v1
and c2 = :v2
and c3 = :v3
It's easy to AND the bitmaps together to find which rows match all the predicates. So you can create single column indexes on all your columns. And the optimizer can combine them as needed. This makes them great for tables subject to ad-hoc queries.
https://asktom.oracle.com/pls/asktom/f?p=100:11:0::::P11_QUESTION_ID:2049072400346231785 While the optimizer can combine indexes with B-trees, it's more work because it first has to convert the rowids to bitmaps. In general you need to create the multi-column index:
create index i on t (c1, c2, c3);
Plus all the other combinations you may wish to query.
So if bitmap indexes are so flexible, you may be wondering:
Why are B-trees the default instead of bitmaps?
Well, bitmap indexes come with a massive drawback:
Killing scalability.
They're one of the few situations in Oracle Database where an insert in one session can block an insert in another. This renders them useless for most OLTP applications.
https://asktom.oracle.com/pls/apex/f?p=100:11:::NO:RP:P11_QUESTION_ID:9533571800346380617 Note that bitmap indexes entries that are wholly null. Whereas B-tree indexes don't. So:
where col is null
Can use a bitmap index on col. But not a regular B-tree index on
create index i on t (c1);
You can get around this by adding a constant to the end of the B-tree index:
create index i on t (c1, 1);
Function-based IndexesThese are simply indexes where one or more of the columns have a function applied to them. For example:
create index i on t (trunc(dt));
For Oracle Database to use the index, the function in your where clause needs to match that in the index exactly. i.e.
where trunc(dt) := b1
Note: starting in 11.2.0.2, there's a special case where Oracle Database can use function-based indexes, even if the function is not in the query! This can happen if the function extracts the "leading portion" of the indexed values. For example, trunc() or substr:
create table t (
x date,
y varchar2(1)
);
insert into t values (sysdate, 'ABCDEF');
create index ix on t (trunc(x));
create index iy on t (substr(y, 1, 3));
select * from t
where x = sysdate;
select * from table(dbms_xplan.display_cursor(null, null, 'BASIC LAST'));
PLAN_TABLE_OUTPUT
EXPLAINED SQL STATEMENT:
------------------------
select * from t where x = sysdate
Plan hash value: 4213880728
----------------------------------------------------
| Id | Operation | Name |
----------------------------------------------------
| 0 | SELECT STATEMENT | |
| 1 | TABLE ACCESS BY INDEX ROWID BATCHED| T |
| 2 | INDEX RANGE SCAN | IX |
----------------------------------------------------
select * from t
where y = 'ABCDEF';
select * from table(dbms_xplan.display_cursor(null, null, 'BASIC LAST'));
PLAN_TABLE_OUTPUT
EXPLAINED SQL STATEMENT:
------------------------
select * from t where y = 'ABCDEF'
Plan hash value: 2460001713
----------------------------------------------------
| Id | Operation | Name |
----------------------------------------------------
| 0 | SELECT STATEMENT | |
| 1 | TABLE ACCESS BY INDEX ROWID BATCHED| T |
| 2 | INDEX RANGE SCAN | IY |
----------------------------------------------------
Clustered indexesThese don't exist in Oracle! (Though you can have indexed table clusters). I'm guessing your search brought back results from some other database. ;)
Though the concept does exist in Oracle Database:
Physically store data in the same logic order defined by the indexThis is known as an Index Organized Table (IOT). This combines two data structures - the table and an index - into one. The index for an IOT must be the primary key. These are most useful on tables:
- That have a multi-column primary key
- You regularly query using the first column(s) of the primary key
e.g.
create table t (
x int,
y int,
primary key (x, y)
);
select * from t
where x = :b1;
Because the rows are physically stored sorted by the primary key (x, then y), all the rows for a given value of X will be "next" to each other. This can reduce IO and make better use of your buffer cache.
For more on these, read Martin Widlake's IOT series:
https://mwidlake.wordpress.com/2011/07/18/index-organized-tables-the-basics/ If you want to know more about indexes, check out the concepts guide:
http://docs.oracle.com/database/122/CNCPT/indexes-and-index-organized-tables.htm#CNCPT721 Or Richard Foote's blog which is dedicated to indexes in Oracle:
https://richardfoote.wordpress.com/