What is a database index and why is it used?

An index is a data structure that improves the speed of data retrieval operations on a table by providing quick access paths to rows. Like a book index, it maps column values to row locations. Without indexes, queries perform full table scans (O(n)). Indexes enable O(log n) lookups using B-trees. Trade-off: indexes speed up reads but slow down writes and use additional storage. Index columns used in WHERE, JOIN, and ORDER BY clauses.