Pengindeksan untuk Skala

Intuisi B-tree, covering index, dan biaya penulisan yang dibayar untuk kecepatan baca.

Daftar isi

Indeks adalah struktur data tambahan yang menyimpan rujukan terurut ke baris tabel, sehingga pencarian baris tertentu tidak perlu memindai seluruh tabel. Topik ini membahas intuisi struktur B-tree, perhitungan kedalaman pohon pada berbagai jumlah baris, covering index untuk pembacaan tanpa menyentuh tabel utama, dan biaya penulisan yang dibayar atas kecepatan baca tersebut.

Biaya pencarian tanpa indeks#

Query yang menyaring tabel tanpa indeks memaksa basis data membaca seluruh baris satu per satu, dan pola ini disebut pemindaian tabel penuh. Pada tabel dengan seribu baris, pemindaian tersebut terasa seketika. Pada tabel dengan ratusan juta baris, operasi yang sama berarti membaca hampir semua halaman penyimpanan, padahal hanya segelintir baris yang dicari. Latensi query ikut membesar berbanding lurus dengan jumlah barisnya, dan kebutuhan memori serta penyimpanannya ikut membesar pula.

Dampaknya juga menular ke query lain. Setiap pemindaian penuh menambah beban pembacaan pada penyimpanan yang sama, sehingga query yang tadinya sehat ikut melambat. Query detail pembacaan sensor menurut pengenalnya, yang awalnya selesai dalam hitungan milidetik, dapat memakan waktu berdetik begitu tabel pembacaan membesar tanpa indeks.

Basis data relasional menyelesaikan masalah ini dengan indeks, yaitu struktur terurut yang menunjuk langsung ke baris. Cara kerjanya mirip mencari kata pada daftar isi buku, yaitu melompat ke titik yang tepat pada urutan, bukan membaca buku dari halaman pertama. Struktur yang paling umum dipakai indeks basis data adalah B-tree, yang dibahas pada bagian berikutnya.

B-tree dan kedalaman pohon#

B-tree adalah pohon seimbang dengan fanout besar, yaitu banyaknya cabang dari satu simpul. Setiap simpul menyimpan kunci terurut beserta rujukan ke simpul turunannya, dan ukurannya diselaraskan dengan satu halaman penyimpanan, misalnya 8 kB pada PostgreSQL, sehingga satu pembacaan halaman membawa banyak kunci sekaligus. Pencarian satu baris bergerak dari akar ke daun, dan jumlah pembacaan simpulnya sama dengan kedalaman pohon.

Hubungan fanout dengan kedalaman mudah dihitung. Dengan fanout $F$ dan $n$ baris, kedalaman minimum adalah bilangan bulat terkecil $L$ yang memenuhi $F^L \ge n$ , yaitu $\lceil \log_F n \rceil$ . Skrip berikut menghitungnya untuk beberapa kombinasi jumlah baris dan fanout.

python simulasi-btree.py

"""Menghitung kedalaman B-tree untuk berbagai jumlah baris.

Model yang disederhanakan: setiap tingkat pohon memperbanyak cakupan
sebesar FANOUT, sehingga kedalaman minimum adalah bilangan bulat
terkecil L yang memenuhi FANOUT**L >= jumlah baris. Pencarian satu
baris pada indeks berbayang sebesar L membutuhkan paling banyak L
pembacaan simpul.
"""

FANOUT = (50, 200)
BARIS = (1_000, 100_000, 10_000_000, 1_000_000_000)


def kedalaman(baris: int, fanout: int) -> int:
    tingkat = 0
    cakupan = 1
    while cakupan < baris:
        cakupan *= fanout
        tingkat += 1
    return tingkat


header = f"{'baris':>13} | " + " | ".join(f"fanout {f}" for f in FANOUT)
print(header)
print("-" * len(header))
for n in BARIS:
    kolom = " | ".join(f"{kedalaman(n, f):>9}" for f in FANOUT)
    print(f"{n:>13} | {kolom}")

text Keluaran

        baris | fanout 50 | fanout 200
--------------------------------------
         1000 |         2 |         2
       100000 |         3 |         3
     10000000 |         5 |         4
   1000000000 |         6 |         4

Tabel keluaran memperlihatkan sifat utama B-tree, yaitu kedalaman yang bertambah sangat lambat. Dengan fanout 200, satu miliar baris dicapai hanya dalam empat pembacaan simpul, dan akar pohon biasanya sudah tersimpan di cache memori sehingga biaya sesungguhnya berada pada beberapa halaman bawahnya. Inilah alasan pencarian berindeks terasa hampir tetap meskipun data terus tumbuh, sedangkan pemindaian tabel penuh tumbuh berbanding lurus dengan jumlah barisnya.

Covering index#

Covering index adalah indeks yang memuat seluruh kolom yang dibutuhkan sebuah query, sehingga query dijawab dari indeks tanpa membaca tabel utamanya. Pencarian biasa berhenti pada daun indeks untuk mengambil rujukan baris, lalu membaca tabel satu kali lagi. Bila kolom yang dibaca tersedia di daun indeks, langkah kedua itu tidak pernah terjadi, sehingga jumlah pembacaan berkurang dan pola bacanya menjadi lebih teratur.

