Table Indexes

A table index is a replica of a subset of a table’s columns that is organized and/or sorted for efficient access using a subset of those attributes.
Instead of performing a sequential scan, the DBMS can perform a lookup on the table index to find certain tuples more quickly.
Sync between indexes and the table.

B+ Tree Index

The DBMS can use a B+Tree index if the query provides any of the attributes of the search key.
This differs from a hash index, which requires all attributes in the search key.

Duplicate keys

The first approach is to append record IDs as part of the key. Since each tuple’s record ID is unique, this will ensure that all the keys are identifiable. The second approach is to allow leaf nodes to spill into overflow nodes that contain the duplicate keys. Although no redundant information is stored, this approach is more complex to maintain and modify.

Clustered Indexes

The table is stored in the sort order specified by the primary key, as either heap- or index-organized storage. Since some DBMSs always use a clustered index, they will automatically make a hidden row id primary key if a table doesn’t have an explicit one, but others cannot use them at all.

Hash Index

  • TODO: Optimization and Hash Index

Covering Index

Not an actual index method. A covering index is a regular index that provides all the data required for a query without having to access the actual table. When a query is executed, the database looks for the required data in the index tree, retrieves it, and returns the result.