Database Indexing Performance

Primary Key

A primary key is a special type of index that enforces data integrity and ensures each row's uniqueness. When a primary key is defined on a table, the database management system automatically creates an index on the primary key column(s). This index allows for efficient lookups, insertions, updates, and deletions. Due to its unique values, searching for a specific primary key value has an average complexity of O(log(n)), where n is the number of rows in the table.

Unique Columns

Unique constraints ensure that the values in the specified column(s) are unique across all rows in the table. Like primary keys, unique columns are indexed to facilitate efficient searches and enforce data integrity. Searching for a specific unique value in a column has an average complexity of O(n/2), where n is the number of rows. However, in practice, this is still considered linear time complexity due to its proportional growth with the number of rows.

Non-Unique Columns

Non-unique columns contain duplicate values across different rows. These columns may not be suitable for primary keys or unique constraints, but they can still be indexed to speed up search operations. Indexing a non-unique column allows for average-case search complexity of O(n), where n is the number of rows. This is because, in the worst case, all rows might need to be examined to find the desired value.