1 Fundamentals

1.1 Definition and purpose

An index is a supporting data structure that makes it faster to locate records, documents, or values without scanning an entire collection. In databases, it typically maps one or more search keys to the physical or logical position of the corresponding data. In broader information systems, the same idea appears in search tools, file systems, and programming languages, where a compact reference improves access speed.

The main purpose of an index is efficiency. Instead of examining every item, a system can consult the index to narrow the search to a small set of candidates. This can greatly reduce response time for queries, lookups, and sorting operations.

1.2 How indexes work

Most indexes organize entries by key value and store pointers, references, or row identifiers that lead to the underlying data. When a request matches an indexed field, the system consults the index structure first and then retrieves the associated records. This two-step process is usually much faster than a full scan when the indexed values are selective.

An index may also support ordering. Because many index structures store keys in sorted form, they can speed up range queries, minimum and maximum searches, and ordered retrieval. Some indexes are designed for exact match searches, while others are better suited to prefix, text, spatial, or multi-column queries.

1.3 Benefits and trade-offs

Indexes improve read performance, but they are not free. They require extra storage and must be updated whenever the underlying data changes. For this reason, database administrators and developers often balance query speed against the cost of maintenance and space usage.

1.3.1 Faster lookups

The most visible advantage of an index is rapid retrieval. Queries that would otherwise scan large tables can often jump directly to relevant rows. This is especially useful for frequently searched columns, join keys, and columns used in sorting or filtering.

1.3.2 Storage overhead

Because an index duplicates key values and adds structural information, it consumes additional space. Large tables with many indexes may require substantial storage, and the index itself can become a notable part of the database footprint. In memory-sensitive systems, this overhead may also affect cache behavior.

1.3.3 Write performance impact

Whenever data is inserted, updated, or deleted, related indexes must also change. This can slow write operations, especially when a table has many indexes or when index keys are wide or highly volatile. In heavily updated systems, too many indexes can reduce overall throughput.

2 Types of indexes

2.1 Single-field indexes

A single-field index is built on one column or one attribute. It is useful when queries commonly filter on that field alone. Such an index is simple to design and often effective for equality searches, range conditions, and sorting by that field.

2.2 Composite indexes

A composite index combines multiple columns into one structure. It is helpful when queries frequently use the same set of fields together, such as a surname and given name or a category and date pair. The combined key allows the system to find rows more efficiently than by using separate indexes in many cases.

2.2.1 Column order

The order of columns in a composite index matters. The leading column usually has the greatest influence on whether the index can be used effectively. Queries that match the leftmost portion of the index are often the best candidates for index usage, while queries that ignore the leading column may benefit less.

2.2.2 Prefix matching

Prefix matching allows a query to use the initial columns of a composite index even if later columns are not specified. This makes composite indexes flexible, but only to a point. The more of the leading sequence a query can use, the more efficient the access path tends to be.

2.3 Unique indexes

A unique index prevents duplicate values in the indexed field or field combination. It is commonly used to enforce constraints such as usernames, email addresses, or other identifiers that must not repeat. Besides supporting fast lookup, it also helps maintain data integrity.

2.4 Full-text indexes

Full-text indexes are designed for searching words and phrases within large bodies of text. Rather than matching exact values only, they often break content into terms and support linguistic searching. They are widely used in document management systems, content platforms, and search-oriented databases.

2.5 Clustered indexes

A clustered index determines the physical or logical order of data rows in relation to the indexed key. Because the data itself follows the index order, range queries and ordered retrieval can be efficient. However, changing the clustered key can be costly because it may require moving rows.

2.6 Non-clustered indexes

A non-clustered index is separate from the table data and contains key values plus references to the underlying rows. Multiple non-clustered indexes can exist on the same table, each supporting different query patterns. They are versatile, though they add maintenance overhead.

2.7 Hash indexes

Hash indexes use a hash function to map keys to buckets. They are often very fast for exact-match searches because the hash value directly identifies the likely location of the data. They are less effective for ordered retrieval or range queries, since hash order does not preserve key order.

2.8 Bitmap indexes

Bitmap indexes represent values using compact bit arrays. They can be efficient for columns with relatively few distinct values, such as yes-or-no attributes or status fields. Their structure makes them useful in analytical workloads where multiple conditions are combined.

2.9 Spatial indexes

Spatial indexes support geographic and geometric data, such as points, lines, and polygons. They help systems answer proximity, containment, and overlap queries more quickly than a brute-force scan. These indexes are commonly used in mapping, routing, and location-based applications.

