🌲B-tree Index

NEW

A balanced-tree indexing structure that accelerates equality and range lookups by maintaining sorted keys.

DESCRIPTION

A B-tree index stores sorted keys in a balanced tree, enabling efficient searches, inserts, and deletes in logarithmic time. It supports equality and range predicates, ordered scans, and is the default index type in many relational databases. Proper use improves join performance, WHERE filters, and ORDER BY queries. Selectivity, clustering, and maintenance (vacuuming, reindexing) influence performance. Alternatives like hash indexes or LSM-trees may excel in specific workloads.

ALTERNATIVE DEFINITIONS

PostgreSQL Documentation

B-tree indexes can handle equality and range queries on data that can be sorted into some ordering.

Highlights support for both equality and range predicates, matching common SQL usage.

Source

Wikipedia

In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.

General definition of the underlying structure used by B-tree indexes.

Source

RELATED TERMS

B-Tree Clustered Index Nonclustered Index Range Query Selectivity Cardinality PostgreSQL InnoDB

COMPETING TERMS

Hash Index Log-Structured Merge-Tree

RELATIONS

• Broader: B-Tree Index

KNOWLEDGE AREAS

Data Storage & Operations Data Engineering Data Modeling Data Warehousing & BI

TARGET AUDIENCE

Data Engineer Data Architect Data Modeler Software Developer BI Specialist Cloud Architect

EXTERNAL SOURCES

• Wikipedia - B-tree
• PostgreSQL - Official B-tree index behavior
• MySQL - InnoDB B-tree index types
• SQLite - On-disk B-tree page format

TOP QUESTIONS

When should I use a B-tree Index?

Use it for equality and range predicates, ordered scans, and join keys on columns with good selectivity.

Category: Requirements

What workloads are not ideal for B-tree Indexes?

High write amplification workloads with heavy random inserts may prefer LSM-trees; exact-match-only lookups may favor hash indexes.

Category: Alternatives

How does clustering affect B-tree Index performance?

Heap clustering improves locality for range scans and reduces random I/O, often yielding faster queries.

Category: Explanation

Do B-tree Indexes help ORDER BY queries?

Yes, matching index order can satisfy ORDER BY without sorts, reducing query latency significantly.

Category: Example

What is a common mistake with B-tree Indexes?

Over-indexing increases write overhead and maintenance costs. Index only what queries use.

Category: Mistakes

How do composite B-tree Indexes work?

They index multiple columns in a left-to-right priority; predicates should start with leading columns to be effective.

Category: Explanation

How are B-tree Indexes maintained?

Databases rebalance and split nodes automatically. Periodic vacuuming, analyze, or reindexing may be needed.

Category: Management

What is the storage overhead of B-tree Indexes?

They store keys and pointers with some fill-factor overhead; size scales with row count and key width.

Category: Example

Do NULLs impact B-tree Index behavior?

Ordering and inclusion of NULLs vary by DBMS; check documentation for sort order and predicate support.

Category: Risk