Learn SQL: Day 6A – How postgresql store B-tree index data, Seq Scan vs Bitmap Heap Scan

In this post let’s find out how the data structure look like for a b-tree index in postgresql. Also we analyse our following test query results using EXPLAIN ANALYSE

EXPLAIN ANALYSE SELECT * FROM users WHERE city='Chicago'; 
QUERY PLAN ----- Seq Scan on users (cost=0.00..2332.00 rows=24780 width=51)
(actual time=0.077..21.085 rows=25000 loops=1) 

CREATE INDEX idx_users_city ON users(city); 

CREATE INDEX EXPLAIN ANALYSE SELECT * FROM users WHERE city='Chicago';
QUERY PLAN ---- Bitmap Heap Scan on users (cost=280.34..1672.09 rows=24780 width=51) 
(actual time=3.309..15.732 rows=25000 loops=1)

Q1) How can PostgreSQL build a B-tree index for emails when every email is unique?

Short answer: Yes. The index contains one entry for every row.

Suppose your table is:

The table itself is stored separately (simplified):

Heap Table
Row 1 -> john@test.com
Row 2 -> mary@test.com
Row 3 -> alice@test.com
Row 4 -> bob@test.com

The B-tree index is another structure.

Conceptually:

Email Index (B-tree)
alice@test.com  ----> Row 3
bob@test.com    ----> Row 4
john@test.com   ----> Row 1
mary@test.com   ----> Row 2

Notice two things:

1. The index is sorted by the indexed column (email), not by insertion order.
2. Each index entry stores:
   • the indexed value (email)
   • a pointer (called a TID, Tuple ID) to the actual row in the table

It does not store the entire row.

Why is this faster?

Without an index:

Search for:
user75000@example.com
↓
Row 1
No
↓
Row 2
No
↓
...
↓
Row 75000
Yes

Potentially 75,000 comparisons.

With a B-tree:

               root
             /      \
      A-M              N-Z
    /   \            /    \
 A-F   G-M      N-T     U-Z
                |
         user70000...
                |
         user75000...

The tree lets PostgreSQL eliminate huge portions of the search space.

Instead of checking every row, it follows the correct branch.

Does it consume memory?

Yes.

Every index consumes disk space.

If you have:

1 million rows

and create an index on email,

the index also has approximately 1 million entries.

That’s why we don’t create indexes on everything.

What happens during INSERT?

Suppose:

INSERT INTO users(email)
VALUES ('zack@test.com');

PostgreSQL does two things:

1. Inserts the row into the table.
2. Inserts a new entry into the B-tree.

That’s why indexes make:

• INSERT
• UPDATE
• DELETE

slightly slower.

Interview Question

If an index has one entry per row, isn’t searching still O(n)?

No.

Because of the B-tree.

Searching isn’t done linearly.

It’s approximately:

O(log n)

instead of

O(n)

For:

1,000,000 rows

a B-tree may require only around 20–25 comparisons rather than scanning all million rows.

Q2. Why did PostgreSQL use a Bitmap Heap Scan instead of an Index Scan?

Your output:

Before index:

Seq Scan on users
rows = 25000

After index:

Bitmap Heap Scan
rows = 25000

This is actually exactly what PostgreSQL should do.

Let’s understand why.

Your data distribution

Remember how you inserted the data?

CASE
WHEN i % 4 = 0 THEN 'Boston'
WHEN i % 4 = 1 THEN 'Chicago'
WHEN i % 4 = 2 THEN 'New York'
ELSE 'Dallas'
END

So:

100,000 rows
↓
4 cities
↓
25,000 users per city

That means:

Chicago
↓
25%
of the table

Option 1 — Sequential Scan

Without index:

Read
100000 rows
↓
Return
25000 rows

One pass through the table.

Option 2 — Normal Index Scan

Imagine PostgreSQL used the city index.

It would do something like:

Index
↓
Find row 4
↓
Jump to table
↓
Find row 9
↓
Jump to table
↓
Find row 13
↓
Jump to table
...
25000 times

