Server
Database index
Database index is a sorted lookup structure on one or more columns that lets the database find matching rows without reading the whole table. It makes reads cheaper and writes a little dearer.
How it is measured
Verify an index is used with the query plan: look for an index scan or seek rather than a full table scan, and compare rows examined to rows returned. In MySQL, EXPLAIN's 'rows' and 'key' columns tell you; in Postgres, EXPLAIN ANALYZE shows actual time.
Also check what it costs: index size on disk, and the extra work on each INSERT and UPDATE. The useful ratio is rows examined divided by rows returned, and it should be near 1 for a lookup.
Worked example
A WordPress site with 1.2 million rows in wp_postmeta runs a query filtering on meta_key and meta_value for a product filter. Without a useful index it examines all 1.2 million rows and takes 2.9 seconds.
Adding a composite index on (meta_key, meta_value(40)) drops the examined rows to about 600 and the query to 11 ms. Writes to postmeta become around 8 percent slower, which nobody noticed.
How it differs
A database index is the structure that makes a lookup cheap. A query plan is the database's description of how it will run a statement, including whether it uses that index. The index excludes any promise it will be chosen. The plan excludes the data structure itself, and only the plan tells you if the index helped.
Common errors
Indexing every column and slowing every write. Putting columns in the wrong order in a composite index. Wrapping an indexed column in a function so the index is ignored. Forgetting that low-cardinality columns rarely benefit. Never dropping unused indexes. Assuming it is used without reading the plan.
In practice
Pick your five slowest queries from the slow log, run EXPLAIN on each, and add an index only where a scan shows up. Remove indexes that have had zero reads over a month, since each one taxes every write.