PostgreSQL: The B-Tree Index Explained

Have you ever wondered why your database query takes 5 seconds instead of 5 milliseconds?

Warning: This post contains heavy SQL concepts. Grab a coffee! ☕

The Phonebook Analogy

Imagine a phonebook that is not sorted alphabetically. If you want to find "Otabek", you have to check every single name from page 1 to page 1000. This is called a Sequential Scan (O(N)).

Now, imagine the phonebook is sorted. You open the middle page. "M". You know "O" is after "M", so you ignore the first half. You split the remaining half again. This is a B-Tree (O(Log N)).

Internals

PostgreSQL uses a B-Tree (Balanced Tree) by default.

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

If you see Seq Scan, you are scanning the whole table. If you see Index Scan, you are traversing the tree.

When B-Trees Fail

B-Trees are great for =, <, >. But what if you want to find everyone whose name ends with "bek"?

SELECT * FROM users WHERE name LIKE '%bek';

A normal B-Tree cannot help you here. You need a GIN index or a Reverse Index.

Conclusion

Indexes are not magic. They are data structures. Choosing the right one (B-Tree, GIN, GiST) is the difference between a scalable app and a crashed server.