Database Indexing and Query Performance: How Indexes Make Searching Large Tables Scalable

Abstract

ABSTRACT Databases hold the data on which most information systems depend, and a common operation is to find particular records among many, but searching a large table by examining every record is slow, and becomes slower in proportion as the table grows, so that on a very large table such a search is impractical; an index makes this search fast by providing an ordered structure that locates records without scanning them all. This study examines database indexing and query performance and how an index makes searching a large table scalable. The time to find a record was examined as the size of the table grew, with and without an index, so that the difference between scanning every record and using an index, and how each scaled with the size of the table, could be seen. Without an index the search time grew in direct proportion to the size of the table, since every record had to be examined, so a table ten times larger took ten times as long to search, and a very large table took impractically long; with an index the search time grew only very slowly, far more slowly than the table, because the index located the record through an ordered structure in a number of steps that rose only logarithmically with the size of the table, so that even a very large table could be searched almost as quickly as a small one. The difference therefore widened enormously as the table grew, the indexed search remaining fast where the unindexed search became unusable. This is why indexes are essential to database performance, making searches that would otherwise be impractical on large tables fast and scalable. The study shows that indexing changes search time from growing in proportion to the table to growing only logarithmically, and it discusses the implications, and the costs, of indexing in information systems.

KEYWORDS: Database indexing, Query performance, B-tree, Search, Scalability, Relational database, Full table scan, Logarithmic search, Information systems