Overview

Indexing is a data structure technique used to quickly locate data without having to search every row in a database table. An index is like a table of contents for a database, storing a sorted version of a column’s values and a pointer to the original row.

Core Concepts

• B-Trees (Balanced Trees): The most common index type. They keep data sorted and allow search, sequential access, insertions, and deletions in $O(\log n)$.
• Hash Indexes: Use a hash table to find values. Extremely fast $O(1)$ for equality checks (=), but useless for range queries (>, <).
• Clustered Index:
  • Defines the physical order of data in the table.
  • Only one clustered index per table (usually the Primary Key).
  • The leaf nodes contain the actual data rows.
• Non-Clustered Index:
  • A separate structure from the data table.
  • The leaf nodes contain pointers (row IDs) to the data.
  • Multiple non-clustered indexes can exist per table.
• Composite Index: An index on multiple columns. The order of columns in the index is critical for its effectiveness.

Code Examples

-- Create a non-clustered index on email
CREATE INDEX idx_user_email ON Users(Email);

-- Create a composite index on last_name and first_name
CREATE INDEX idx_user_name ON Users(LastName, FirstName);

Use Cases

• Read-Heavy Workloads: Speeding up SELECT queries on large tables.
• Filtering: Optimizing WHERE clauses.
• Sorting: Optimizing ORDER BY clauses.

Gotchas

• Write Penalty: Every time a row is inserted, updated, or deleted, the index must also be updated. This slows down INSERT, UPDATE, and DELETE operations.
• Index Bloat: Having too many indexes consumes excessive disk space.
• Unused Indexes: Indexes that are never used by the query optimizer but still slow down writes.

Related Notes

• Relational Databases
• NoSQL Databases
• Transactions & Concurrency Control