Relation - Index (Indices)

About

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

Indexing the data can lead to either performance or degradation of queries, so understanding indexing is an important step in the data modeling process.

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.

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.

Task Runner