What is indexing in the context of databases or collections?

Indexing is a performance optimization technique for data retrieval.

In databases, an index is a structure (such as a B-tree) that allows for quick lookup of rows in a table without scanning the entire table. It is created on one or more columns.

In collections (for example, ArrayList in Java), indexing is essentially built-in. Elements are stored in an ordered sequence, and access to any element by index (its position number) is performed in O(1) time.

Main goals of indexing:

• Speeding up query execution: Especially for SELECT operations with WHERE and JOIN conditions.
• Ensuring uniqueness: Unique indexes guarantee that values in the indexed column or combination of columns are unique.
• Supporting sorting: Indexes can be used for quick sorting of results (ORDER BY).

Examples of usage in SQL:

-- Creating an index on the price column
CREATE INDEX idx_products_price ON products (price);

-- Creating a composite index on customer_id and order_date columns
CREATE INDEX idx_orders_customer_date ON orders (customer_id, order_date);

In collections, access by index:

// Getting an element by index
List<String> names = new ArrayList<>();
names.add("Alice");
names.add("Bob");
String firstElement = names.get(0); // Access by index 0

Disadvantages of indexing:

• They occupy additional disk space.
• Data modification operations (INSERT, UPDATE, DELETE) become slower because the index must also be updated.
• They are not always used by the query optimizer (for example, during full table scans).