Database indexing interview questions, with answers

The questions, with answers

1. 1.What is an index, and what does it cost?

   An index is a separate, ordered structure — almost always a B+ tree — that maps the values of one or more columns to the rows that hold them, so the database can find matching rows by walking a few tree levels instead of scanning the whole table. A lookup on a million-row table drops from a million row reads to three or four page reads. The cost is paid on every write: an INSERT adds an entry to every index on the table, an UPDATE to an indexed column moves its entry, and a DELETE removes one, so a table with eight indexes does nine writes per insert. Indexes also take disk and memory. The rule interviewers want to hear: index what you filter, join and sort on; do not index everything.

2. 2.Why can a table have only one clustered index?

   Because a clustered index is not beside the table — it is the table, stored in the index's key order. The leaf level of a clustered index holds the actual rows, and rows can only be physically arranged one way, so there can be only one. InnoDB clusters every table on its primary key; SQL Server clusters on the primary key by default. A non-clustered (secondary) index is a separate structure whose leaf entries hold the key plus a pointer to the row — the primary key value in InnoDB, a row locator in SQL Server — so a table can have many. That pointer is why a secondary-index lookup costs an extra step: find the key in the index, then fetch the row from the clustered index.

3. 3.When would a hash index beat a B-tree, and why are B-trees still the default?

   A hash index answers an equality lookup — WHERE email = ? — in O(1) with a single bucket read, and a B-tree needs O(log n) page reads for the same thing, so for pure equality on a huge table a hash index is faster. But a hash index cannot answer anything else: no range queries (BETWEEN, <, >), no prefix matches, no ORDER BY, no leftmost-prefix use of a composite key, because hashing destroys order. A B-tree keeps keys sorted, stays balanced under inserts and deletes, and has a fan-out of hundreds of keys per page, so a billion rows are three or four levels deep. That combination — nearly as fast for equality, and the only option for everything else — is why every major database defaults to B-trees; PostgreSQL offers hash indexes, and MySQL's MEMORY engine uses them, but they are the exception.

4. 4.What is the leftmost-prefix rule for a composite index?

   A composite index on (city, street, house_no) is sorted by city first, then by street within each city, then by house number within each street — like a phone book sorted by surname, then first name. Queries can use it only if they constrain a prefix of that column list from the left: city alone, city and street, or all three. A query on street alone cannot use it, because streets are scattered across every city, exactly as you cannot find everyone called Priya in a book sorted by surname. The consequences: column order in the index matters, put the columns you always filter on first, and a second index starting with street is a separate object, not something the first one gives you for free.

   CREATE INDEX idx_addr ON Addresses (city, street, house_no);
   
   -- uses the index
   SELECT * FROM Addresses WHERE city = 'Pune' AND street = 'MG Road';
   -- cannot use it: no leading city
   SELECT * FROM Addresses WHERE street = 'MG Road';

5. 5.What is a covering index, and how do you tell the database used one?

   An index that contains every column a query needs — the ones it filters on and the ones it returns — so the database answers the query from the index alone and never touches the table. With an index on (last_name, email), the query SELECT email FROM Users WHERE last_name = 'Rao' finds the entries by last name and reads email straight out of them; it skips the second step of fetching each row. The plan shows it: MySQL's EXPLAIN prints "Using index" in the Extra column, PostgreSQL shows an "Index Only Scan". Some databases let you append non-key columns just for coverage — INCLUDE in PostgreSQL and SQL Server — which keeps the index narrower than putting everything in the key.

6. 6.Why would the optimiser ignore an index that exists on the column?

   Usually for one of six reasons. The column is wrapped in a function or expression — WHERE YEAR(order_date) = 2024, or LOWER(email) — so the stored values are not what is being compared; rewrite as a range (order_date >= '2024-01-01' AND order_date < '2025-01-01') or create an expression index. A leading wildcard, LIKE '%son', which defeats the sorted order. An implicit type conversion, such as comparing a VARCHAR column to a number. Low selectivity, where the predicate matches so much of the table that a scan is cheaper than millions of index-then-row hops. A tiny table, where a scan is a single page. And stale statistics, which make the optimiser misjudge all of the above — ANALYZE fixes that one. Read the EXPLAIN plan before guessing.

7. 7.Does an index help ORDER BY, GROUP BY and JOINs?

   Yes, when the index order matches what the query needs. An ORDER BY on the leading index columns, in the same direction, lets the database read rows in order and skip the sort entirely — the difference between a pipelined result and a filesort of the whole table. GROUP BY on an indexed column can aggregate consecutive runs without a hash table. For joins, the index that matters is on the join column of the table being probed — typically the foreign key — because for every row on the driving side the database looks up matches on the other; without it each lookup is a scan. That is why foreign key columns are indexed automatically in MySQL and should be indexed by hand in PostgreSQL, which does not do it for you.

8. 8.What is index selectivity, and why is a boolean column a poor index?

   Selectivity is the fraction of rows a typical lookup returns: an index on a unique column returns one row per lookup (perfectly selective), while an index on is_active with two values returns about half the table per lookup. Walking an index to find half a million rows and then fetching each one from the table is slower than just scanning the table, so the optimiser correctly ignores the index — the index was never going to help. The exception is a skewed column where you always query the rare value: if 1% of orders are pending and you only ever ask for pending ones, a partial (filtered) index — CREATE INDEX ... WHERE status = 'pending' — is small and highly selective. Cardinality, the number of distinct values, is the number statistics keep to estimate this.

How the diagnostic asks it

One question from the DBMS bank, exactly as a sitting would show it. The bank has 6 on indexing and 60 across DBMS.