Introduction

As a database table grows, scanning every row for each query becomes increasingly expensive. An index provides an additional data structure that helps the database locate qualifying rows without examining the complete table.

B-tree indexes are widely used for equality searches, range conditions, ordered retrieval, prefix matching, uniqueness enforcement, and join operations.

A composite index contains more than one indexed column. It is useful when important queries filter, join, or order by a specific combination of columns.

In your System Design curriculum, B-tree and Composite Indexes is Topic 5.7 under Relational Data Modeling & SQL. It follows isolation and precedes query plans and connection pools.

Prerequisites

What Is a Database Index?

A database index is a separate physical data structure containing selected key values and references that help the database locate table rows.

Without a suitable index:

Query
  |
  v
Examine many or all table rows
  |
  v
Evaluate the filter
  |
  v
Return matching rows


With a suitable index:

Query
  |
  v
Navigate indexed keys
  |
  v
Locate qualifying entries
  |
  v
Retrieve matching rows

An index does not replace the table. It provides another route through which the database can access data.

What Is a B-tree?

A B-tree is a balanced, ordered tree structure used by many database systems for indexes.

Rather than storing one key and one child per node, a B-tree node can contain several ordered keys and references. This keeps the tree relatively shallow and reduces the number of storage pages required during navigation.

                    [40 | 80]
                   /    |     \
                  /     |      \
                 v      v       v
        [10 | 20 | 30] [50 | 70] [90 | 100 | 120]

The diagram is simplified. Real database indexes are stored in fixed-size pages and contain database-specific metadata, key values, and references.

B-tree Index Structure

A B-tree index generally contains:

• A root page
• Zero or more intermediate levels
• Leaf pages
• Ordered key values
• References to child pages or table rows

Root page
    |
    +-- Intermediate page
    |       |
    |       +-- Leaf page
    |       +-- Leaf page
    |
    +-- Intermediate page
            |
            +-- Leaf page
            +-- Leaf page

Root Page

The root is the starting point for index navigation.

Intermediate Pages

Intermediate pages guide navigation toward the leaf page containing the required key range.

Leaf Pages

Leaf pages contain ordered index entries. The exact leaf representation depends on whether the index is clustered, nonclustered, covering, or implemented through another database-specific design.

Why Balanced Trees Matter

A balanced tree keeps leaf pages at a consistent navigation depth. This avoids the progressively longer search paths that can occur in an unbalanced search tree.

Balanced tree:

Root
 |
 +-- Branch
 |    |
 |    +-- Leaf
 |
 +-- Branch
      |
      +-- Leaf


Comparable navigation depth
for indexed keys

B-tree height depends on page size, key width, entry overhead, row count, fill characteristics, and the database implementation.

Equality Search

A B-tree index can efficiently support equality conditions on its indexed key.

SELECT
    customer_id,
    customer_number,
    display_name
FROM customers
WHERE customer_number = :customer_number;

CREATE UNIQUE INDEX ix_customers_number
ON customers
(
    customer_number
);

The database can navigate to the relevant indexed value instead of scanning the entire customer table.

Range Search

Because B-tree keys are ordered, the index can support range conditions.

SELECT
    order_id,
    order_number,
    ordered_at
FROM orders
WHERE ordered_at >= :start_time
  AND ordered_at < :end_time
ORDER BY
    ordered_at;

CREATE INDEX ix_orders_ordered_at
ON orders
(
    ordered_at
);

After locating the beginning of the range, the database can read consecutive index entries until the range ends.

Supporting ORDER BY

An index can provide rows in an order compatible with an ORDER BY clause, potentially reducing or avoiding a separate sorting operation.

SELECT
    order_id,
    order_status,
    ordered_at
FROM orders
WHERE customer_id = :customer_id
ORDER BY
    ordered_at DESC,
    order_id DESC;

CREATE INDEX ix_orders_customer_ordered_id
ON orders
(
    customer_id,
    ordered_at DESC,
    order_id DESC
);

The database can navigate matching customer entries in the required ordering when the index and query are compatible.

Supporting Joins

Indexes on columns participating in joins can help the database locate related rows.

SELECT
    o.order_number,
    ol.line_number,
    ol.product_id,
    ol.quantity
