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 INDEXcommand - 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
SELECTquery, 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
- table scan
Hit ratio is the percentage of table rows selected by a query.
- aka filter factor or selectivity
- when a
SELECTquery is executed,- the database examines the
WHEREclause 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:
- looks for an indexed column in the
WHEREclause - scans the index
- finds values that match the
WHEREclause - reads the corresponding table blocks
- looks for an indexed column in the
- the database examines the
- if the
WHEREclause 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
Binary Search
In a binary search, the database repeatedly splits the index in two until it finds the entry containing the search value.
- how it works:
- database first compares the search value to an entry in the middle of the index
- 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
- 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
- primary index
- 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
- dense index
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
- insert
- 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