"Index" sounds like one thing. It isn't — it's a family of structures, each one solving a narrower version of "find rows fast," and picking the wrong member of that family is as common a mistake as not indexing at all. This is the map: what each type actually trades away to be fast, and the two mechanical reasons an index you did create can still get ignored.
The default: B-tree
Unless told otherwise, every major relational database builds a B-tree (technically a B+ tree) when you run CREATE INDEX — sorted, balanced, and the only type that supports range queries and ORDER BY as well as equality. See Understanding B-Trees for the actual mechanism, and SQL Index Advisor for how column order in a composite B-tree index should follow from your actual WHERE/ORDER BY clauses. Everything below is about the cases where a plain B-tree isn't the right tool, or needs a variant.
Hash indexes: faster equality, at the cost of everything else
A hash index is exactly a hash table built as a database index — average O(1) equality lookups instead of a B-tree's O(log n). The trade is the same one that post covers: a hash function deliberately destroys ordering to spread keys evenly, so a hash index can answer WHERE id = 42 but is structurally useless for WHERE id > 42 or ORDER BY id — there's no sorted structure left to walk. PostgreSQL supports them explicitly (CREATE INDEX ... USING hash); worth knowing if you're reading older material — before PostgreSQL 10, hash indexes weren't crash-safe (not write-ahead-logged), which earned them a reputation for years afterward that the current implementation no longer deserves. MySQL's InnoDB, by contrast, never exposes a hash index you can explicitly create — it only uses one internally and automatically (the "adaptive hash index") as a cache in front of its own B+ tree, not a user-facing index type.
Unique indexes: the constraint and the index are the same structure
A PRIMARY KEY or UNIQUE constraint isn't enforced by some separate mechanism that also happens to have an index nearby — declaring one creates a real index (a B-tree, by default), and enforcement is a side effect of that index rejecting a duplicate key on insert. Every table with a primary key already has at least one index, whether or not anyone explicitly asked for it.
Covering indexes: skipping the table entirely
A composite index — multiple columns in one index, ordered by the equality-then-range logic SQL Index Advisor generates — speeds up filtering and sorting. A covering index is a related but distinct idea: if every column a query needs (filtered, sorted, and selected) is present in the index itself, the database can answer the query directly from the index and never touch the actual table row at all — an index-only scan. PostgreSQL's INCLUDE clause makes this explicit: columns listed there ride along in the index purely to make it covering, without affecting the sort order the key columns still define. The win is real and specific — one structure to read instead of two — not just a faster version of a normal index lookup.
Partial indexes: indexing only the rows that matter
An index doesn't have to cover the whole table. A partial index — CREATE INDEX ... ON orders (customer_id) WHERE status = 'pending' — only indexes rows matching that condition. Smaller than a full index on the same column (less disk, less write overhead per insert — see Database Index Cost Estimator for putting a number on that overhead), at the cost of only being usable by a query whose WHERE clause matches or implies the same condition. The classic case: indexing only WHERE deleted_at IS NULL on a table that soft-deletes — the (often much larger) history of deleted rows never bloats the index at all.
The two mechanical reasons an index gets ignored
Low selectivity. Every index match still costs a heap fetch — a second read back to the actual table row, since a standard index (not a covering one) doesn't hold the full row. For a highly selective condition matching a handful of rows, a handful of heap fetches easily beats scanning the whole table. For a condition matching a large fraction of it — a boolean column that's 95% true, say — the accumulated cost of one heap fetch per match can exceed the cost of one sequential scan reading everything in order. This is a mechanical property of the index itself, not a planner mistake; see How Query Optimization Works for exactly how the planner estimates that fraction from real table statistics before deciding which way to go.
Wrapping the column in a function. WHERE LOWER(email) = 'a@b.com' can't use a plain index on email, because the index is sorted by the raw column values, not by what a function would return when applied to them — the sort order the lookup needs simply isn't the one that exists. The fix, where it's available, is an expression index — an index built on LOWER(email) directly instead of on email — which is a real, separate index the planner can only use for a query that applies that exact same expression.
Try it yourself
SQL Index Advisor reads a real query and suggests a composite index and column order. Database Index Cost Estimator puts a number on whether a new index's read savings are worth its write overhead. SQL Explain Helper reads a real execution plan and confirms whether the planner actually used the index at all.
FAQ
Does adding an index always speed up a query?
No, for either of the two mechanical reasons above, or because the read savings genuinely don't outweigh the write cost of maintaining it — see Database Index Cost Estimator for making that trade-off concrete instead of assumed.
What's the actual difference between a composite index and a covering index?
A composite index adds columns to filter or sort by — each one narrows what the index has to scan. A covering index adds columns purely so the query never has to leave the index to fetch them — those columns might not appear in WHERE or ORDER BY at all, only in SELECT. An index can be both at once: a composite index on the filter/sort columns, with additional covering columns tacked on (via INCLUDE in PostgreSQL) purely to make it index-only.
Is a primary key always a B-tree?
By default across PostgreSQL, MySQL (InnoDB), and SQL Server, yes — a declared primary key creates a standard B-tree index unless something more specific was explicitly requested.