Index in Relational Databases

An index is a database object used to improve the speed of data retrieval from a table.
It provides an efficient access path to rows based on the values of one or more columns.

Conceptually, an index works similarly to the index in a book: instead of scanning the entire table, the database engine can quickly locate the required rows using indexed values.

SQL Standard Perspective

The SQL Standard (ISO/IEC 9075) primarily defines the logical structure of data such as tables, views, and constraints.
It does not define the internal structure or implementation of indexes.

Indexes are therefore considered implementation-specific optimization objects, and their design is left to each database system.

General Syntax

Most relational databases support similar syntax:

CREATE INDEX index_name

ON table_name (column1, column2, ...);

This creates an index on one or more columns of a table.

Conceptual Structure

An index typically stores:

·      key values from indexed columns

·      references (pointers) to table rows

When a query filters or searches using indexed columns, the database engine can use the index to locate matching rows without scanning the entire table.

B-Tree and B+Tree Index Structures

Most relational databases implement their default indexes using B+Tree structures, which are a variation of B-Trees.

B-Tree

In a B-Tree:

·      keys and row references can appear in both internal nodes and leaf nodes

·      data may be found at multiple levels of the tree

·      leaf nodes are not necessarily linked sequentially

B+Tree

In a B+Tree:

·      internal nodes store only keys

·      all row references are stored in leaf nodes

·      leaf nodes are linked sequentially

Because of the linked leaf nodes, B+Trees are very efficient for range queries and ordered scans, which are common in SQL workloads.
For this reason, most modern relational databases use B+Tree indexes as their default index type.

Specialized Index Structures

Although B+Tree indexes are the most common, databases also provide specialized index types designed for specific workloads.

These specialized indexes do not use B+Tree structures and may rely on other data structures such as:

·      hash tables

·      bitmap structures

·      inverted indexes

·      spatial trees

·      block-range summaries

·      column-oriented storage

These indexes are typically used for cases such as:

·      text search

·      spatial data

·      analytical workloads

·      very large tables

·      equality-based lookups

Summary

An index is a database structure that improves data retrieval performance by providing an efficient path to locate rows.
While the SQL standard does not define how indexes are implemented, most relational databases use B+Tree indexes as the default structure, while also supporting specialized non-B+Tree indexes for particular use cases.