Overview - B-tree index (default) behavior

What is it?

A B-tree index is a special data structure used by PostgreSQL to speed up searching and sorting data in tables. It organizes data in a balanced tree format, allowing quick lookups, insertions, and deletions. This index type is the default in PostgreSQL because it works well for many common queries involving comparisons like equals, less than, or greater than. It helps the database find data without scanning the entire table.

Why it matters

Without B-tree indexes, searching for data in large tables would be slow because the database would have to look at every row. This would make applications feel sluggish and inefficient. B-tree indexes solve this by narrowing down the search quickly, improving performance and user experience. They are essential for databases to handle large amounts of data efficiently.

Where it fits

Before learning about B-tree indexes, you should understand basic database tables and how queries work. After mastering B-tree indexes, you can explore other index types like hash, GIN, or GiST indexes, and learn about query optimization and execution plans.

Mental Model

Core Idea

A B-tree index organizes data in a balanced tree structure to quickly find and sort values without scanning the whole table.

Think of it like...

Imagine a phone book organized alphabetically with tabs for each letter. Instead of flipping through every page, you jump directly to the letter you want, then find the name quickly. The B-tree index works like those tabs, guiding you fast to the right place.

Root
 ├─ Internal Node
 │   ├─ Leaf Node (values)
 │   ├─ Leaf Node (values)
 │   └─ Leaf Node (values)
 └─ Internal Node
     ├─ Leaf Node (values)
     └─ Leaf Node (values)

Each node holds keys and pointers to child nodes or data rows, keeping the tree balanced.

Build-Up - 7 Steps

1

FoundationWhat is an Index in Databases

Concept: Introduce the idea of an index as a tool to speed up data retrieval.

An index in a database is like the index in a book. Instead of reading every page to find a topic, you look at the index to find the page number quickly. Similarly, a database index helps find rows faster without scanning the whole table.

Result

You understand that indexes help speed up searches by pointing directly to data locations.

Knowing that indexes act like a shortcut to data helps you appreciate why databases use them to improve performance.

2

FoundationBasics of B-tree Structure

3

IntermediateHow PostgreSQL Uses B-tree Indexes

4

IntermediateRange Queries and B-tree Efficiency

5

IntermediateLimitations of B-tree Indexes

6

AdvancedHow B-tree Maintains Balance and Performance

7

ExpertB-tree Index Usage in PostgreSQL Query Planner

Under the Hood

Internally, a B-tree index stores keys and pointers to table rows in nodes arranged in a balanced tree. Each node holds multiple keys sorted in order. Searching starts at the root node and moves down by comparing the search key to node keys, choosing the correct child node. This continues until reaching a leaf node, which points to the actual data. Inserts and deletes cause nodes to split or merge to keep the tree balanced, ensuring the height remains low for fast access.

Why designed this way?

B-trees were designed to minimize disk reads by storing many keys per node, matching disk page sizes. Balancing ensures that the tree height grows slowly with data size, keeping search times logarithmic. Alternatives like binary trees were rejected because they require more disk reads and can become unbalanced, slowing down queries.

┌───────────┐
│   Root    │
│ Keys: 30  │
├─────┬─────┤
│     │     │
▼     ▼     ▼
Node  Node  Node
Keys: 10 Keys: 20 Keys: 40
│     │     │
▼     ▼     ▼
Leaf  Leaf  Leaf
Pointers to data rows

Myth Busters - 4 Common Misconceptions

Quick: Does a B-tree index always speed up every query? Commit yes or no.

Common Belief:A B-tree index always makes queries faster no matter the query.

Tap to reveal reality

Quick: Can B-tree indexes speed up full-text search queries? Commit yes or no.

Common Belief:B-tree indexes are good for all types of searches, including full-text search.

Tap to reveal reality

Quick: Does PostgreSQL always use a B-tree index if it exists? Commit yes or no.

Common Belief:If a B-tree index exists on a column, PostgreSQL will always use it for queries on that column.

Tap to reveal reality

Quick: Are B-tree indexes always small in size? Commit yes or no.

Common Belief:B-tree indexes are always small and don't affect storage much.

Tap to reveal reality

Expert Zone

1

B-tree index performance depends heavily on fill factor settings, which control how full nodes are kept to balance read and write efficiency.

2

PostgreSQL supports index-only scans with B-tree indexes when all needed columns are in the index, avoiding table access and improving speed.

3

Multi-column B-tree indexes follow a left-prefix rule, meaning queries must use the leading columns to benefit from the index.

When NOT to use

Avoid B-tree indexes for data types or queries involving full-text search, arrays, or geometric data. Use GIN or GiST indexes instead. Also, for equality-only lookups on large datasets, hash indexes can be an alternative, though less common.

Production Patterns

In production, B-tree indexes are commonly used on primary keys, foreign keys, and columns frequently used in WHERE clauses or ORDER BY. DBAs monitor index usage and size, adjusting fill factors and reindexing to maintain performance.

Connections

Binary Search Algorithm

B-tree search is a generalization of binary search to multiple keys per node.

Understanding binary search helps grasp how B-tree nodes quickly narrow down search ranges.

File System Directory Trees

Both organize data hierarchically for fast lookup and updates.

Knowing how file systems use tree structures clarifies why balanced trees are efficient for indexing.

Library Card Catalogs

Both use sorted, hierarchical systems to find information quickly.

Recognizing this connection shows how indexing is a universal solution for organizing large information sets.

Common Pitfalls

#1Creating indexes on columns that are rarely used in queries.

Wrong approach:CREATE INDEX idx_unused ON table(column_not_in_queries);

Correct approach:Create indexes only on columns frequently used in WHERE, JOIN, or ORDER BY clauses.

Root cause:Misunderstanding that indexes improve all queries, leading to unnecessary overhead.

#2Expecting B-tree indexes to speed up queries with LIKE '%pattern'.

Wrong approach:SELECT * FROM table WHERE column LIKE '%pattern'; -- expecting index use

Correct approach:Use full-text search or trigram indexes for such patterns.

Root cause:Not knowing that B-tree indexes only help with prefix matches, not arbitrary substring searches.

#3Ignoring the impact of frequent writes on index performance.

Wrong approach:Creating many indexes on a write-heavy table without monitoring.

Correct approach:Limit indexes on write-heavy tables and monitor performance, adjusting as needed.

Root cause:Overlooking that indexes slow down inserts, updates, and deletes due to maintenance overhead.

Key Takeaways

B-tree indexes organize data in a balanced tree to speed up searches and sorting without scanning entire tables.

They work best for equality and range queries but are not suitable for full-text or complex data searches.

PostgreSQL's query planner decides when to use B-tree indexes based on cost estimates, not automatically.

Maintaining balanced nodes through splitting and merging keeps B-tree performance consistent even as data changes.

Choosing the right columns and understanding index limitations is crucial for effective database performance.