How does an index speed up query execution in a database?

An index creates an ordered data structure (e.g., B-tree or hash table) associated with one or more columns of a table. When a query with conditions on indexed columns is executed, the DBMS uses this index for quick row retrieval without scanning the entire table.

Main acceleration mechanisms:

• Fast search: Instead of scanning all table rows, the DBMS quickly finds the needed data by navigating through the nodes of the index structure.
• Reducing disk operations: Only the disk pages containing the index and necessary data are read, not the entire table.
• Data sorting: Indexes can store data in sorted order, speeding up ORDER BY queries.
• Accelerating JOIN operations: Indexes on JOIN keys allow quick matching of corresponding rows in another table.

Pseudo-code example (analogy with searching in a book):

// Without index: viewing each page of the book to find a word
// With index (alphabetical pointer): searching for the word in the index, jumping to the page number