Contoh berikut menggunakan tabel pembacaan sensor. Indeks gabungan pada kolom penyaring, ditambah kolom pembacaan yang ditaruh di daun indeks, membuat query harian per sensor dapat dijawab dari indeks itu sendiri.

sql Contoh: covering index untuk pembacaan sensor

-- tidak-dijalankan
-- Indeks gabungan pada kolom penyaring ditambah kolom pembacaan di daun indeks
CREATE INDEX idx_sensor_sensor_waktu
    ON pembacaan_sensor (sensor_id, waktu_baca) INCLUDE (nilai_suhu);

-- Query berikut dapat dijawab sepenuhnya dari indeks di atas
SELECT waktu_baca, nilai_suhu
FROM pembacaan_sensor
WHERE sensor_id = 42
  AND waktu_baca >= '2026-11-01'
ORDER BY waktu_baca DESC;

PostgreSQL menyebut teknik ini index-only scan dan menyediakan klausa INCLUDE yang menaruh kolom tambahan di daun indeks. Kolom pada INCLUDE tidak dapat dipakai untuk menyaring, tetapi cukup untuk dibaca. Harganya tetap ada, yaitu indeks yang membawa lebih banyak kolom menjadi lebih lebar dan lebih mahal untuk ditulis, sehingga kolom pada INCLUDE dipilih seperlunya. Teknik ini paling bermanfaat pada query yang dibaca terus-menerus, karena seluruh pola bacanya berhenti pada struktur yang jauh lebih kecil daripada tabelnya.

Biaya penulisan#

Kecepatan baca pada indeks dibayar pada waktu tulis. Setiap baris baru menambah entri pada setiap indeks tabelnya, dan setiap pembaruan kolom yang terindeks menulis ulang entri indeksnya. Pembaruan yang menyentuh kolom kunci indeks lebih mahal lagi, karena posisi entri dalam urutan pohon ikut berpindah. Tabel dengan empat indeks membayar empat penulisan struktur tambahan untuk setiap baris baru, ditambah ruang penyimpanan untuk keempat struktur itu. Biaya ini tidak terasa pada trafik kecil, tetapi menjadi batas atas throughput tulis ketika beban membesar.

Karena itu jumlah indeks ditetapkan berdasarkan pola baca nyata. Tabel yang padat tulisannya, misalnya log sensor, memakai indeks sesedikit mungkin, sedangkan tabel yang sering dibaca dengan pola penyaringan tetap mendapat indeks untuk pola tersebut. Indeks yang tidak pernah dipakai sebaiknya dihapus karena indeks itu hanya menambah biaya tulis tanpa mengembalikan apa pun.

Kesalahan umum#

Tiga kesalahan berikut paling sering muncul ketika indeks baru ditambahkan.

Membuat indeks satu kolom untuk setiap kolom yang mungkin disaring. Kebanyakan indeks itu tidak pernah dipakai, dan perbaikannya adalah indeks gabungan yang mengikuti pola query, misalnya (sensor_id, waktu_baca). Urutan kolom pada indeks gabungan juga menentukan, karena kolom penyaring yang paling ketat diletakkan lebih dahulu.
Membungkus kolom dengan fungsi pada sisi penyaring, misalnya YEAR(waktu_baca) = 2026. Indeks pada kolom aslinya tidak terpakai, dan perbaikannya adalah menulis syarat sebagai rentang, misalnya waktu_baca >= '2026-01-01' AND waktu_baca < '2027-01-01'.
Mengindeks kolom dengan sedikit nilai berbeda sebagai satu-satunya kolom, misalnya kolom status dengan tiga nilai. Selektivitasnya rendah sehingga basis data sering memilih pemindaian penuh, dan perbaikannya adalah menggabungkan kolom itu dengan kolom yang selektif pada indeks yang sama. Pengecualiannya adalah indeks parsial pada satu nilai yang memang sering dicari, yang tetap kecil dan bermanfaat.
Menambah indeks tanpa mengukur pengaruhnya pada tulisan. Tabel yang padat tulisan dapat melambat jauh setelah beberapa indeks baru, dan perbaikannya adalah menguji perubahan tersebut dengan beban tulis yang setara sebelum dipasang di production.

Ringkasan#

B-tree dengan fanout besar membuat kedalaman pohon bertambah sangat lambat, sehingga pencarian satu baris di antara miliaran baris hanya membutuhkan beberapa pembacaan simpul.
Covering index menyimpan kolom yang dibaca pada daun indeks, sehingga query tertentu dijawab tanpa menyentuh tabel utama.
Setiap indeks menambah biaya tulis dan penyimpanan, sehingga jumlah dan bentuknya ditetapkan dari rencana eksekusi, bukan dari prasangka.

Referensi#

Chapter 11. Indexes — PostgreSQL — Dokumentasi resmi indeks PostgreSQL, termasuk index-only scan dan covering index.
65.1. B-Tree Indexes — PostgreSQL — Dokumentasi resmi struktur B-tree PostgreSQL, dari simpul daun hingga pemecahan halaman.