Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 77 ยท Databases and Data Interview Questions

Databases: Indexes, Normalization and Transactions

Answer database design interview questions: how B-tree indexes and query plans work, normalization, ACID transactions, isolation levels and deadlocks.

After the query-writing round, the next database questions are about why things are fast, correct or broken. "Why is this query slow?", "What is an index?", "What does ACID mean?", "What happens if two transactions update the same row?" These test whether you understand what the database does underneath, not just the syntax.

The examples run in the in-browser SQL runner, which uses SQLite. SQLite is a real relational database and shows indexes, query plans, constraints and transactions faithfully. A few topics (isolation levels, locks, deadlocks) depend on server databases such as PostgreSQL or MySQL InnoDB, which the site cannot run; those parts are read-only, and I say so each time. Dialect differences are noted where they matter. For background, see the indexes and transactions lessons.

Four ideas interviewers test

Indexes A sorted structure for fast lookups.
Normalization Store each fact once.
ACID Transactions you can trust.
Concurrency Isolation and deadlocks.

Everything is a trade-off between speed, space and safety.

1 / 2

What is an index, and how does it help?

Short answer: an index is a separate, sorted data structure that maps column values to the rows that contain them. Without one, the database must read every row (a full table scan, O(n)). With one it can jump to the matching rows (O(log n) for a B-tree) and then fetch them.

Most relational databases use a B-tree (or B+tree): a shallow, wide, balanced tree where each node holds many sorted keys. Because nodes are wide, even a table with hundreds of millions of rows needs only three or four page reads to find a key. B-trees support equality (=), ranges (BETWEEN, <, >), prefix matches (LIKE 'abc%') and sorted output (ORDER BY). Hash indexes support only equality.

Indexes are not free. Every INSERT, UPDATE and DELETE must also update each index, and indexes take disk and memory. So the answer to "should we index every column?" is no: index columns used in WHERE, JOIN and ORDER BY of frequent, slow queries.

Reading a query plan

The query plan tells you what the database will actually do. Every database has a command for it (EXPLAIN in PostgreSQL and MySQL, EXPLAIN QUERY PLAN in SQLite). Run this and compare the two plans:

SQL Query plan before and after an index

Press Run (or Ctrl + Enter) to see the result here.

The first plan says the table is scanned; the second says it is searched using the index. The wording differs between databases, but the idea is the same: look for "scan" (reads everything) versus "seek/search/index" (jumps). In PostgreSQL you will see Seq Scan versus Index Scan; in MySQL, type: ALL versus ref.

Composite indexes and the leftmost-prefix rule

An index on (customer_id, status) is sorted by customer_id first, then by status inside each customer. It helps queries filtering by customer_id alone, or by both columns. It does not help a query that filters only by status, just as a phone book sorted by last name then first name cannot help you find everyone named "Anna". Column order should put equality conditions first and the most selective column early.

SQL The leftmost-prefix rule in a plan

Press Run (or Ctrl + Enter) to see the result here.

Why might an index not be used?

  • A function wraps the column: WHERE LOWER(email) = '[email protected]' cannot use a plain index on email (use an expression index where supported).
  • A leading wildcard: LIKE '%son'.
  • Implicit type conversion, such as comparing a string column with a number.
  • The table is tiny, or the condition matches most rows, so scanning is cheaper. The optimizer decides using statistics.
  • Low-selectivity columns, such as a boolean, rarely benefit from indexes alone.

A covering index contains every column the query needs, so the database never visits the table itself. That is often the cheapest fix for a hot query.

Normalization

Short answer: normalization organizes tables so each fact is stored once, which prevents update, insert and delete anomalies.

  • 1NF: each cell holds one atomic value; no repeating groups (no phones = "555-1, 555-2").
  • 2NF: in a table with a composite key, every non-key column depends on the whole key, not part of it.
  • 3NF: non-key columns depend only on the key, not on other non-key columns (a city column and a zip_code column that determines it should be split out).

A table storing order_id, product_id, product_name, product_price repeats the product name on every order line. Rename a product and you must update many rows (and might miss some). Splitting products into their own table fixes that. Denormalization means deliberately breaking these rules (copying a name or counter) to avoid joins on very hot reads. It is a trade-off you accept knowingly, with a plan to keep the copies consistent.

SQL A normalized design with constraints

Press Run (or Ctrl + Enter) to see the result here.

The last statement fails: product 99 does not exist, so the foreign key rejects it. (SQLite only enforces foreign keys when the pragma is on; PostgreSQL and MySQL enforce them by default.) That is the C in ACID at work.

ACID and transactions