FROM orders AS o
INNER JOIN order_lines AS ol
    ON ol.order_id = o.order_id
WHERE
    o.order_id = :order_id;

CREATE INDEX ix_order_lines_order
ON order_lines
(
    order_id
);

Some databases do not automatically create an index on every foreign-key column. Foreign-key indexes should be selected according to joins, parent modifications, table size, and workload evidence.

What Is a Composite Index?

A composite index contains two or more key columns.

CREATE INDEX ix_orders_customer_status_date
ON orders
(
    customer_id,
    order_status,
    ordered_at
);

The combined key is ordered first by customer_id, then by order_status within each customer, and finally by ordered_at within each customer-and-status group.

Composite ordering:

customer_id
    |
    +-- order_status
            |
            +-- ordered_at

Why Composite Column Order Matters

A composite index does not provide identical access for every permutation of its columns.

CREATE INDEX ix_orders_customer_status_date
ON orders
(
    customer_id,
    order_status,
    ordered_at
);

This index is organized primarily by customer. Entries for the same customer are then organized by status and date.

It can be suitable for:

WHERE customer_id = :customer_id

WHERE customer_id = :customer_id
  AND order_status = :status

WHERE customer_id = :customer_id
  AND order_status = :status
  AND ordered_at >= :start_time

It is generally less directly suitable for a query filtering only by order_status or only by ordered_at, because the leading customer column is absent.

Leftmost-prefix Principle

A composite B-tree index is commonly most useful when a query constrains a leading sequence of its key columns.

Index:

(tenant_id, customer_id, ordered_at)


Leading prefixes:

tenant_id

tenant_id, customer_id

tenant_id, customer_id, ordered_at

Compatible Query

SELECT
    order_id,
    ordered_at
FROM orders
WHERE tenant_id = :tenant_id
  AND customer_id = :customer_id
ORDER BY
    ordered_at DESC;

Missing Leading Column

SELECT
    order_id,
    ordered_at
FROM orders
WHERE customer_id = :customer_id;

The database may be unable to seek efficiently by customer using this index when tenant_id is not supplied. The optimizer can still choose an index scan or another access strategy, depending on the engine and statistics.

Equality, Range, and Sort Columns

A practical composite-index design often considers:

1. Columns used by equality conditions
2. Columns used by range conditions
3. Columns used for ordering
4. Columns required to complete the result

Query Example

SELECT
    order_id,
    order_number,
    ordered_at,
    total_amount
FROM orders
WHERE tenant_id = :tenant_id
  AND customer_id = :customer_id
  AND order_status = :status
  AND ordered_at >= :start_time
ORDER BY
    ordered_at DESC,
    order_id DESC;

Candidate Index

CREATE INDEX ix_orders_tenant_customer_status_date_id
ON orders
(
    tenant_id,
    customer_id,
    order_status,
    ordered_at DESC,
    order_id DESC
);

The query uses equality conditions on tenant, customer, and status, followed by a date range and compatible ordering.

Range Conditions and Later Columns

A range condition can reduce how effectively later key columns narrow index navigation.

CREATE INDEX ix_orders_tenant_date_status
ON orders
(
    tenant_id,
    ordered_at,
    order_status
);

SELECT
    order_id
FROM orders
WHERE tenant_id = :tenant_id
  AND ordered_at >= :start_time
  AND order_status = :status;

The index can navigate the tenant and date range. The status condition can still be evaluated from the index or rows, but it might not narrow the initial range as effectively as it would before the range column.

Exact behaviour depends on the database optimizer and index implementation. Validate the execution plan.

Selectivity

Selectivity describes how strongly a condition reduces the number of matching rows.

Highly selective condition:

customer_number = one unique value


Low-selectivity condition:

customer_status = active

when most customers are active

A low-selectivity index is not automatically useless. It can still be valuable when combined with tenant, category, date, ordering, or covering requirements.

Tenant-first Composite Indexes

Multi-tenant queries commonly include a tenant condition.

SELECT
    order_id,
    order_number,
    order_status
FROM orders
WHERE tenant_id = :trusted_tenant_id
  AND customer_id = :customer_id;

CREATE INDEX ix_orders_tenant_customer
ON orders
(
    tenant_id,
    customer_id
);

Including the tenant key can support tenant-scoped access patterns and keep matching entries adjacent.

