How does database indexing improve performance?

Database indexing improves performance by creating a data structure, typically a B-tree or hash based structure, that allows the database engine to locate rows quickly without scanning the entire table.

Without an index, queries often require full table scans, which are O(n). With a proper index, lookups can be reduced to O(log n) or even O(1) depending on the index type.

However, indexes come with trade offs. They consume additional storage and can slow down write operations because the index must be updated whenever the data changes. Therefore, indexes should be added selectively based on query patterns.