DataBase Index

1. what is Database index?
A database index is a data structure that improves the speed of operations on a database table. Indexes can be created using one or more columns of a database table, providing the basis for both rapid random look ups and efficient access of ordered records.
An index

• is sorted by key values, (that need not be the same as those of the table)
• is small, has just a few columns of the table.
• refers for a key value to the right block within the table.
• speeds up reading a row, when you know the right search arguments.

2. Database Index Tips

• Put the most unique data element first in the index, the element that has the biggest variety of values. The index will find the correct page faster.
• Keep indexes small. It's better to have an index on just zip code or postal code, rather than postal code & country. The smaller the index, the better the response time.
• For high frequency functions (thousands of times per day) it can be wise to have a very large index, so the system does not even need the table for the read function.
• For small tables an index is disadvantageous. For any function the system would be better off by scanning the whole table. An index would only slow down.
• Index note:
• An index slows down additions, modifications and deletes. It's not just the table that needs an update, but the index as well. So, preferably, add an index for values that are often used for a search, but that do not change much. An index on bank account number is better than one on balance.

3.Index Implementations

3.1 The Oracle b-tree index

树最底层的块叫叶子节点，其中分别包括各个索引键以及一个rowid（指向索引的行），有意思的是，索引的叶子节点实际上构成了一个双向链表，一旦发现要从叶节点中的哪里“开始”，执行值的有序扫描（索引区间扫描index range scan）
就会很容易。我们不用再在索引结构中导航。
所以要满足如下的谓词条件将相当简单：
where x between 20 and 30
Oracle 发现一个最小键值大于或等于20的索引叶子块，然后水平地遍历叶子节点链表，直到命中一个大于30的值。

3.2 Bitmapped indexes

Oracle bitmap indexes are very different from standard b-tree indexes. In bitmap structures, a two-dimensional array is created with one column for every row in the table being indexed
在位图结构中，一个二位数组中的一列被用来存储被索引列的所有可能值
The real benefit of bitmapped indexing occurs when one table includes multiple bitmapped indexes. Each individual column may have low cardinality.
For example, assume there is a motor vehicle database with numerous low-cardinality columns such as car_color, car_make, car_model, and car_year. Each column contains less than 100 distinct values by themselves.
For example, assume we wanted to find old blue Toyota Corollas manufactured in 1981:

Create BITMAP index color_idx on vehicle(color);

select

   license_plat_nbr

from

   vehicle

where

   color = ‘blue’

and

   make = ‘toyota’

and

   year = 1981;

位图索引适用于低基数（low-cardinality)列，所谓低基数列就是这个列只有很少的可取值，但是对频繁更新的列不适用，因为一个键指向多行，可能数以百计甚至更多
如果更新一个位图索引键，那么这个键指向的数百条纪录会与你实际更新的那一行一同被有效地锁定。