Tenant scope must come from trusted application identity and authorization context. An index does not enforce authorization by itself.

Sort Direction

Some database systems allow ascending and descending directions in index definitions.

CREATE INDEX ix_orders_customer_date
ON orders
(
    customer_id ASC,
    ordered_at DESC,
    order_id DESC
);

Whether one index can satisfy forward, reverse, or mixed-direction ordering depends on the database platform and query shape.

Composite Indexes for Cursor Pagination

Cursor pagination commonly uses a deterministic composite ordering.

SELECT
    order_id,
    order_status,
    ordered_at
FROM orders
WHERE tenant_id = :tenant_id
  AND
  (
      ordered_at < :cursor_ordered_at
      OR
      (
          ordered_at = :cursor_ordered_at
          AND order_id < :cursor_order_id
      )
  )
ORDER BY
    ordered_at DESC,
    order_id DESC
LIMIT 21;

Supporting Index

CREATE INDEX ix_orders_tenant_date_id
ON orders
(
    tenant_id,
    ordered_at DESC,
    order_id DESC
);

The unique order ID acts as a deterministic tiebreaker when several orders have the same timestamp.

Covering Indexes

A covering index contains the information required to evaluate and return a query without retrieving additional data from the underlying table.

Query

SELECT
    order_id,
    order_status,
    ordered_at,
    total_amount
FROM orders
WHERE customer_id = :customer_id
ORDER BY
    ordered_at DESC;

Covering-index Concept

Key columns:

customer_id
ordered_at
order_id


Included or stored output columns:

order_status
total_amount

Some databases support non-key included columns through an INCLUDE clause.

CREATE INDEX ix_orders_customer_date
ON orders
(
    customer_id,
    ordered_at DESC,
    order_id
)
INCLUDE
(
    order_status,
    total_amount
);

Included-column syntax and behaviour are database-specific. In systems without this feature, all indexed columns can become key columns, increasing key width and maintenance cost.

Key Columns vs Included Columns

Do not place every selected column into every index. Wide indexes increase storage, memory consumption, write work, logging, and maintenance cost.

Unique Indexes

A unique index prevents duplicate indexed key values according to the database's null and collation semantics.

CREATE UNIQUE INDEX ux_customers_tenant_number
ON customers
(
    tenant_id,
    customer_number
);

This design enforces uniqueness of the customer number inside a tenant.

Prefer a PRIMARY KEY or UNIQUE constraint when the requirement represents a logical integrity rule. The database can implement that constraint using a unique index.

Filtered and Partial Indexes

Some databases support indexing only rows that satisfy a predicate.

CREATE INDEX ix_orders_active_customer
ON orders
(
    customer_id,
    ordered_at DESC
)
WHERE order_status IN
(
    'pending',
    'confirmed',
    'processing'
);

A filtered or partial index can be smaller and more selective when important queries repeatedly access a stable subset of rows.

Syntax, supported predicates, parameter behavior, and optimizer matching are platform-specific.

Expression and Computed-column Indexes

Some databases can index an expression or a computed column.

CREATE INDEX ix_users_lower_email
ON users
(
    LOWER(email_address)
);

A query must use a compatible expression for the optimizer to consider the index.

SELECT
    user_id,
    email_address
FROM users
WHERE LOWER(email_address) =
      LOWER(:email_address);

Expression-index support and function-determinism requirements differ by database.

Prefix Search

A B-tree index can often support a string prefix search.

SELECT
    product_id,
    product_name
FROM products
WHERE product_name LIKE 'Key%';

A pattern beginning with an unrestricted wildcard is usually less suitable for ordinary B-tree navigation.

SELECT
    product_id,
    product_name
FROM products
WHERE product_name LIKE '%board%';

Substring and linguistic search can require full-text or specialized search indexes rather than an ordinary B-tree.

Non-sargable Predicates

A predicate is commonly called sargable when the database can use it as a search argument for an index access path.

SELECT
    order_id
FROM orders
WHERE DATE(ordered_at) = :order_date;

SELECT
    order_id
FROM orders
WHERE ordered_at >= :day_start
  AND ordered_at < :next_day_start;

The range expression is also clearer about timestamp boundaries and can align with an ordinary index on ordered_at.

