Single-Level Indexes


A single-level index is a file containing column values, along with pointers to rows containing the column value.

  • pointer identifies the block containing the row
    • may also identify the exact location of the row within the block in some indexes
  • indexes are created by database designers with CREATE INDEX command
  • normally sorted on the column value
  • sorted index is no the same as an index on a sorted table
    • e.g., index on a heap table is a sorted index on an unsorted table
  • if index column is unique,
    • index has one entry for each column value
  • if index column is not unique,
    • index may have multiple entries for some column values
    • or one entry for each column value, followed by multiple pointers
  • index is usually defined on a single column
    • but can be multiple

In a multi-column index, each index entry is a composite of values from all indexed columns.

  • behave exactly like indexes on a single column

Query Processing

  • to execute a SELECT query, a database can perform a:
    • table scan
      • is a database operation that reads table blocks directly, without accessing an index
    • index scan
      • is a database operation that reads index blocks sequentially, in order to locate the needed table blocks

Hit ratio is the percentage of table rows selected by a query.

  • aka filter factor or selectivity
  • when a SELECT query is executed,
    • the database examines the WHERE clause and estimates hit ratio
    • if ratio is high, performs a table scan
    • if ratio is low, the query needs only a few table blocks, so:
      1. looks for an indexed column in the WHERE clause
      2. scans the index
      3. finds values that match the WHERE clause
      4. reads the corresponding table blocks
  • if the WHERE clause does not contain an indexed column,
    • the database must perform a table scan
  • index requires fewer blocks than a table
    • bc column value and pointer occupy less space than an entire row
  • index scans are much faster than table scans
  • some cases, indexes can be small enough to reside in main memory, and scan time is insignificant
  • When hit ratio is low,
    • additional time to read the table blocks containing selected rows is insignificant

In a binary search, the database repeatedly splits the index in two until it finds the entry containing the search value.

  • how it works:
    1. database first compares the search value to an entry in the middle of the index
    2. If the search value is less than the entry value,
      • the search value is in the first half of the index
      • If not, the search value is in the second half
    3. database continues in this manner until it finds the index block containing the search value

Primary and Secondary Indexes

  • indexes on a sorted table can be:
    • primary index
      • is an index on a sort column.
      • aka clustering index
      • sorted table can have only one sort column
        • thus only one primary index
        • usually is on the primary key columns
    • secondary index
      • is an index that is not on the sort column.
      • aka non-clustering index
      • tables can have many secondary indexes
      • all indexes of a heap or hash table are secondary
        • since they have no sort column
  • indexes can be:
    • dense index
      • contains an entry for every table row
      • secondary indexes are on non-sort columns
        • thus always dense
    • sparse index
      • contains an entry for every table block
      • primary indexes are on sort columns and usually sparse
      • much faster than dense
        • have fewer entries and occupy fewer blocks

Inserts, Updates, and Deletes

  • Inserts, updates, and deletes to tables have an impact on single-level indexes
  • Consider the behavior of dense indexes:
    • insert
      • When a row is inserted into a table, a new index entry is created
      • Since single-level indexes are sorted, the new entry must be placed in the correct index block
      • If this block is full, the block splits in two to create space for the new index entry
    • delete
      • When a row is deleted, the row’s index entry must be deleted
      • deleted entry can be either physically removed or marked as ‘deleted’
      • Since single-level indexes are sorted, physically removing an entry requires moving all subsequent entries, which is slow
      • For this reason, index entries are marked as ‘deleted’
      • database may reorganize the index to remove deleted entries and compress the index, periodically
    • update
      • An update to a column that is not indexed does not affect the index
      • An update to an indexed column is like a delete followed by an insert
      • index entry for the initial value is deleted and an index entry for the updated value is inserted
  • With a sparse index,
    • each entry corresponds to a table block rather than a table row
    • index entries are inserted or deleted when blocks split or merge
    • Since blocks contain many rows, block splits and mergers occur less often than row inserts and deletes
    • aside from frequency, behavior of sparse and dense indexes is similar