Dua chapter pertama menampilkan kata btree berulang kali — di pg_indexes, di output \d, dan di index penopang primary key — tanpa pernah menjelaskannya. Kata itu adalah nama tipe index yang menjadi pilihan default CREATE INDEX, dan alasan ia menjadi default bukan kebetulan: B-tree melayani hampir semua pola pencarian yang umum, dari kesetaraan, perbandingan, rentang, sampai pengurutan hasil. Chapter ini membedah bentuk strukturnya, daftar operator yang dilayaninya, dan batas tegasnya pada pola LIKE. Demonstrasi tetap memakai tabel pelanggan 1000 baris, dibangun ulang di sini agar chapter ini berdiri sendiri:

sql buat-tabel.sql 
-- Tabel contoh chapter ini (domain yang sama dengan chapter Konsep Index).
CREATE TABLE pelanggan (
    id       integer PRIMARY KEY,
    nama     text NOT NULL,
    email    text NOT NULL,
    kota     text NOT NULL,
    kategori text NOT NULL,
    saldo    numeric(12,2) NOT NULL,
    aktif    boolean NOT NULL
);

INSERT INTO pelanggan (id, nama, email, kota, kategori, saldo, aktif)
SELECT
    g,
    'Pelanggan ' || lpad(g::text, 4, '0'),
    'pelanggan' || lpad(g::text, 4, '0') || '@example.com',
    (ARRAY['Jakarta','Bandung','Surabaya','Medan','Denpasar'])[1 + (g - 1) / 200],
    (ARRAY['reguler','silver','gold'])[1 + g % 3],
    ((g - 1) * 1000 + 500)::numeric(12,2),
    (g % 10 <> 0)
FROM generate_series(1, 1000) AS g;

ANALYZE pelanggan;

Output yang Dihasilkan:

text 
CREATE TABLE
INSERT 0 1000
ANALYZE

Pohon Terurut yang Selalu Seimbang #

B-tree adalah pohon pencarian seimbang (balanced tree): struktur berlapis yang menyimpan entri terurut, dengan janji bahwa setiap halaman daun berada pada kedalaman yang sama dari akar. Bentuknya seperti ini:

Mekanismenya bekerja dalam tiga lapis. Halaman daun menyimpan entri-entri (nilai kolom, ctid) dalam keadaan terurut penuh — entri Pelanggan 0001 selalu bersebelahan dengan Pelanggan 0002. Setiap halaman daun terhubung dua arah dengan tetangganya, sehingga PostgreSQL dapat berjalan maju dan mundur untuk membaca rentang tanpa kembali ke akar. Halaman internal dan akar tidak menyimpan data; keduanya hanya menyimpan batas-batas nilai sebagai penunjuk arah — “nilai di bawah 250? turun ke kiri; di atasnya? turun ke kanan”.

Karena semua daun berada di kedalaman yang sama, mencari satu nilai dari 1000 entri maupun dari satu miliar entri hanya menuntut jumlah lompatan halaman yang sama besarnya: tiga sampai empat kali untuk tabel berukuran wajar. Pertumbuhan biaya pencarian mengikuti logaritma jumlah entri — menambah data sepuluh kali lipat hanya menambah satu lapisan pohon.

Operator yang Dilayani B-tree #

Daftar kemampuan B-tree dapat dirangkum dalam satu tabel:

Pola kondisiDilayani?Contoh
Kesetaraan =YaWHERE nama = 'Pelanggan 0420'
Perbandingan <, <=, >, >=YaWHERE saldo >= 420000
Rentang BETWEENYaWHERE saldo BETWEEN 420000 AND 440000
LIKE 'awalan%' (jangkar kiri)YaWHERE nama LIKE 'Pelanggan 04%'
LIKE '%akhiran' (jangkar kanan)TidakWHERE nama LIKE '%0042'
ORDER BY kolom indeksYaORDER BY saldo tanpa sort ulang

Dua baris terakhir itu yang paling sering mengejutkan pemula — dan keduanya kita buktikan dengan EXPLAIN sebentar lagi. Membuat kedua index B-tree di tabel contoh cukup dua perintah:

sql buat-index-btree.sql 
-- USING btree boleh ditulis eksplisit...
CREATE INDEX idx_pelanggan_nama ON pelanggan USING btree (nama);

