Primary key declaration in MySQL - Time & Space Complexity

Time Complexity: Primary key declaration

O(log n)

Understanding Time Complexity

When we declare a primary key in a database table, the system creates a unique index to quickly find rows.

We want to understand how the time to insert or find data changes as the table grows.

Scenario Under Consideration

Analyze the time complexity of declaring a primary key and inserting rows.

CREATE TABLE users (
  id INT NOT NULL,
  name VARCHAR(100),
  PRIMARY KEY (id)
);

INSERT INTO users (id, name) VALUES (1, 'Alice');
INSERT INTO users (id, name) VALUES (2, 'Bob');
-- More inserts follow
    

This code creates a table with a primary key on the 'id' column and inserts rows.

Identify Repeating Operations

When inserting rows, the database must maintain the primary key index.

• Primary operation: Inserting into a balanced tree index (like B-tree) for the primary key.
• How many times: Once per insert operation, repeated for each row inserted.

How Execution Grows With Input

As the number of rows grows, inserting a new row requires searching the index to place the key correctly.

Input Size (n)	Approx. Operations
10	About 3 steps to insert
100	About 7 steps to insert
1000	About 10 steps to insert

Pattern observation: The number of steps grows slowly as the table grows larger, not directly proportional.

Final Time Complexity

Time Complexity: O(log n)

This means inserting or searching by primary key takes a little more time as the table grows, but it grows slowly and efficiently.

Common Mistake

[X] Wrong: "Inserting with a primary key is always slow because it checks every row."

[OK] Correct: The database uses an index structure that avoids checking every row, so it only needs a few steps even for large tables.

Interview Connect

Understanding how primary keys affect performance shows you know how databases keep data organized and fast to access, a key skill for many roles.

Self-Check

"What if we changed the primary key to a non-indexed column? How would the time complexity for searching change?"