Hard20 minDatabase Fundamentals
UpdatedAug 1, 2026
Edit

B-Tree Indexes & SARGability

Question Variations

  • "What is a B-Tree index, and how does it speed up database queries?"
  • "What does 'SARGable' mean, and can you give an example of a non-SARGable query?"
  • "Explain the importance of column order in a composite (multi-column) index."
  • "What is the difference between an 'index seek' and an 'index scan'?"

Why This Is Asked

Indexing is the most impactful database optimization skill. Interviewers want to know if you can explain how indexes work at a structural level, predict when a query will use an index, and identify common patterns that break index usage (non-SARGable queries).

Key Concepts

  • B-Tree is a balanced tree: root and internal nodes contain navigation keys, leaf nodes contain data or row pointers
  • Search, insert, and delete are all O(log n) — this is why indexes make reads fast
  • SARGable (Search ARGumentable): a query predicate that can leverage an index seek instead of a scan
  • Functions on columns (WHERE YEAR(date) = 2024), leading wildcards (LIKE '%foo'), and implicit type conversions break SARGability
  • Composite index key order matters: the “left-prefix rule” means (A, B, C) supports queries on A, A,B, or A,B,C — not B alone

Question Variations

  • “What is a B-Tree index, and how does it speed up database queries?”
  • “What does ‘SARGable’ mean, and can you give an example of a non-SARGable query?”
  • “Explain the importance of column order in a composite (multi-column) index.”
  • “What is the difference between an ‘index seek’ and an ‘index scan’?”

Answers by Technology

+ Add Variant

Expected Answer (PostgreSQL 16)

PostgreSQL B-Tree indexes are the default and support deduplication (since PG 13).

  • Index-Only Scans: Possible when using INCLUDE or if all columns are in the index.
  • Partial Indexes: Indexing only a subset of rows.

Why It Matters

Indexing is the primary tool for performance. PostgreSQL 16 improves vacuuming and index maintenance, reducing the “bloat” that naturally occurs in MVCC systems. Understanding how Postgres handles B-Trees is vital for scaling high-traffic databases.

SQL Example

-- Creating a B-Tree index
CREATE INDEX idx_user_email ON users(email);

-- Partial Index (Very efficient for status flags)
CREATE INDEX idx_active_users ON users(id) WHERE is_active = true;

-- Covering Index using INCLUDE
CREATE INDEX idx_orders_customer_covering ON orders(customer_id) INCLUDE (total_amount);

Common Mistakes

  • Index Bloat: Forgetting that every UPDATE in Postgres is a DELETE + INSERT.
  • Ignoring Deduplication: Not realizing that Postgres can significantly shrink index size for columns with many duplicate values.

Follow-up Questions

  • What are Partial Indexes? (Answer: Indexes with a WHERE clause).
  • Difference between B-Tree and GIN? (Answer: B-Tree is for scalar comparison; GIN is for composite data like JSONB).

Expected Answer (MySQL 8.4)

MySQL’s primary index structure is the B+Tree.

  • B+Tree vs B-Tree: MySQL uses B+Tree where data is only stored in leaf nodes, and leaf nodes are linked, making range scans very efficient.
  • Left-Prefix Rule: In a composite index (col1, col2), MySQL can only use the index if col1 is provided in the query.

Why It Matters

Understanding the B+Tree structure explains why ORDER BY and GROUP BY can often be satisfied by an index without a “filesort” in MySQL.

SQL Example

-- Composite index
CREATE INDEX idx_user_status ON users(status, last_login);

-- SARGable (Uses index)
SELECT * FROM users WHERE status = 'active' ORDER BY last_login;

-- NOT SARGable for filtering (Violates left-prefix)
SELECT * FROM users WHERE last_login > '2024-01-01';

Common Mistakes

  • Incorrect Column Order: Putting high-cardinality columns at the end of a composite index when they are frequently used for filtering.
  • Over-indexing: Creating too many indexes which slows down INSERT performance.

Follow-up Questions

  • What is a Covering Index? (Answer: An index that contains all columns needed for the query).
  • What is a Prefix Index? (Answer: Indexing only the first N characters of a string column).

Expected Answer (SQL Server 2022)

SQL Server B-Trees are used for both clustered and non-clustered indexes.

  • Included Columns: Creating covering indexes without increasing tree size.
  • Filtered Indexes: Indexing a subset of data using a WHERE clause.

Why It Matters

B-Tree indexes are the backbone of SQL Server performance. SQL Server 2022’s Intelligent Query Processing features rely on accurate index statistics to choose the best execution path.

SQL Example

-- Standard Non-Clustered Index
CREATE INDEX IX_Email ON Users(Email);

-- Covering Index with Included Columns
CREATE INDEX IX_OrderDate_Total ON Orders(OrderDate) INCLUDE(TotalAmount, CustomerID);

-- Filtered Index
CREATE INDEX IX_IncompleteOrders ON Orders(OrderID) WHERE Status = 'Pending';

Common Mistakes

  • Over-indexing: Each index slows down INSERT/UPDATE/DELETE.
  • Key Order: Forgetting that the order of columns in a composite index must match the query’s filter order.

Follow-up Questions

  • What is a Covering Index? (Answer: An index containing all columns needed for a query).
  • What are statistics? (Answer: Data about the distribution of values in an index).

Expected Answer (MongoDB 7.0/8.0)

MongoDB uses B-Tree indexes for standard queries.

  • Multikey Indexes: Indexing an array field creates entries for every element.
  • Compound Indexes: Supports sorting and filtering on multiple fields (ESR Rule: Equality, Sort, Range).
  • Text Indexes: For string searches.

Why It Matters

Indexes are critical in MongoDB to avoid “Collection Scans” which are extremely slow. B-Trees allow for efficient filtering and sorting, and features like TTL indexes allow for automatic data cleanup.

Example

// Compound Index following ESR rule
db.users.createIndex({ status: 1, last_login: -1, age: 1 });

Common Mistakes

  • Incorrect ESR Order: Putting the range filter before the sort field in a compound index.
  • Index Bloat: Creating too many multikey indexes on large arrays.

Follow-up Questions

  • What is an Index-Only scan? (Answer: When the index contains all data needed, skipping the document fetch).
  • What is a Partial Index? (Answer: Indexing only documents that match a filter).