What is an index and how does it work on a physical level, what accelerates it?

An index in a database is a data structure that speeds up the search and sorting of records. At the physical level, an index is usually implemented as a balanced tree (e.g., B-tree) or a hash table.

The idea is that instead of sequentially scanning all rows of a table, the DBMS refers to the index, which contains sorted keys and references to the corresponding records. This allows for quick retrieval of data by key.

Speed is improved by:

• reducing the number of disk read operations (the index is more compact and organized for quick search);
• using structures with logarithmic search time (B-tree);
• enabling fast filtering and sorting of data without a full table scan.

For example, if there is an index on the "id" column, searching for a record with a specific id takes O(log n), rather than O(n).