Primary keys and uniqueness in SQL - Time & Space Complexity

Time Complexity: Primary keys and uniqueness

O(log n)

Understanding Time Complexity

When we use primary keys and uniqueness constraints in a database, the system must check if new data breaks these rules.

We want to know how the time to check these rules grows as the data grows.

Scenario Under Consideration

Analyze the time complexity of inserting a new row with a primary key constraint.

INSERT INTO users (user_id, name) VALUES (123, 'Alice');
-- user_id is the primary key
    

This code adds a new user, ensuring the user_id is unique as required by the primary key.

Identify Repeating Operations

What does the database do to keep the primary key unique?

• Primary operation: Searching the index for the user_id to check uniqueness.
• How many times: Once per insert, but the search depends on the number of rows.

How Execution Grows With Input

As the table grows, the time to check if the user_id exists changes.

Input Size (n)	Approx. Operations
10	About 4-5 steps to find or confirm uniqueness
100	About 7 steps
1000	About 10 steps

Pattern observation: The number of steps grows slowly, not directly with n, but with how deep the index tree is.

Final Time Complexity

Time Complexity: O(log n)

This means checking uniqueness takes a little more time as data grows, but it grows slowly and efficiently.

Common Mistake

[X] Wrong: "Checking uniqueness takes the same time no matter how big the table is."

[OK] Correct: The database uses an index, which grows in a balanced way, so checking takes more steps as data grows, but not one step per row.

Interview Connect

Understanding how primary keys affect performance shows you know how databases keep data safe and fast, a key skill for real projects.

Self-Check

"What if the primary key was not indexed? How would the time complexity change?"