Implicit Conversion

Comparing incompatible types can introduce conversion and prevent efficient index use.

Indexed column:

customer_number VARCHAR


Parameter supplied as:

Integer

Indexed column:

customer_number VARCHAR


Parameter supplied as:

String using matching semantics

Parameter types, column types, collations, and comparison rules should align with the database schema.

Clustered and Nonclustered Indexes

Some database systems distinguish clustered and nonclustered indexes.

Terminology and storage behavior vary significantly among database platforms. Learn the implementation used by the selected engine rather than assuming that all B-tree indexes behave identically.

Index Write Cost

Every applicable INSERT, UPDATE, and DELETE can require index maintenance.

INSERT row
   |
   +-- Update table data
   |
   +-- Update primary-key index
   |
   +-- Update unique indexes
   |
   +-- Update secondary indexes
   |
   +-- Write transaction-log records

Additional indexes can increase:

• Insert latency
• Update latency
• Delete latency
• Transaction-log volume
• Storage consumption
• Memory pressure
• Backup size
• Maintenance time

Page Splits

When an index page lacks enough free space for a new entry, the database can split or reorganize pages according to its implementation.

Full leaf page:

[10] [20] [30] [40]


Insert:

25


Possible result:

Page A:
[10] [20]

Page B:
[25] [30] [40]

Splits can increase writes, logging, and fragmentation. The actual impact depends on insert order, key distribution, page management, fill settings, and database implementation.

Sequential and Random Keys

A sequential key commonly directs new entries toward one end of an index, while a randomly distributed key can place inserts throughout the index.

The correct identifier strategy depends on workload, database engine, distribution requirements, privacy needs, and operational measurement.

Key Width

Wider index keys reduce the number of entries that fit on a page and can increase memory, storage, I/O, and comparison cost.

Narrow key:

BIGINT


Wider composite key:

tenant_id
+
customer_number
+
order_timestamp
+
long_status_text

Keep index keys focused. Place output-only columns in an included section where supported instead of expanding the ordered key unnecessarily.

Too Many Indexes

Indexing every column is not a valid optimization strategy.

Index every column.

Index every column pair.

Index every possible ORDER BY.

Never remove an index.

Identify important queries.

Create candidate indexes.

Measure query plans and latency.

Measure write impact.

Remove duplicate or unused indexes carefully.

Overlapping Indexes

CREATE INDEX ix_orders_customer
ON orders
(
    customer_id
);

CREATE INDEX ix_orders_customer_date
ON orders
(
    customer_id,
    ordered_at
);

CREATE INDEX ix_orders_customer_date_status
ON orders
(
    customer_id,
    ordered_at,
    order_status
);

These indexes overlap. That does not automatically mean that the shorter indexes are redundant, because key width, covering needs, query shapes, and optimizer choices can differ.

Review usage and plans before removing an index.

Statistics and Cardinality Estimates

The optimizer uses statistics to estimate how many rows a predicate or join will return.

Optimizer estimates:

- Rows matching tenant
- Rows matching status
- Rows inside date range
- Join cardinality
- Expected lookup count

Inaccurate estimates can cause the optimizer to choose an inefficient scan, join order, or lookup strategy even when useful indexes exist.

Index Seek vs Index Scan

A scan is not automatically bad. Scanning can be efficient when a query needs a large portion of the table or when the table is small.

Validate with Query Plans

EXPLAIN
SELECT
    order_id,
    order_status,
    ordered_at
FROM orders
WHERE tenant_id = :tenant_id
  AND customer_id = :customer_id
ORDER BY
    ordered_at DESC;

EXPLAIN syntax and plan terminology differ by database platform.

Inspect whether the plan shows:

• The expected index
• A seek or scan
• Estimated and actual row counts
• Residual filtering
• Explicit sorting
• Repeated lookups
• Join algorithms
• Memory or spill indicators

Composite-index Design Workflow

1. Capture the complete important query.
2. Identify equality predicates.
3. Identify range predicates.
4. Identify join columns.
5. Identify grouping and ordering.
6. Identify required result columns.
7. Identify tenant or authorization scope.
8. Estimate result selectivity.
9. Create the narrowest useful candidate index.
10. Inspect the execution plan.
11. Measure reads, latency, and returned rows.
12. Measure write and storage impact.
13. Test with representative data distribution.
14. Review overlapping indexes.
15. Monitor the index after deployment.