-- ...atau ditiadakan: btree adalah tipe default CREATE INDEX.
CREATE INDEX idx_pelanggan_saldo ON pelanggan (saldo);

-- pg_indexes mencatat keduanya sebagai btree.
SELECT indexname, indexdef
FROM pg_indexes
WHERE schemaname = 'public' AND tablename = 'pelanggan'
ORDER BY indexname;

-- Collation database menentukan apakah LIKE 'awalan%' dapat memakai btree
-- (dibahas pada bagian LIKE di bawah).
SELECT datcollate FROM pg_database WHERE datname = current_database();

Output yang Dihasilkan:

text 
CREATE INDEX
CREATE INDEX
      indexname      |                                 indexdef                                 
---------------------+--------------------------------------------------------------------------
 idx_pelanggan_nama  | CREATE INDEX idx_pelanggan_nama ON public.pelanggan USING btree (nama)
 idx_pelanggan_saldo | CREATE INDEX idx_pelanggan_saldo ON public.pelanggan USING btree (saldo)
 pelanggan_pkey      | CREATE UNIQUE INDEX pelanggan_pkey ON public.pelanggan USING btree (id)
(3 rows)

 datcollate 
------------
 C
(1 row)

Perhatikan kolom indexdef pada output: perintah pertama yang menuliskan USING btree secara eksplisit dan perintah kedua yang tidak menuliskannya menghasilkan definisi yang persis sama — btree memang default-nya. Baris terakhir output menunjukkan datcollate bernilai C, artinya database latihan ini memakai collation C yang mengurutkan teks berdasarkan urutan byte; fakta ini akan menjadi penting di bagian LIKE.

Pencarian Kesetaraan #

Kasus paling dasar: mencari satu pelanggan berdasarkan nama. Hasil query-nya satu baris:

sql query-sama.sql 
-- Pencarian satu pelanggan berdasarkan nama: kesetaraan murni.
SELECT id, nama, kota, kategori, saldo
FROM pelanggan
WHERE nama = 'Pelanggan 0420';

Output yang Dihasilkan:

text 
 id  |      nama      |   kota   | kategori |   saldo   
-----+----------------+----------+----------+-----------
 420 | Pelanggan 0420 | Surabaya | reguler  | 419500.00
(1 row)

Rencana di balik query itu terlihat lewat EXPLAIN:

sql explain-sama.sql 
-- Rencana pencarian kesetaraan: turun dari akar ke satu entri daun.
EXPLAIN
SELECT id, nama, kota, kategori, saldo
FROM pelanggan
WHERE nama = 'Pelanggan 0420';

Output yang Dihasilkan:

text 
                                     QUERY PLAN                                      
-------------------------------------------------------------------------------------
 Index Scan using idx_pelanggan_nama on pelanggan  (cost=0.28..8.29 rows=1 width=39)
   Index Cond: (nama = 'Pelanggan 0420'::text)
(2 rows)

Baris Index Scan using idx_pelanggan_nama mengumumkan index yang terpakai. Baris Index Cond: (nama = 'Pelanggan 0420') menegaskan kondisi tersebut menjadi kondisi pencarian: PostgreSQL membandingkan nilai yang dicari dengan batas-batas di halaman internal, menuruni pohon tiga lapis, dan mendarat tepat di entri daun yang cocok — lalu melompat ke heap lewat ctid. Total halaman yang disentuh: beberapa halaman index dan satu baris tabel. Bandingkan dengan sequential scan yang menyentuh seluruh 1000 baris demi menemukan satu.

Pencarian Rentang dan Bonus Urutan #

Kekuatan kedua B-tree: rentang nilai. Karena entri daun terurut dan halaman-halaman daun saling terhubung, rentang dibaca dengan mendarat di batas bawah lalu berjalan ke kanan sampai batas atas. Berikut pelanggan dengan saldo antara 420.000 dan 440.000:

sql query-rentang.sql 
-- Pencarian rentang: semua pelanggan dengan saldo di jendela tertentu,
-- hasil diurutkan berdasarkan saldo.
SELECT id, nama, saldo
FROM pelanggan
WHERE saldo BETWEEN 420000 AND 440000
ORDER BY saldo;

Output yang Dihasilkan:

text 
 id  |      nama      |   saldo   
