🔬 BACOT — Sesi 10:00 · Technical Exploration

Database Indexing: B-tree vs Hash vs GIN/GiST

Kategori: Database · Level: Intermediate–Advanced Tanggal: 2026-10-12

🎯 Tujuan Belajar

Setelah sesi ini, kamu bisa: 1. Menjelaskan struktur internal tiap tipe index (bukan cuma "pakai btree buat semua"). 2. Memilih tipe index berdasarkan access pattern + tipe data, bukan hafalan. 3. Membaca operator class di EXPLAIN dan tahu kenapa planner milih/menolak index. 4. Membuat index di produksi tanpa dump lock (CONCURRENTLY, partitioned approach). 5. Mengantisipasi failure mode: bloat, write amplification, planner mis-estimate.

📊 Ringkasan Singkat

Postgres punya 6 tipe index native: B-tree, Hash, GiST, SP-GiST, GIN, BRIN. Konsensus benchmark (2025): B-tree tetap default untuk OLTP (equality + range). Hash cuma menang tipis untuk pure equality dan kehilangan semua fleksibilitas → jarang worth it. GIN paling cepat untuk full-text & JSONB containment, tapi paling brutal soal bloat & write penalty. GiST/SP-GiST untuk geospatial. BRIN juara untuk tabel append-only raksasa. BRIN & B-tree paling forgiving di mixed read/write.

🏗️ Arsitektur & Alur Teknis

B-tree — struktur balanced tree multi-way

Index default. Setiap node = satu page 8KB (matched ke page I/O storage). Key terurut, lookup O(log n), mendukung:

=, <, <=, >, >=, BETWEEN, IN, IS NULL, IS NOT NULL
LIKE 'foo%'   (prefix-anchored, butuh operator class text_pattern_ops
               kalau locale bukan C)
ORDER BY ... (index bisa langsung nyuplai urutan, skip sort node)

Karena data terurut, B-tree bisa dipakai untuk ORDER BY dan LIMIT → top-N heapsort jadi index scan.

CREATE INDEX idx_orders_created ON orders (created_at DESC);
-- Query: ORDER BY created_at DESC LIMIT 20  → index scan, no sort

Hash — flat hash table di disk

Cuma =. Titik. Tidak ada range, tidak ada ORDER BY.

⚠️ Sebelum PG 10, hash index tidak WAL-logged → hilang setelah crash, tidak ikut replicasi. PG 10+ sudah WAL-logged dan crash-safe. Tapi tetap: latency gain vs B-tree kecil, dan kamu kehilangan semua fleksibilitas.

CREATE INDEX idx_sessions_token ON sessions USING HASH (token);
-- worth it HANYA kalau: kolom lebar (long text/uuid), akses 100% equality,
-- dan storage sangat terbatas.

GIN — Generalized Inverted Index

Bukan tree, tapi inverted index: satu entry per component value (token), menunjuk ke posting list of row IDs. Cocok untuk data yang satu nilainya berisi banyak sub-nilai:

array → @>, <@, &&
jsonb → @>, ?, ?|, ?&
tsvector (full-text) → @@
pg_trgm → operator LIKE '%...%'

-- Full-text search
CREATE INDEX idx_docs_tsv ON docs USING GIN (to_tsvector('indonesian', body));

-- JSONB containment
CREATE INDEX idx_events_meta ON events USING GIN (meta jsonb_path_ops);

GiST — Generalized Search Tree (infrastruktur, bukan single strategy)

Bukan satu index, tapi framework tempat berbagai indexing strategy ditanam. Lossy: bisa hasilkan false match, Postgres re-check baris aslinya. Dipakai untuk:

Geometri 2D (&&, @>, <@, <-> nearest-neighbor)
Range types (int4range, tsrange) → exclusion constraint
Full-text (alternatif GIN, lebih hemat tapi query lebih lambat)

