Bigtable schema design in GCP - Time & Space Complexity

Time Complexity: Bigtable schema design

O(n)

Understanding Time Complexity

When designing a Bigtable schema, it is important to understand how the layout affects the speed of data access.

We want to know how the time to read or write data changes as the amount of data grows.

Scenario Under Consideration

Analyze the time complexity of reading rows with a well-designed Bigtable schema.

// Example: Reading rows by row key prefix
Table.readRows({
  prefix: 'user#1234#',
  limit: 100
});

This code reads up to 100 rows that start with a specific prefix in the row key.

Identify Repeating Operations

Look at what repeats when reading rows by prefix.

• Primary operation: Scanning rows that match the prefix.
• How many times: Up to the number of rows with that prefix, limited here to 100.

How Execution Grows With Input

As the number of rows with the prefix grows, the time to read them grows roughly in direct proportion.

Input Size (rows with prefix)	Approx. Operations
10	10 row reads
100	100 row reads
1000	1000 row reads

Pattern observation: The time grows linearly with the number of rows read.

Final Time Complexity

Time Complexity: O(n)

This means reading n rows takes time proportional to n; doubling rows roughly doubles the time.

Common Mistake

[X] Wrong: "Reading rows by prefix is always fast no matter how many rows match."

[OK] Correct: If many rows share the prefix, reading all of them takes longer because each row must be accessed.

Interview Connect

Understanding how schema design affects read time helps you explain how to keep Bigtable queries efficient as data grows.

Self-Check

"What if we changed the row key design to include a timestamp at the start? How would that affect the time complexity of reading recent rows?"