🌳B-Tree

NEW

Balanced multiway tree index that maintains sorted keys for efficient search, range queries, insertion, and deletion.

DESCRIPTION

A B-tree organizes keys in nodes with multiple children, keeping the tree height small for efficient disk access. Internal nodes guide search; leaves store pointers or records. Balanced by design, it supports ordered scans and range queries. Variants like B+Tree store all data in leaves and link leaf nodes. B-trees are widely used in databases and filesystems for primary and secondary indexes. They outperform hash indexes for range predicates but are slower for pure equality under some workloads. Careful page sizing, fill factor, and maintenance impact performance.

ALTERNATIVE DEFINITIONS

PostgreSQL Documentation

B-tree indexes are the standard index type and are suitable for most queries, including equality and range comparisons.

Emphasizes suitability for equality and range comparisons and default status.

Source

Oracle

B-tree indexes store key values derived from one or more columns and pointers to the associated table rows.

Explains structure with column-derived keys and row pointers.

Source

SQLite

The SQLite database file is organized as a B-tree.

Shows B-tree as foundational file structure in SQLite.

Source

RELATED TERMS

Balanced Tree Index Skip List Binary Search Tree Range Query Page Node Disk I/O

COMPETING TERMS

Hash Index Log-Structured Merge-Tree

RELATIONS

• Broader: Index
• Narrower: B-tree Index

KNOWLEDGE AREAS

Data Storage & Operations Data Engineering Software Engineering Infrastructure

TARGET AUDIENCE

Data Engineer Software Developer Data Architect Cloud Architect Data Modeler

EXTERNAL SOURCES

• Wikipedia - B-tree
• PostgreSQL - Index types including B-tree
• Oracle - Oracle index concepts, B-tree
• SQLite - SQLite file format using B-tree

TOP QUESTIONS

Why are B-trees widely used in databases?

They provide balanced, shallow structures that minimize disk I/O and support fast equality and range queries on large datasets.

Category: Relevancy

What is the difference between B-tree and B+Tree?

B+Tree stores all data in leaves and links leaf nodes, improving range scans; internal nodes hold only keys for navigation.

Category: Example

When should a Hash Index be preferred over a B-tree?

For workloads dominated by equality lookups with minimal range queries, hash indexes may offer better performance.

Category: Alternatives

What are common mistakes with B-tree indexes?

Creating redundant indexes, ignoring fill factor and maintenance, and indexing low-selectivity columns can degrade performance.

Category: Mistakes

How does page size affect B-tree performance?

Larger pages reduce height and improve scans but may increase memory overhead; optimal size depends on workload and hardware.

Category: Opinion

What is a risk of over-indexing with B-trees?

Write performance can suffer, and storage costs rise; excessive indexes complicate maintenance and query planning.

Category: Risk

Can B-trees support composite keys?

Yes, they can index multiple columns and maintain lexicographic ordering for efficient multi-column predicates.

Category: Requirements

Do B-trees guarantee balanced height?

Yes, rebalancing operations maintain a shallow, balanced tree structure across inserts and deletes.

Category: Example

Where to start learning B-trees?

Read PostgreSQL and Oracle indexing documentation and implement a simple B-tree to understand node splits and merges.

Category: Overview