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).
Oracle bitmap indexes
Bitmap indexes are completely different to b-tree indexes. Whereas b-tree indexes are ideal for storing highly selective/unique values (low cardinality), bitmap indexes are designed to store values of low cardinality 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.