That’s a lot of random table accesses.

Random disk reads (or random memory accesses) are expensive.

Option 3 — Bitmap Heap Scan

This is PostgreSQL’s compromise.

Step 1:

Read the index.

Chicago
↓
Rows
4
9
13
22
31
...
99998

Instead of fetching the rows immediately, PostgreSQL creates a bitmap.

Conceptually:

Rows to fetch
4
9
13
22
31
...

Then it sorts/groups those row locations by table page.

Only then does it read the table.

So instead of:

Index
↓
Table
↓
Index
↓
Table
↓
Index
↓
Table

it does:

Index
↓
Collect all matching row locations
↓
Read table pages efficiently
↓
Return rows

This reduces random I/O significantly.

When does PostgreSQL choose Bitmap Heap Scan?

Typically when:

Some rows match
but
not too few
and
not almost all.

Think of it like this:

The exact thresholds depend on statistics and cost estimates.

Why not an Index Scan?

Your query returns:

25,000 rows

That’s 25% of the table.

PostgreSQL thinks:

“Using the index is worthwhile, but fetching 25,000 rows one-by-one would be inefficient. I’ll gather all matching row locations first and then fetch the data in batches.”

That’s why you got:

Bitmap Heap Scan

Understanding our EXPLAIN ANALYZE Output

Seq Scan on users
(cost=0.00..2332.00 rows=24780 width=51)
(actual time=0.077..21.085 rows=25000 loops=1)

Let’s decode it.

Seq Scan

PostgreSQL reads every row.

cost

0.00..2332.00

This is not time.

It’s PostgreSQL’s internal cost estimate.

• 0.00 = startup cost
• 2332.00 = estimated total cost

Costs are used only to compare execution plans.

rows=24780

Planner estimated:

24,780 rows

Actual:

25,000 rows

Excellent estimate.

Good statistics help PostgreSQL choose the right plan.

width=51

Average row size is estimated to be:

51 bytes

This helps estimate I/O cost.

actual time

0.077..21.085

• First row available after 0.077 ms.
• Entire query finished after 21.085 ms.

loops=1

The node executed once.

After Creating the Index

Bitmap Heap Scan
(actual time=3.309..15.732)

Notice:

Execution time dropped from roughly:

21 ms
↓
16 ms

The improvement isn’t dramatic because your query still returns 25% of the table.

Indexes shine when they allow PostgreSQL to skip most of the table.

Want to See an Index Scan?

Try a highly selective query.

EXPLAIN ANALYZE
SELECT *
FROM users
WHERE email = 'user75000@example.com';

Since email is unique, PostgreSQL should choose:

Index Scan

because only one row matches.

A Practical Rule for Senior Engineers

When reading an execution plan, ask yourself these questions in order:

1. How many rows does the query return?
2. How many rows are in the table?
3. Is the predicate selective enough for an index?
4. What scan type did PostgreSQL choose?
5. Does that choice make sense?

Let’s cover the following topics in the remaining areas of Day 6.

• Day 6B – Composite indexes, covering indexes, partial indexes, unique indexes, expression indexes, GIN vs GiST vs BRIN vs Hash indexes, and real-world Rails indexing strategies
• Day 6C – Query optimization workshop: we’ll analyze real EXPLAIN ANALYZE outputs together, identify bottlenecks, and optimize queries step by step.

Given our role of Senior Rails Developer, Let’s spend 3 focused sessions on indexing and query optimization will provide much more value than rushing to the next topic.

Happy Learning! 🚀

Author: Abhilash

Hi, I’m Abhilash! A seasoned web developer with 15 years of experience specializing in Ruby and Ruby on Rails. Since 2010, I’ve built scalable, robust web applications and worked with frameworks like Angular, Sinatra, Laravel, Node.js, Vue and React. Passionate about clean, maintainable code and continuous learning, I share insights, tutorials, and experiences here. Let’s explore the ever-evolving world of web development together! View all posts by Abhilash