2.10 Partial and filtered indexes

Partial or filtered indexes cover only the subset of rows that meet a specified condition. This reduces index size and can improve efficiency when queries target a common subset of data. They are useful when only some records are frequently searched, such as active entries or recent events.

3 Database indexing

3.1 Relational database indexes

In relational database systems, indexes are central to query performance. They support selection, joins, ordering, and constraint enforcement. Good indexing can make a large database responsive, while poor indexing can leave even a well-designed schema sluggish.

3.1.1 Primary key indexes

Primary key indexes support the main identifier of a table. Because primary keys must be unique, the index also helps guarantee that no two rows share the same key. In many systems, the primary key is automatically indexed.

3.1.2 Foreign key indexes

Foreign key indexes improve joins and relationship checks between tables. They can speed up queries that connect child records to parent records and may reduce the cost of referential integrity operations. In practice, they are often created on columns that are used repeatedly in join conditions.

3.2 Index creation and maintenance

Indexes must be created, updated, and occasionally repaired or reorganized. These tasks may happen automatically in some systems, while in others they are managed explicitly by administrators. Maintenance keeps indexes useful as data changes over time.

3.2.1 Index building

Index building is the process of creating a new index from existing data. This may be done online, with limited disruption, or offline, with greater impact on availability. Large tables can take significant time to index because each row must be examined and placed into the structure.

3.2.2 Rebuilding and reorganization

Rebuilding recreates an index from scratch, often removing fragmentation and restoring efficiency. Reorganization is typically a lighter operation that tidies the existing structure without full reconstruction. The choice between them depends on how much the index has degraded and how much downtime is acceptable.

3.3 Query optimization

Database optimizers consider indexes when deciding how to execute a query. They compare available access paths and estimate which one will cost the least. A suitable index can change a slow query into a fast one, especially for selective filters and joins.

3.3.1 Execution plans

An execution plan describes how the database will run a query. It may show whether the system uses an index seek, an index scan, or a full table scan. Reading execution plans helps identify whether an index is being used effectively or whether the optimizer prefers another path.

3.3.2 Selectivity and cardinality

Selectivity refers to how well a column narrows down the data set, while cardinality describes the number of distinct values in that column. High-selectivity columns often make better indexes because they eliminate many rows quickly. Low-cardinality fields may still be useful in combination with other columns or in specialized index types.

3.4 Index tuning

Index tuning is the process of refining indexes to match query behavior. It involves identifying the most common workloads, measuring performance, and adjusting the index set accordingly. Proper tuning usually improves both speed and resource efficiency.

3.4.1 Choosing indexed columns

The best candidates for indexing are typically columns used in filters, joins, sorting, and frequent lookups. Columns with stable values and strong selectivity often offer the highest benefit. The overall workload should guide design, rather than indexing every available field.

3.4.2 Avoiding over-indexing

Too many indexes can slow writes, consume storage, and complicate maintenance. Redundant or rarely used indexes add cost without much benefit. A leaner set of well-chosen indexes is often preferable to a large collection of overlapping ones.

4 Index data structures

4.1 B-trees and B+ trees

B-trees and B+ trees are among the most widely used index structures in databases. They keep keys sorted and maintain balanced depth, which provides consistent search performance. Their design supports both exact lookups and range queries efficiently.

4.2 Hash tables

Hash tables underpin many fast exact-match indexes and associative structures. By applying a hash function, they distribute keys across buckets for quick access. They are excellent for equality searches but do not naturally preserve ordering.

4.3 Inverted indexes

An inverted index maps terms to the documents or records that contain them. This structure is fundamental to text search because it reverses the usual relationship between document and content. Instead of asking where a term appears, the system can immediately list matching sources.

4.4 Trie-based indexes

Trie-based indexes organize keys by shared prefixes. They are useful for autocomplete, prefix search, and hierarchical keys. Because common beginnings are stored once, tries can be efficient for string-oriented workloads.

4.5 Skip lists

Skip lists use layered linked structures to speed up traversal. By allowing jumps over sections of data, they offer search performance comparable to balanced tree structures in many settings. They are valued for conceptual simplicity and efficient updates.

5 Indexes in information retrieval

5.1 Search engine indexing

Search engines rely on indexes to transform large collections of web pages or documents into searchable resources. The index lets the system respond to queries rapidly rather than analyzing every source from scratch. This process is essential to large-scale retrieval.

5.1.1 Crawling and parsing

