Panduan Lengkap B-Tree Index di PostgreSQL: Teori & Optimasi Query

PostgreSQL adalah database dengan kemampuan indexing yang paling matang di era open source — dan B-Tree adalah jenis index paling fundamental di dalamnya. Tapi tau gak sih, mayoritas problem performa yang gue handle di klien bukan karena database-nya lambat, melainkan karena index-nya gak optimal? Lo bikin index di kolom A, tapi query-nya filter di kolom B. Lo bikin composite index (A, B, C) urutannya salah. Atau — yang paling sering — lo gak bikin index sama sekali.

Artikel ini bedah B-Tree index di PostgreSQL dari level paling dasar sampai strategi optimasi yang gue pake di production. Lo bakal ngerti: gimana B-Tree bekerja di dalam, kapan pake index vs full scan, cara baca query plan, dan trik index yang jarang diketahui.

Apa Itu B-Tree Index?

B-Tree (Balanced Tree) adalah struktur data yang nyimpen key-value pairs secara terurut dan seimbang. Bayangin kayak kamus: lo cari kata "PostgreSQL" — lo buka bagian tengah, compare dengan halaman yang lagi lo buka, terus lo tau harus ke kiri atau ke kanan sampe ketemu.

Secara teknis, B-Tree di PostgreSQL punya karakteristik:

• Self-balancing — semua leaf nodes berada di level yang sama, jadi worst-case search time predictable
• Logarithmic complexity — search, insert, delete semuanya O(log n). Untuk tabel 1 juta baris, B-Tree cuma butuh ~20 langkah buat nemuin data. Bandingin sama full sequential scan yang butuh 1 juta langkah
• Page-based storage — node B-Tree disimpen di halaman 8KB (default PostgreSQL page size). Ini penting buat performa I/O
• Multi-level branching — root → internal → leaf. Semakin tinggi fill factor, semakin efisien page utilization

Struktur Internal B-Tree

B-Tree di PostgreSQL punya 3 level:

Level 0 (Root):     [100, 200, 300]
                       /    |    \
Level 1 (Internal): [50,75] [150,175] [250,275]
                      /  \     /  \      /  \
Level 2 (Leaf):    [1..49] [50..99] [100..149] ...

Setiap node (kecuali root) punya antara ceil(fill_factor * branching_factor) sampai branching_factor anak. Default branching factor di Postgres tergantung ukuran key — makin kecil key-nya, makin banyak cabang per page.

Penting: leaf nodes menyimpan TID (Tuple ID), bukan data langsung. TID adalah pointer fisik ke baris di heap page: (block_number, offset_in_block). Artinya, setelah B-Tree nemuin key yang cocok, Postgres masih perlu heap access buat ambil data lengkap — yang kadang jadi bottleneck kalo index-only scan gak bisa dipake.

Kapan B-Tree Efektif?

Operasi	Cepat?	Catatan
Equality (=)	🟢 Sangat cepat	B-Tree langsung nemuin exact match dalam O(log n)
Range (>, <, BETWEEN)	🟢 Cepat	B-Tree scan satu arah (forward/backward) sangat efisien
Prefix matching (LIKE 'abc%')	🟡 Sedang	Bisa pake index scan kalo collation-nya C, tapi gak untuk LIKE '%abc'
ORDER BY	🟢 Cepat	Index sudah terurut — gak perlu sort tambahan (index scan)
IN clauses	🟡 Sedang	BitMap scan sering lebih efisien daripada banyak index seek
Suffix matching (LIKE '%abc')	🔴 Tidak bisa	Gunakan trigram index atau full-text search
Pattern negasi (!=, NOT IN)	🔴 Tidak efektif	Biasanya full scan lebih cepat

Composite Index: Urutan Kolom Itu Krusial

Kesalahan paling umum: bikin index di kolom A dan B secara terpisah, padahal sering di-query barengan. Atau bikin composite index (A, B, C) tapi urutannya salah.

Aturan utama composite index:

1. Equality column first — kolom yang lo pake di = dulu, baru yang range
2. Most selective column first — kolom dengan cardinality tinggi (banyak nilai unik) duluan
3. Partial index �� kalo cuma butuh nge-index WHERE status = 'active', jangan index semua baris

-- ❌ Kurang optimal: index terpisah
CREATE INDEX idx_user_email ON users(email);
CREATE INDEX idx_user_status ON users(status);

-- ✅ Lebih optimal: composite index + partial
CREATE INDEX idx_user_active_email ON users(email)
  WHERE status = 'active';

Contoh practical: tabel orders dengan kolom user_id, status, created_at, amount. Query yang sering jalan: "cari order user 123 yang udah paid dalam 30 hari terakhir"

-- Index optimal
CREATE INDEX idx_orders_user_status_date ON orders(user_id, status, created_at DESC);

-- Query yang bisa memanfaatkan index di atas
EXPLAIN ANALYZE
SELECT * FROM orders
WHERE user_id = 123
  AND status = 'paid'
  AND created_at >= NOW() - INTERVAL '30 days'