-----+----------------+-----------
 421 | Pelanggan 0421 | 420500.00
 422 | Pelanggan 0422 | 421500.00
 423 | Pelanggan 0423 | 422500.00
 424 | Pelanggan 0424 | 423500.00
 425 | Pelanggan 0425 | 424500.00
 426 | Pelanggan 0426 | 425500.00
 427 | Pelanggan 0427 | 426500.00
 428 | Pelanggan 0428 | 427500.00
 429 | Pelanggan 0429 | 428500.00
 430 | Pelanggan 0430 | 429500.00
 431 | Pelanggan 0431 | 430500.00
 432 | Pelanggan 0432 | 431500.00
 433 | Pelanggan 0433 | 432500.00
 434 | Pelanggan 0434 | 433500.00
 435 | Pelanggan 0435 | 434500.00
 436 | Pelanggan 0436 | 435500.00
 437 | Pelanggan 0437 | 436500.00
 438 | Pelanggan 0438 | 437500.00
 439 | Pelanggan 0439 | 438500.00
 440 | Pelanggan 0440 | 439500.00
(20 rows)

Rencana eksekusinya menyimpan satu kejutan yang menyenangkan:

sql explain-rentang.sql 
-- Rencana pencarian rentang: dua batas menjadi satu kondisi index,
-- dan urutan index membuat ORDER BY saldo tidak memerlukan node Sort.
EXPLAIN
SELECT id, nama, saldo
FROM pelanggan
WHERE saldo BETWEEN 420000 AND 440000
ORDER BY saldo;

Output yang Dihasilkan:

text 
                                      QUERY PLAN                                       
---------------------------------------------------------------------------------------
 Index Scan using idx_pelanggan_saldo on pelanggan  (cost=0.28..8.70 rows=21 width=25)
   Index Cond: ((saldo >= '420000'::numeric) AND (saldo <= '440000'::numeric))
(2 rows)

Mari kita baca rencana itu baris per baris:

  1. Index Scan using idx_pelanggan_saldo: rentang dilayani index pada kolom saldo.
  2. Index Cond: ((saldo >= '420000') AND (saldo <= '440000')): BETWEEN diterjemahkan menjadi dua batas perbandingan, dan keduanya menjadi kondisi pencarian — PostgreSQL mendarat di entri pertama yang >= 420000 lalu berjalan menyusuri daun sampai melewati 440000.
  3. Tidak ada node Sort: inilah kejutannya. Klausa ORDER BY saldo tidak menuntut pengurutan ulang karena baris keluar dari index sudah dalam urutan saldo. Pada tabel besar, penghematan ini sering menjadi selisih yang paling terasa.

LIKE Hanya Dilayani dari Kiri #

Kasus terakhir adalah LIKE. Pola 'awalan%' berjangkar kiri: awal teks diketahui, sehingga pola itu dapat diterjemahkan menjadi rentang — semua nama mulai dari 'Pelanggan 04' sampai sebelum 'Pelanggan 05'. Sebaliknya, pola '%akhiran' tidak menetapkan di mana nilai dimulai, dan pohon terurut tidak punya titik mendarat. Bukti dari kedua-duanya:

sql explain-like.sql 
-- LIKE berjangkar kiri: 'awalan%' dapat diterjemahkan menjadi rentang
-- sehingga index terpakai.
EXPLAIN
SELECT id
FROM pelanggan
WHERE nama LIKE 'Pelanggan 04%';

-- LIKE berjangkar kanan: '%akhiran' tidak bisa menjadi rentang,
-- index harus diabaikan.
EXPLAIN
SELECT id
FROM pelanggan
WHERE nama LIKE '%0042';

Output yang Dihasilkan:

text 
                                      QUERY PLAN                                       
---------------------------------------------------------------------------------------
 Index Scan using idx_pelanggan_nama on pelanggan  (cost=0.28..11.53 rows=101 width=4)
   Index Cond: ((nama >= 'Pelanggan 04'::text) AND (nama < 'Pelanggan 05'::text))
   Filter: (nama ~~ 'Pelanggan 04%'::text)
(3 rows)

                        QUERY PLAN                        
----------------------------------------------------------
 Seq Scan on pelanggan  (cost=0.00..25.50 rows=1 width=4)
   Filter: (nama ~~ '%0042'::text)
(2 rows)