-- Cegah double-booking pakai exclusion constraint
ALTER TABLE bookings ADD CONSTRAINT no_overlap
  EXCLUDE USING gist (room_id WITH =, period WITH &&);

SP-GiST — Space-partitioned GiST

Non-balanced tree: quadtree, k-d tree, radix tree (trie). Untuk data dengan natural clustering tapi tidak rata — misal prefix string panjang, titik 2D skewed.

BRIN — Block Range Index

Bukan tree per-row. Menyimpan ringkasan min/max per blok (default 128 page). Ukuran index ~ribuan kali lebih kecil dari B-tree. Kuncinya: data harus physical-correlated dengan kolom index (biasanya created_at di tabel append-only).

CREATE INDEX idx_logs_ts ON logs USING BRIN (created_at)
  WITH (pages_per_range = 32);
-- Tabel 1 miliar baris: BRIN index cuma puluhan MB,
-- B-tree bisa ratusan GB.

📄 Contoh Kode / Diagram

Diagram pilih index (decision flow)

Access pattern?
├── equality + range/order        → B-tree (default)
├── pure equality, storage kritikal → Hash (jarang)
├── array / jsonb / full-text     → GIN (read-heavy) | GiST (mixed r/w)
├── geospatial / range / exclusion → GiST
├── prefix/skewed tree-like       → SP-GiST
└── append-only huge + correlated → BRIN

Composite index & column order — baca btree sebagai "sorted directory"

CREATE INDEX idx_user_status_created
  ON orders (user_id, status, created_at);

-- ✅ Efektif: user_id (=), status (=), created_at (range terakhir)
SELECT * FROM orders
WHERE user_id = 42 AND status = 'paid' AND created_at > now() - interval '7 days';

-- ❌ TIDAK efektif: skip user_id (leftmost prefix rule)
SELECT * FROM orders WHERE status = 'paid';

Aturan praktis: equality dulu, range paling kanan, lalu paling kiri = kolom yang paling sering di-filter.

Partial index — index cuma subset yang relevan

-- 99% row status='done' & gak pernah di-query. Index cuma yg pending.
CREATE INDEX idx_orders_pending ON orders (created_at)
  WHERE status = 'pending';
-- Index 100x lebih kecil, write overhead cuma utk row pending.

Index-only scan (covering index) + INCLUDE

CREATE INDEX idx_orders_cover ON orders (user_id, created_at)
  INCLUDE (total, status);   -- PG 11+
-- Kalau visibility map bersih → Index Only Scan, gak nyentuh heap sama sekali.
VACUUM orders;  -- wajib biar visibility map updated

EXPLAIN — cek planner benar-benar pakai index

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE user_id = 42 AND created_at > now() - interval '7 days';
-- Perhatikan: Index Scan vs Seq Scan, rows estimated vs actual (kalau beda jauh
-- → statistik stale → ANALYZE / naikkan default_statistics_target)

⚖️ Trade-off & Pendekatan Alternatif

Aspek	B-tree	Hash	GIN	GiST	BRIN
Equality	✅	✅ (khusus)	✅ (containment)	varies	⚠️ lossy
Range	✅	❌	❌	✅	✅ (lossy)
ORDER BY	✅	❌	❌	❌	❌
Ukuran index	sedang	sedang	besar	besar	kecil
Build time	sedang	sedang	tinggi	tinggi	rendah
Write penalty	sedang	sedang	tertinggi	tinggi	rendah
Bloat setelah VACUUM	rendah	rendah	sedang-tinggi	sedang	rendah
Primary use	OLTP umum	equality-only	FTS/JSONB/array	geo/range	append-only besar

B-tree vs Hash — Benchmark 2025 (Wang, Mret via preprints.org 202511.2170): selisih latensi B-tree vs Hash untuk equality kecil, sementara B-tree mendukung range & ordering. Hash hampir selalu kalah secara trade-off → "hanya justify kalau storage sangat sempit & akses strict equality" [9].