ORDER BY created_at DESC;

-- Output: Index Only Scan (kalau kolom yang direturn ada di index)
-- Ket: sequential scan di kompleksitas 3 level index vs ribuan halaman heap

Membaca Query Plan

Ini skill paling penting: baca EXPLAIN ANALYZE. Tanpa ini, lo cuma nebak-nebak apakah index-nya dipake atau enggak.

-- Contoh output EXPLAIN ANALYZE
                                                      QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
 Index Only Scan using idx_orders_user_status_date on orders  (cost=0.43..12.65 rows=5 width=112)
   (actual time=0.023..0.035 rows=8 loops=1)
   Index Cond: ((user_id = 123) AND (status = 'paid'::text) AND (created_at >= (now() - '30 days'::interval)))
   Heap Fetches: 0
 Planning Time: 0.154 ms
 Execution Time: 0.052 ms

Yang perlu lo perhatiin:

• Index vs Seq Scan — kalo lo liat "Seq Scan on orders" walau udah bikin index, ada yang salah
• Index Only Scan �� ini holy grail: semua data yang direturn ada di index, gak perlu heap access. Heap Fetches: 0 konfirmasi ini
• rows — estimator vs actual. Kalo beda jauh (>10x), statistik tabel udah outdated. Jalanin ANALYZE
• cost �� startup cost + total cost dalam arbitrary units. Gak perlu hapal nilai exact, tapi bandingin antara plan yang satu vs yang lain
• actual time — real execution time dalam millisecond. Ini yang paling relevan

Advanced: Covering Index, Partial Index & Expression Index

1. Covering Index (INCLUDE) — Postgres 11+ mendukung INCLUDE untuk nambahin kolom ke index tanpa mempengaruhi B-Tree structure:

CREATE INDEX idx_orders_covering ON orders(user_id, status)
  INCLUDE (amount, created_at);
-- Query yang butuh user_id, status, amount, dan created_at bisa
-- pake Index Only Scan tanpa heap access

2. Partial Index — index yang cuma mencakup subset baris. Ukuran index bisa turun 80-90%:

CREATE INDEX idx_orders_paid ON orders(created_at)
  WHERE status = 'paid';
-- Cuma nge-index order berstatus 'paid' — sisanya diabaikan

3. Expression Index — index berdasarkan hasil fungsi atau ekspresi:

CREATE INDEX idx_users_lower_email ON users(LOWER(email));
-- Mempercepat: SELECT * FROM users WHERE LOWER(email) = '[email protected]';

4. Descending Index — berguna buat ORDER BY DESC:

CREATE INDEX idx_orders_created_desc ON orders(created_at DESC);
-- Mempercepat: SELECT * FROM orders ORDER BY created_at DESC LIMIT 10;

Monitoring Index Usage

Jangan asal bikin index — setiap index nambah overhead write. Monitor pake query built-in:

SELECT
  schemaname || '.' || relname,
  indexrelname,
  idx_scan,
  idx_tup_read,
  idx_tup_fetch,
  pg_size_pretty(pg_relation_size(indexrelid)) AS index_size
FROM pg_stat_user_indexes
WHERE schemaname = 'public'
ORDER BY idx_scan ASC;
-- Index dengan idx_scan = 0: UNUSED. Drop aja.

Di production, gue jalanin query ini mingguan. Kalo liat index yang gak pernah di-scan dalam 30 hari — di-drop. Kalo liat sequential scan di tabel besar — di-investigasi kenapa index-nya gak dipake (mungkin statistik outdated, atau query-nya suboptimal).

5 Real-World Performance Gains

Beberapa kasus yang gue handle beberapa bulan terakhir:

Kasus	Sebelum	Sesudah	Perubahan
Query laporan penjualan 6 bulan	12 detik	0.3 detik	Partial index + covering index
Login user (email lookup)	80ms	0.5ms	Expression index LOWER(email)
Cek ketersediaan produk	2.5 detik	0.05 detik	Composite index (status, stock, category)
Notification feed user	1.8 detik	0.02 detik	Descending index + partial WHERE
Batch update 50K rows	45 detik	8 detik	Drop unused index sebelum batch

Kesimpulan

B-Tree index adalah fondasi performa PostgreSQL. Dengan memahami struktur internal dan cara membaca query plan, lo bisa ngoptimalin query dari menit ke milidetik — tanpa perlu sharding, tanpa perlu caching layer tambahan.

Tiga langkah yang bisa lo terapin mulai besok: (1) audit index usage dengan pg_stat_user_indexes, (2) ganti multiple single-column index dengan composite + partial index, dan (3) biasain jalanin EXPLAIN ANALYZE sebelum nge-deploy query baru ke production.

Buat yang mau deepen skill database, baca juga arsitektur LTAP Postgres dan panduan data analytics dengan Postgres + Parquet + S3.