Query-to-index Examples

Customer's Recent Orders

SELECT
    order_id,
    order_status,
    ordered_at
FROM orders
WHERE tenant_id = :tenant_id
  AND customer_id = :customer_id
ORDER BY
    ordered_at DESC,
    order_id DESC
LIMIT 20;

CREATE INDEX ix_orders_tenant_customer_date_id
ON orders
(
    tenant_id,
    customer_id,
    ordered_at DESC,
    order_id DESC
);

Pending Orders by Date

SELECT
    order_id,
    customer_id,
    ordered_at
FROM orders
WHERE tenant_id = :tenant_id
  AND order_status = 'pending'
  AND ordered_at < :cutoff
ORDER BY
    ordered_at;

CREATE INDEX ix_orders_tenant_status_date
ON orders
(
    tenant_id,
    order_status,
    ordered_at
);

Course Lessons

SELECT
    lesson_id,
    lesson_title,
    display_order
FROM lessons
WHERE chapter_id = :chapter_id
ORDER BY
    display_order;

CREATE UNIQUE INDEX ux_lessons_chapter_order
ON lessons
(
    chapter_id,
    display_order
);

The unique index can support retrieval order and enforce that a chapter cannot contain two lessons at the same display position.

Indexes and Security

Indexes do not replace authentication, authorization, row filtering, or tenant isolation.

SELECT
    order_id,
    order_status
FROM orders
WHERE tenant_id = :trusted_tenant_id
  AND order_id = :order_id;

The index can accelerate the authorized query, but trusted tenant filtering and resource-level authorization still must be enforced.

Indexes can also duplicate sensitive key values in a separate physical structure. Database access, backups, replicas, diagnostics, and disposal procedures must protect indexed data appropriately.

Index Maintenance

Index maintenance requirements depend on database engine, write workload, page utilization, fragmentation, and query behaviour.

Operational activities can include:

• Updating statistics
• Rebuilding or reorganizing selected indexes
• Removing verified unused indexes
• Consolidating overlapping indexes
• Monitoring index size
• Monitoring page splits
• Validating corruption checks
• Reviewing indexes after query changes

Avoid applying a fixed maintenance routine to every index without measuring the database platform and workload.

Index Observability

Useful index metrics include:

• Index seeks and scans
• Lookup count
• Index size
• Page count
• Page-split activity
• Write-maintenance cost
• Index usage by query
• Unused-index evidence
• Duplicate or overlapping-index evidence
• Estimated versus actual row counts
• Sort and spill activity
• Query latency before and after index changes

Common Indexing Mistakes

Recommended Test Cases

B-tree and Composite-index Best Practices

Practice Exercise

Design and validate indexes for the online learning platform developed in previous lessons.

Requirements

1. List all enrollments for one learner ordered by enrollment date.
2. List active learners for one course.
3. Prevent duplicate learner-course enrollment.
4. List chapters in course display order.
5. List lessons in chapter display order.
6. Retrieve recent quiz attempts for one learner and quiz.
7. Support cursor pagination for quiz attempts.
8. Find incomplete enrollments for a scheduled reminder job.
9. Include the tenant key in organization-scoped queries.
10. Create the narrowest useful candidate indexes.
11. Capture the execution plan before each index.
12. Create one index at a time.
13. Capture the execution plan after each index.
14. Measure read and write latency.
15. Document overlapping or unnecessary indexes.

Candidate Enrollment Index

CREATE UNIQUE INDEX ux_enrollments_tenant_learner_course
ON enrollments
(
    tenant_id,
    learner_id,
    course_id
);

Candidate Course-roster Index

CREATE INDEX ix_enrollments_tenant_course_status_learner
ON enrollments
(
    tenant_id,
    course_id,
    enrollment_status,
    learner_id
);

Candidate Quiz-attempt Cursor Index

CREATE INDEX ix_attempts_tenant_learner_quiz_submitted_id
ON quiz_attempts
(
    tenant_id,
    learner_id,
    quiz_id,
    submitted_at DESC,
    attempt_id DESC
);

Index Review Template

Frequently Asked Questions