GIN vs GiST untuk FTS/geo — GIN: query lebih cepat, index lebih besar, write penalty lebih berat. GiST: query lebih lambat, bloat lebih tahan, maintenance lebih ringan. Untuk workload mixed read-write → GiST lebih seimbang. Untuk read-heavy search → GIN.

Fast-update GIN option — fastupdate=on (default) menunda merge ke pending list → insert lebih cepat, tapi query bisa melambat & bloat naik. Tune dengan gin_pending_list_limit atau matikan fastupdate kalau write pattern churn.

Alternatif non-index — sebelum bikin index, tanyakan: apakah masalahnya missing index atau query jelek? Kadang rewrite query (hindari OR, hindari function di kolom ter-indeks, pakai EXISTS bukan IN subquery) lebih murah dari nambah index.

🏭 Use Case Produksi

E-commerce order lookup — B-tree composite (user_id, status, created_at DESC) + partial index WHERE status='pending'. Index pending kecil → cepat, hemat write.
Log/analytics tabel 500 juta+ baris — BRIN di created_at. B-tree bakal makan ratusan GB; BRIN puluhan MB dan cukup karena query selalu time-window.
Multi-tenant SaaS — GIN di jsonb meta untuk query atribut dinamis, dikombinasikan dengan RLS. Hati-hati bloat saat high update.
Booking system — GiST + EXCLUDE constraint untuk cegah overlap jadwal (tidak bisa dicapai pakai unique biasa).
Search produk katalog — GIN pg_trgm untuk substring %keyword%, karena B-tree cuma bisa prefix.

💥 Failure Mode Umum

Redundant / overlapping index — (user_id) + (user_id, status) → yang pertama jadi sampah, tapi tetap dibayar tiap write. Cek pg_stat_user_indexes.idx_scan = 0 → kandidat drop.
Write amplification — 8 index di satu tabel = setiap INSERT update 8 struktur. Tabel write-heavy dengan banyak index → throughput drop drastis. GIN paling parah.
GIN bloat — GIN & GiST menumpuk dead space bahkan setelah VACUUM. fastupdate=on bikin pending list numpuk. Butuh autovacuum agresif + REINDEX CONCURRENTLY periodik (PG 12+).
CREATE INDEX (non-concurrent) di produksi — ambil ACCESS EXCLUSIVE lock, menahan semua write sampai selesai. Tabel besar = outage.
CONCURRENTLY tetap bisa gagal / deadlock — masih butuh SHARE UPDATE EXCLUSIVE, dan kalau ada transaksi lama, bisa lock_timeout. Kalau gagal → index dibiarkan INVALID, harus drop & ulang.
Planner mis-estimate — statistik stale → rows estimated vs actual beda 1000x → planner milih seq scan. Fix: ANALYZE, naikkan default_statistics_target, atau CREATE STATISTICS untuk correlation antar kolom.
BRIN salah pakai — kalau data tidak physical-correlated (misal row di-update acak), BRIN jadi useless & malah false-positive scan.

Contoh aman bikin index di produksi

-- ❌ DILARANG di prod tabel besar
CREATE INDEX idx_big ON big_table (col);

-- ✅ Aman
SET lock_timeout = '5s';          -- bail cepat, jangan nunggu selamanya
CREATE INDEX CONCURRENTLY idx_big ON big_table (col);

-- Cek status (kalau INVALID → drop & ulang)
SELECT indexrelid::regclass, indisvalid, indisready
FROM pg_index WHERE indexrelid = 'idx_big'::regclass;

-- Rebuild index besar tanpa lock (PG 12+)
REINDEX INDEX CONCURRENTLY idx_big;

🧪 Latihan Praktis Kecil