A transaction groups statements so they succeed or fail as a unit. The classic example is a bank transfer: debit one account and credit another. If the system crashes between the two, atomicity means the debit is undone.

SQL A transfer that rolls back

Press Run (or Ctrl + Enter) to see the result here.

Inside the transaction you can see the debit, but ROLLBACK undoes it, and the balances match the state before BEGIN. In real code the trigger is usually an error: if a statement violated the CHECK (balance >= 0) rule (for example debiting 500 from Alice), the database would reject it, and the application would roll back the whole transaction instead of leaving a half-finished transfer.

Durability means a committed transaction survives a crash. Databases get it by writing changes to a write-ahead log and flushing it to disk before saying "committed"; the data files can be updated later and replayed from the log after a crash.

Isolation levels (read-only)

Isolation controls what a transaction can see of other transactions' work. The anomalies it prevents are:

  • Dirty read: seeing another transaction's uncommitted changes.
  • Non-repeatable read: reading the same row twice and getting different values because someone committed in between.
  • Phantom read: running the same range query twice and getting different sets of rows.

The SQL standard defines four levels, from weakest to strongest:

Level Dirty read Non-repeatable read Phantom read
READ UNCOMMITTED possible possible possible
READ COMMITTED prevented possible possible
REPEATABLE READ prevented prevented possible (by the standard)
SERIALIZABLE prevented prevented prevented
SQL
-- Read-only: PostgreSQL syntax; the site's runner cannot run concurrent sessions
BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT balance FROM accounts WHERE name = 'alice';
-- another session commits a change to alice here
SELECT balance FROM accounts WHERE name = 'alice';  -- same value as the first read
COMMIT;

Real products differ from the table: PostgreSQL's default is READ COMMITTED and its REPEATABLE READ also prevents phantoms through snapshots; MySQL InnoDB defaults to REPEATABLE READ. If asked, say you would check the documentation of the database in use and that higher isolation costs throughput or causes retries.

Deadlocks (read-only)

A deadlock occurs when two transactions each hold a lock the other needs. Transaction A locks row 1 and wants row 2; transaction B locks row 2 and wants row 1. Neither can proceed. Databases detect the cycle and abort one transaction (the "victim") with an error; the application should retry it.

To reduce deadlocks: always touch rows in a consistent order (for example, lower account ID first), keep transactions short, avoid user interaction inside a transaction, and use appropriate indexes so that fewer rows are locked.

SQL
-- Read-only: two sessions running at the same time
-- Session A                                   -- Session B
BEGIN;                                         BEGIN;
UPDATE accounts SET balance = balance - 1      UPDATE accounts SET balance = balance - 1
  WHERE name = 'alice';                          WHERE name = 'bob';
UPDATE accounts SET balance = balance + 1      UPDATE accounts SET balance = balance + 1
  WHERE name = 'bob';   -- waits for B            WHERE name = 'alice'; -- waits for A: deadlock

What is real and what is a stand-in: everything run above is real SQLite (indexes, plans, constraints, transactions). Isolation levels and deadlocks need several concurrent sessions on a server database, so they are shown as read-only text.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A table has an index on (last_name, first_name). Which query can use it efficiently?

    The index is sorted by last_name first (leftmost prefix). Filtering only by first_name cannot seek into it, and wrapping a column in a function usually prevents index use.
  2. 2. What does atomicity guarantee?

    Atomicity means all-or-nothing. If any step fails, the whole transaction is rolled back.
  3. 3. Which anomaly is prevented by READ COMMITTED but not by READ UNCOMMITTED?

    READ COMMITTED only lets you see committed data, so dirty reads are gone; non-repeatable and phantom reads can still happen.
  4. 4. What is the most reliable way to reduce deadlocks between transfers?

    If every transaction acquires locks in the same order, a circular wait cannot form. Short transactions hold locks for less time.
  5. 5. A product_name column is copied into every order line. Which problem is this?

    The same fact is stored in many rows, so renaming the product requires updating them all. Normalize it, or denormalize deliberately.

Summary

  • An index is a sorted structure (usually a B-tree) that turns scans into seeks; it costs write speed and space.
  • Read the query plan to see scan versus index use; composite indexes follow the leftmost-prefix rule.
  • Functions on columns, leading wildcards and type mismatches often block index use.
  • Normalization stores each fact once (1NF, 2NF, 3NF); denormalize only on purpose.
  • ACID: atomic, consistent, isolated, durable; the write-ahead log provides durability.
  • Isolation levels trade anomalies (dirty, non-repeatable, phantom reads) against throughput.
  • Deadlocks are cycles of waiting locks; prevent them with consistent lock order and short transactions, and retry the victim.

Next: Databases: NoSQL, Caching and Scaling.