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 - 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.

4 - 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.