Rencana pertama memperlihatkan terjemahan rentang secara terbuka: Index Cond: ((nama >= 'Pelanggan 04') AND (nama < 'Pelanggan 05')), disertai Filter: (nama ~~ 'Pelanggan 04%') untuk menyaring baris yang lolos rentang tapi tidak memenuhi pola penuhnya. Rencana kedua jatuh kembali ke Seq Scan on pelanggan — index B-tree sama sekali tidak terpakai untuk pola berjangkar kanan.

Kesetaraan, rentang, dan urutan — tiga kemampuan itu berasal dari satu sifat yang sama: entri B-tree terurut. Bayangkan sekarang kasus yang hanya butuh kesetaraan murni, tanpa rentang dan tanpa urutan. Adakah struktur yang lebih ramping untuk pekerjaan itu? Ada, dan namanya hash — chapter berikutnya.

Referensi #

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

buat-index-btree.sql

Unduh berkas
sql 
-- USING btree boleh ditulis eksplisit...
CREATE INDEX idx_pelanggan_nama ON pelanggan USING btree (nama);

-- ...atau ditiadakan: btree adalah tipe default CREATE INDEX.
CREATE INDEX idx_pelanggan_saldo ON pelanggan (saldo);

-- pg_indexes mencatat keduanya sebagai btree.
SELECT indexname, indexdef
FROM pg_indexes
WHERE schemaname = 'public' AND tablename = 'pelanggan'
ORDER BY indexname;

-- Collation database menentukan apakah LIKE 'awalan%' dapat memakai btree
-- (dibahas pada bagian LIKE di bawah).
SELECT datcollate FROM pg_database WHERE datname = current_database();

buat-tabel.sql

Unduh berkas
sql 
-- Tabel contoh chapter ini (domain yang sama dengan chapter Konsep Index).
CREATE TABLE pelanggan (
    id       integer PRIMARY KEY,
    nama     text NOT NULL,
    email    text NOT NULL,
    kota     text NOT NULL,
    kategori text NOT NULL,
    saldo    numeric(12,2) NOT NULL,
    aktif    boolean NOT NULL
);

INSERT INTO pelanggan (id, nama, email, kota, kategori, saldo, aktif)
SELECT
    g,
    'Pelanggan ' || lpad(g::text, 4, '0'),
    'pelanggan' || lpad(g::text, 4, '0') || '@example.com',
    (ARRAY['Jakarta','Bandung','Surabaya','Medan','Denpasar'])[1 + (g - 1) / 200],
    (ARRAY['reguler','silver','gold'])[1 + g % 3],
    ((g - 1) * 1000 + 500)::numeric(12,2),
    (g % 10 <> 0)
FROM generate_series(1, 1000) AS g;

ANALYZE pelanggan;

explain-like.sql

Unduh berkas
sql 
-- LIKE berjangkar kiri: 'awalan%' dapat diterjemahkan menjadi rentang
-- sehingga index terpakai.
EXPLAIN
SELECT id
FROM pelanggan
WHERE nama LIKE 'Pelanggan 04%';

-- LIKE berjangkar kanan: '%akhiran' tidak bisa menjadi rentang,
-- index harus diabaikan.
EXPLAIN
SELECT id
FROM pelanggan
WHERE nama LIKE '%0042';

explain-rentang.sql

Unduh berkas
sql 
-- Rencana pencarian rentang: dua batas menjadi satu kondisi index,
-- dan urutan index membuat ORDER BY saldo tidak memerlukan node Sort.
EXPLAIN
SELECT id, nama, saldo
FROM pelanggan
WHERE saldo BETWEEN 420000 AND 440000
ORDER BY saldo;

explain-sama.sql

Unduh berkas
sql 
-- Rencana pencarian kesetaraan: turun dari akar ke satu entri daun.
EXPLAIN
SELECT id, nama, kota, kategori, saldo
FROM pelanggan
WHERE nama = 'Pelanggan 0420';

query-rentang.sql

Unduh berkas
sql 
-- Pencarian rentang: semua pelanggan dengan saldo di jendela tertentu,
-- hasil diurutkan berdasarkan saldo.
SELECT id, nama, saldo
FROM pelanggan
WHERE saldo BETWEEN 420000 AND 440000
ORDER BY saldo;

query-sama.sql

Unduh berkas
sql 
-- Pencarian satu pelanggan berdasarkan nama: kesetaraan murni.
SELECT id, nama, kota, kategori, saldo
FROM pelanggan
WHERE nama = 'Pelanggan 0420';