What is an index in terms of memory storage? How does it interact with the table?

A database index is a special data structure that speeds up search and sorting by table columns.

In terms of in-memory storage, an index is usually implemented as a tree (e.g., B-tree or B+-tree) or a hash table. The tree stores keys (values of indexed columns) and pointers to the corresponding records in the table.

Interaction with the table:

• When creating an index, the DBMS builds a structure that maps key values to physical addresses or identifiers of rows in the table.
• When executing a query with a condition on an indexed column, the DBMS accesses the index, quickly finds the needed keys, and retrieves the corresponding records in the table.
• An index allows avoiding a full table scan, significantly speeding up query operations.

Thus, an index is an additional structure that stores ordered keys and references to data, providing quick access to table rows based on column values.