How Can Database Indexing Significantly Improve Query Performance?

The importance of database indexes in data management

In the field of data management, indexes play a vital role in optimizing database performance, especially as the size of the data set continues to grow. This article delves into the basics of database indexing to provide a comprehensive explanation that is independent of your specific database platform.

Why indexes are important

Data stored on disk-based storage devices is organized into data blocks. Each block contains a portion of the actual data and a pointer to the subsequent block. Unlike linked lists, disk blocks do not need to be stored contiguously.

When searching for records based on non-sorted fields, a linear search is required, requiring (N 1)/2 block accesses on average. For non-key fields (missing unique entries), the entire tablespace must be scanned, requiring N block accesses.

In contrast, sorted fields allow binary searches, which require only log2 N block accesses. Additionally, for non-key fields, the search can be terminated once a higher value is encountered, thus reducing the number of block accesses required.

What is a database index?

Indexing is a technique for sorting records in a table based on multiple fields. Creates an index for a specific field that contains the field value and a pointer to the corresponding record. This index structure is then sorted for binary search.

However, indexes introduce additional disk space overhead because they store a separate table containing field values ​​and record pointers. This space requirement becomes important when indexing multiple fields in a table, especially when using the MyISAM engine where the index file may exceed file system limits.

How indexes work

Let's consider a sample database schema where a table contains five fields: id (primary key), firstName, lastName, and emailAddress. We assume there are 5 million rows with a fixed size of 204 bytes per row and a block size of 1024 bytes.

Scenario 1: Sorted fields and unsorted fields

• Without an index, a linear search on the id field (which is sorted and is the key field) requires approximately 500,000 block accesses.
• With an index, a binary search on the id field reduces the number of block accesses to about 20.
• For the firstName field (unsorted and non-key field), linear search requires 1,000,000 block accesses.

Scene 2: Index

• The index on the firstName field creates a smaller table with a record size of 54 bytes.
• The index table requires approximately 277,778 blocks, while the original table requires 1,000,000 blocks.
• A binary search of the index requires 19 block accesses, and then another 1 block access is required to retrieve the actual record, for a total of 20 block accesses.

When to use indexes

Indexes can improve query performance on fields that are frequently used in search criteria. However, it is important to consider the following when determining whether to index a field:

• Avoid indexing on output-only fields.
• Make sure the indexed field has high cardinality, as low cardinality may negate the effectiveness of the index.
• Consider the file system size limitations that may arise from over-indexing.

The above is the detailed content of How Can Database Indexing Significantly Improve Query Performance?. For more information, please follow other related articles on the PHP Chinese website!