Database Indexing
Database indexing creates auxiliary data structures that speed up query lookups without scanning every row. Understanding index types, their storage trade-offs, and how the query planner uses them is essential to database performance tuning.
itDatabases and data storage | OpenSkills.info
Intro
Database Indexing
A database index is a separate data structure that gives the query planner another way to find rows. Without a useful index, the database may inspect every row in a table. With one, it can navigate to a smaller set of candidates.
Think of an index as an ordered map from selected values to row locations. The map helps only when its structure matches the question. It also occupies space and must change when indexed data changes.
Why indexes exist
Tables are optimized to store complete rows. Queries often need a narrow slice of those rows:
- one account by email address;
- recent orders for one customer;
- rows joined through a key;
- the first ten events in a requested order;
- values that must remain unique.
An index can reduce the work needed for those access patterns. It can support filtering, joins, ordering, and uniqueness enforcement. It does not make every query fast.
The query planner chooses an execution plan from the available access paths. An index is an option, not an instruction. The planner may prefer a table scan when a condition matches much of the table or when the estimated index work costs more.
The B-tree mental model
A B-tree is the default and most common index type in many relational databases. It keeps keys in order and supports equality, range, and ordered retrieval.
Imagine an index on orders.created_at. The database navigates through upper levels of the tree to a leaf range containing the requested dates. Leaf entries identify candidate rows. The database may then fetch full rows from the table.
Continue the course
This section is part of the paid course.
See pricing to subscribe, or log in if you already have access.
Where this skill leads
Relevant careers
See how this topic contributes to broader role-level skill maps.
Sources
- https://www.postgresql.org/docs/current/indexes-intro.html
Supports
- Indexes can avoid scanning every row for suitable predicates and joins
- The planner may choose an index or a sequential scan based on estimated efficiency
- Indexes consume storage and add data-modification overhead
- Statistics collected by ANALYZE help the planner choose access paths
- https://www.postgresql.org/docs/current/indexes-types.html
Supports
- PostgreSQL provides B-tree, hash, GiST, SP-GiST, GIN, and BRIN index types
- B-tree indexes support equality, range, and ordered retrieval over sortable values
- Other index types serve different operators and data structures
- https://www.postgresql.org/docs/current/indexes-multicolumn.html
Supports
- A composite index stores multiple key columns
- Multicolumn B-tree indexes are most efficient with constraints on leading columns
- PostgreSQL can sometimes use later-column constraints through skip scan
- Broad multicolumn indexes should be used sparingly because they cost space and time
- https://dev.mysql.com/doc/refman/8.4/en/multiple-column-indexes.html
Supports
- MySQL treats a composite B-tree as ordered combined values
- MySQL can use leftmost prefixes of a composite index for lookup
- Key order determines which leading value combinations support direct lookup
- https://www.postgresql.org/docs/current/indexes-ordering.html
Supports
- A matching B-tree can deliver ordered rows without a separate sort
- A matching order combined with a limit can stop before scanning the remaining rows
- A table scan plus sort can cost less when a query retrieves a large table fraction
- https://www.postgresql.org/docs/current/indexes-index-only-scans.html
Supports
- Index-only scans require the index to supply all values referenced by the query
- PostgreSQL visibility checks can still require heap access for recently changed pages
- INCLUDE stores payload columns without making them search keys
- Wider covering indexes increase storage and can exceed size limits
- https://www.postgresql.org/docs/current/indexes-partial.html
Supports
- A partial index contains only rows satisfying its predicate
- Partial indexes can avoid storing common or uninteresting values and reduce update work
- The planner must recognize that a query condition implies the index predicate
- https://www.postgresql.org/docs/current/indexes-expressional.html
Supports
- An expression index stores a function or scalar expression result
- A query using a matching expression can use the index
- Expression results add computation to inserts and affected updates
- https://www.postgresql.org/docs/current/indexes-unique.html
Supports
- A unique index enforces uniqueness of one column or a column combination
- PostgreSQL automatically creates a unique index for a primary key or unique constraint
- Null treatment in unique indexes follows explicit PostgreSQL rules
- https://www.postgresql.org/docs/current/using-explain.html
Supports
- EXPLAIN displays the plan tree, cost estimates, and estimated row counts
- Measured execution can compare actual rows and timing against estimates
- Scan choice depends on selectivity, table access, ordering, and estimated costs
- https://www.postgresql.org/docs/current/planner-stats.html
Supports
- The planner estimates row counts from table size and sampled value statistics
- Distinct values, common values, and histograms inform selectivity estimates
- Extended statistics can represent selected cross-column dependencies and distributions
- ANALYZE collects ordinary and configured extended statistics
- https://dev.mysql.com/doc/refman/8.4/en/optimization-indexes.html
Supports
- Indexes can improve selected reads by locating matching rows
- Unnecessary indexes waste storage and add insert, update, and delete cost
- Index selection requires balancing read benefits against maintenance
- https://dev.mysql.com/doc/refman/8.4/en/column-indexes.html
Supports
- MySQL B-tree column indexes support equality, inequalities, BETWEEN, and IN
- Full-text and spatial searches use specialized index features
- https://dev.mysql.com/doc/refman/8.4/en/explain.html
Supports
- MySQL EXPLAIN shows how the optimizer plans to execute a statement
- EXPLAIN ANALYZE runs a statement and reports measured execution information
- https://dev.mysql.com/doc/refman/8.4/en/optimizing-innodb-queries.html
Supports
- An InnoDB covering index can avoid reading table data when it contains all required columns
- Wide or excessive indexes consume input and output capacity and memory and add maintenance
- https://www.sqlite.org/queryplanner.html
Supports
- SQLite documents row lookup through binary search over ordered indexes
- The planner chooses among indexes using available statistics
- SQLite demonstrates multi-column and covering indexes and index-assisted sorting
- https://learn.microsoft.com/en-us/sql/relational-databases/sql-server-index-design-guide?view=sql-server-ver17
Supports
- SQL Server distinguishes clustered, nonclustered, unique, filtered, and specialized index designs
- Effective index design begins with workload characteristics and balances query benefit against update and storage cost