Relation - Index (Indices)

> (Data|State) Management and Processing > (Data Type|Data Structure) > (Relation|Table) - Tabular data > Relation - Index (Indices)

1 - About

An index is an auxiliary data structure of a relation database to speed up the retrieval of rows.


3 - Performance

  • Too many indexes and the performance of DML will suffer.
  • Too few indexes and the performance of queries (including inserts, updates, and deletes) will suffer.

Finding the right mix is critical to your application's performance.

When to index and what column to index are things you need to pay attention to in your design. An index does not always mean faster access, in fact, you will find that indexes will decrease performance in many case if Oracle uses them. See this example with B*Tree

  • btree : Conventional indexes. The most common indexes in use in Oracle and most other databases.
  • Bitmap index : Normally in a btree, there is a one-to-one relationship between an index entry and a row: an entry points to a row. With bitmap index, a single entry uses a bitmap to point to many rows simultaneously (One-to-Many Relationship). They are appropriate for highly repetitive data (data with a few distinct values relative to the total number of rows in the table)

Oracle as many other database can use an index on a column to count the number of rows in the table only when the column has been declared NOT NULL

4 - Access Pattern

  • B-Trees are the best choice for range requests (e.g., retrieve all records in a certain timeframe);
  • Hash-Maps are hard to beat in performance for key-based lookups;
  • Bloom-filters are typically used to check for record existence.

5 - Maintenance

In a database, index maintenance is an expensive process.

Example: a table with a 8k block and 1,000 rows of 200 bytes has

  • about 25 table blocks (1000/200/8000)
  • a few undo blocks
  • half a megabyte of redo

Adding one index on this table have the following consequences:

  • locate and modify 1,000 separate index leaf blocks.
  • access 1,000 different undo blocks for read consistency reasons
  • increment the redo about quarter of a megabyte

Adding more and more index and inserts will become rather low.