Crawling is the process of gathering documents, while parsing extracts the meaningful content from them. Search systems then analyze the structure, links, and text to prepare the material for indexing. Without accurate parsing, the resulting index may miss important information.

5.1.2 Tokenization and normalization

Tokenization breaks text into units such as words or phrases, and normalization makes those units consistent for indexing. This may involve lowercasing, removing punctuation, or applying stemming and lemmatization. These steps help the search system match related forms of the same term.

5.2 Inverted file structures

Inverted file structures are storage systems built around term-to-document mappings. They often include postings lists, which record where each term appears. This organization supports rapid query processing across very large text collections.

5.3 Ranking and retrieval

Retrieval systems do not merely find matches; they also rank them. An index provides the candidate set, and ranking methods decide which results are most relevant. This combination makes search both fast and useful.

5.3.1 Term frequency

Term frequency measures how often a term appears within a document. Higher frequency can suggest greater topical relevance, though it is usually combined with other factors. It is one of several signals used in ranking models.

5.3.2 Relevance scoring

Relevance scoring assigns a value to each result based on how well it matches the query. The score may reflect term frequency, rarity, field weight, phrase matching, and other features. The ranking process then orders results from most to least relevant.

6 Indexes in file systems

6.1 Directory indexing

File systems use indexing to organize directory entries so names can be found quickly. This is important when folders contain many files or deeply nested structures. Efficient directory indexing reduces delay during file opening and listing.

6.2 File allocation and lookup

File lookup depends on structures that map file names or identifiers to storage locations. These mappings help the system locate file blocks, track allocation, and retrieve content efficiently. Without such indexing, access would be much slower on large volumes.

6.3 Metadata indexing

Metadata indexes organize attributes such as file size, timestamps, ownership, and type. They are useful for searches based on properties rather than file content. Operating systems and storage platforms often use them to support quick filtering and discovery.

7 Indexes in programming

7.1 Array and list indexing

In programming, indexing often refers to selecting an element by position in an array or list. This form of indexing is direct and usually very fast. It depends on the structure’s ability to calculate the location of an element from its index number.

7.2 Indexed data access

Indexed access means retrieving data through a stable position, key, or label rather than by sequential traversal. It appears in many language features and libraries. The approach improves convenience and can make algorithms more efficient.

7.3 Associative arrays and maps

Associative arrays and maps store pairs of keys and values. A key is used to retrieve the associated value quickly, which makes these structures a programming analogue of database indexing. They are common in configuration handling, caching, and lookup tasks.

7.3.1 Keys and values

The key identifies the entry, while the value holds the related data. Good key design matters because it affects uniqueness, retrieval speed, and readability. In many languages, keys may be strings, numbers, or more complex objects.

7.3.2 Lookup complexity

Lookup complexity describes how the time required to find a value grows with the size of the structure. Some indexed containers offer near-constant-time access on average, while others may scale logarithmically. The actual behavior depends on the implementation and workload.

8 Index maintenance and performance

8.1 Insert, update, and delete costs

Each data modification can trigger corresponding index changes. Inserts add new entries, updates may alter existing keys, and deletes remove references. The more indexes a table has, the more work each modification can require.

8.2 Fragmentation and page splits

As indexes change, their internal pages may become less compact or less orderly. Fragmentation can reduce performance by increasing the number of reads needed to follow the structure. Page splits occur when a page is full and must be divided, often creating extra overhead.

8.3 Monitoring index usage

Monitoring helps determine which indexes are helpful and which are rarely used. Usage statistics, query logs, and execution plans can reveal whether a particular index supports important workloads. This information guides pruning, redesign, and maintenance decisions.

8.4 Common anti-patterns

Common mistakes include indexing too many columns, creating duplicate or nearly identical indexes, and ignoring query patterns when designing structures. Another problem is keeping indexes that no longer match the workload. Careful review can prevent wasted space and unnecessary slowdown.

9.1 Catalogs and tables of contents

Catalogs and tables of contents are organized reference tools that help users find information quickly. They resemble indexes in that they point to relevant items rather than containing all content in one place. The similarity is strongest in books, archives, and document systems.

9.2 Lookup tables

Lookup tables store reference values that other data can consult. They often standardize categories, codes, or labels. Although simpler than many indexes, they serve a related role by making retrieval more structured and efficient.

9.3 Access paths

Access paths are the routes a system can take to reach data. An index is one of the most important access paths in database design. Choosing the right path can greatly influence query speed and overall system performance.