-- 1. Bikin tabel uji + 1 juta baris
CREATE TABLE t (id serial, uid int, tags text[], meta jsonb, ts timestamptz);
INSERT INTO t (uid, tags, meta, ts)
SELECT random()*1000, ARRAY['a','b','c'][1+floor(random()*3)::int], 
       jsonb_build_object('k', (random()*10)::int),
       now() - (random()*365 || ' days')::interval
FROM generate_series(1, 1000000);

ANALYZE t;

-- 2. Bandingkan query SEBELUM index
EXPLAIN (ANALYZE, BUFFERS) 
SELECT * FROM t WHERE tags @> ARRAY['a'];

-- 3. Bikin GIN, ukur lagi
CREATE INDEX ON t USING GIN (tags);
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM t WHERE tags @> ARRAY['a'];

-- 4. Ukur ukuran index tiap tipe
CREATE INDEX ON t USING BRIN (ts);
SELECT indexrelid::regclass, pg_size_pretty(pg_relation_size(indexrelid))
FROM pg_index WHERE indrelid = 't'::regclass;

Tugas: catat nodes lost, buffers read, execution time sebelum vs sesudah tiap index. Perhatikan kenapa BRIN jauh lebih kecil.

🔑 Poin Kunci

B-tree = default. Kalau ragu, B-tree. 95% kasus OLTP.
Hash hampir selalu kalah — flexibility loss tidak sebanding gain kecil. Hindari kecuali alasan kuat.
GIN = inverted index untuk multi-value (array/jsonb/FTS). Cepat baca, mahal tulis.
GiST = framework untuk geo/range, lossy tapi lebih tahan bloat dari GIN.
BRIN = ringkasan per blok; menang di tabel append-only besar yang correlated. Salah pakai = sampah.
Leftmost prefix rule + equality-dulu-range-terakhir saat susun composite index.
Partial + covering (INCLUDE) sering lebih berdampak dari nambah index baru.
CONCURRENTLY wajib di prod; tetap bisa gagal → cek indisvalid.
Ukur dulu (EXPLAIN ANALYZE, pg_stat_user_indexes), jangan tebak.

DIKETAHUI: Semua sintaks & fitur di atas sesuai dokumentasi resmi PostgreSQL 18 (indexes-types.html, sql-createindex.html). DIINFERENSI: Ranking throughput/bloat mengacu review benchmark 2025 (preprints.org 202511.2170) yang mengonsolidasi studi Wang, Mret, Zolotukhina, Percona — bukan benchmark tunggal teruji sendiri. BELUM PASTI: Angka spesifik (berapa % lambat) sangat workload-dependent; jangan jadikan patokan tanpa test sendiri.

🔍 Eksplorasi Lanjut

Bloom index & index-only scan pg 18 I/O limits — extension bloom untuk multi-kolom equality murah.
HOT updates & fillfactor — gimana update non-indexed column menghindari index rewrite.
BRIN dengan minmax_multi (fitur lebih baru) — dukungan multi-value range.
pg_stat_statements + index advisor — deteksi missing index otomatis dari slow query log.
HNSW/IVFFlat via pgvector — "index" untuk vector similarity, konsep tetangga GIN/GiST tapi ANN.
HypoPG — cek "kalau saya bikin index X, apakah planner pakai?" tanpa bikin index aslinya.

🔗 Sumber: [1] PostgreSQL Docs. "Index Types" — postgresql.org/docs/current/indexes-types.html [2] PostgreSQL Docs. "CREATE INDEX" (CONCURRENTLY, lock semantics) — postgresql.org/docs/current/sql-createindex.html [3] Citus/Percona. "A Tour of Postgres Index Types" — citusdata.com/blog/2017/10/17/tour-of-postgres-index-types/ [4] Preprints.org 202511.2170. "Indexing in PostgreSQL: Performance Evaluation and Use Cases" (2025) — konsolidasi benchmark B-tree/Hash/GIN/GiST/BRIN [5] Alex Stoica. "CREATE INDEX CONCURRENTLY and what locks it requires" — alexstoica.com/blog/create-index-concurrently-locks