Database indexing is a technique used to improve the speed of data retrieval operations on a database table. It involves creating a data structure, called an index, that allows the database management system (DBMS) to quickly locate and access the data without having to scan every row in a table. Here’s a detailed explanation of how database indexing works:
What is a Database Index?
A database index is a data structure that stores a sorted list of values from one or more columns of a table, along with pointers to the corresponding rows in the table. This allows the DBMS to quickly locate the rows that match a given search condition.
Types of Indexes
Primary Index: Created on the primary key of a table, ensuring that each value is unique and sorted.
Secondary Index: Created on non-primary key columns to speed up queries that use those columns.
Clustered Index: Reorders the physical storage of the table's data to match the index, meaning the table is stored in the order of the index.
Non-clustered Index: Does not alter the physical order of the table but creates a separate object within the table that points back to the original table rows.
Composite Index: An index on multiple columns of a table.
Unique Index: Ensures that the indexed column(s) do not have duplicate values.
How Indexing Works
Data Structures Used
B-Tree: The most common data structure used for indexing. It is a balanced tree that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. Each node in a B-tree contains multiple keys and pointers to child nodes, facilitating efficient range queries and ordered traversals[3][17].
Hash Table: Used for equality searches. It maps keys to values using a hash function, allowing for very fast lookups. However, it is not suitable for range queries[19].
Bitmap Index: Efficient for columns with a low number of distinct values, such as boolean fields. It uses bitmaps to represent the presence of values[6].
Index Creation
When an index is created on a column, the DBMS generates a separate data structure that contains the indexed column values and pointers to the corresponding rows in the table. For example, creating an index on the email column of a users table would result in a sorted list of email addresses, each pointing to the row where that email is stored.
Query Optimization
When a query is executed, the DBMS checks if there is an index that can be used to speed up the search. If an index is available, the DBMS uses it to quickly locate the rows that match the query conditions. For instance, a query searching for a specific email address can use the index to directly access the row, bypassing the need to scan the entire table[1][2][5].
