PRIMARY KEY constraint in SQL - Time & Space Complexity

Time Complexity: PRIMARY KEY constraint

O(log n)

Understanding Time Complexity

When we use a PRIMARY KEY constraint in a database table, it helps keep data unique and easy to find.

We want to understand how the time to check or find a primary key changes as the table grows.

Scenario Under Consideration

Analyze the time complexity of inserting and searching rows with a PRIMARY KEY constraint.

CREATE TABLE Employees (
  EmployeeID INT PRIMARY KEY,
  Name VARCHAR(100),
  Department VARCHAR(50)
);

INSERT INTO Employees (EmployeeID, Name, Department) VALUES (1, 'Alice', 'HR');
SELECT * FROM Employees WHERE EmployeeID = 1;
    

This code creates a table with a PRIMARY KEY on EmployeeID, inserts a row, and searches by that key.

Identify Repeating Operations

When inserting or searching, the database checks the PRIMARY KEY to keep values unique and find rows fast.

• Primary operation: Searching or checking the PRIMARY KEY index.
• How many times: Depends on the number of rows, but the index helps avoid scanning all rows.

How Execution Grows With Input

As the table grows, the database uses the PRIMARY KEY index to quickly find or check keys without looking at every row.

Input Size (n)	Approx. Operations
10	About 3-4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: The steps grow slowly even as the table gets much bigger, thanks to the index.

Final Time Complexity

Time Complexity: O(log n)

This means finding or checking a primary key takes a small number of steps that grow slowly as the table gets bigger.

Common Mistake

[X] Wrong: "Searching by PRIMARY KEY scans every row, so it takes longer as the table grows linearly."

[OK] Correct: The PRIMARY KEY uses an index (like a tree) that lets the database jump quickly to the right spot without checking every row.

Interview Connect

Understanding how PRIMARY KEY constraints speed up data access shows you know how databases keep things efficient as data grows.

Self-Check

"What if the PRIMARY KEY was not indexed? How would the time complexity for searching change?"