Menggunakan indeks dan melakukan pemindaian tabel adalah dua pendekatan mendasar untuk mengakses data dalam database, masing-masing dengan trade-off yang berbeda tergantung pada situasinya.
Indeks dalam database adalah struktur data yang memungkinkan pencarian yang lebih cepat dengan memungkinkan sistem untuk dengan cepat menemukan baris tanpa memindai setiap baris dalam tabel. Sebagian besar database relasional menggunakan struktur pohon B+ untuk indeks, yang mengatur kunci dan pointer dalam bentuk pohon. Hal ini memungkinkan pencarian, penyisipan, dan penghapusan dalam kompleksitas waktu logaritmik $$ o (\ log n) $$, yang biasanya jauh lebih cepat daripada memindai seluruh tabel dengan kompleksitas $$ o (n) $$. Indeks dapat dikelompokkan atau tidak dikelompokkan, dengan indeks berkerumun menyimpan data dalam pesanan yang diurutkan secara fisik, meningkatkan kinerja pemindaian rentang dengan biaya overhead tambahan pada modifikasi data. Indeks juga dapat berupa komposit, parsial, difilter, atau berbasis hash, disetel untuk pola kueri tertentu.
Sebaliknya, pemindaian tabel (atau pemindaian tabel penuh) membaca setiap baris di tabel secara berurutan, terlepas dari selektivitas kueri. Ini melibatkan pemindaian semua blok data tabel dan sering dianggap sebagai metode akses paling mahal karena memproses lebih banyak data daripada yang diperlukan. Namun, pemindaian tabel dapat berkinerja baik dalam kasus -kasus tertentu. Misalnya, ketika kueri mengambil sebagian besar baris, overhead menggunakan indeks (yang sering membutuhkan pencarian tambahan untuk baris yang sebenarnya) dapat melebihi biaya pemindaian seluruh tabel sekali. Pemindaian tabel dapat memanfaatkan pembacaan multi-blok, yang memungkinkan membaca potongan data besar dengan operasi I/O yang lebih sedikit, sehingga mengurangi latensi dibandingkan dengan membaca banyak blok individual secara acak diperlukan oleh pemindaian indeks.
Satu trade-off utama melibatkan selektivitas dan ukuran kumpulan data yang dikembalikan oleh kueri. Jika kueri menyaring ke sejumlah kecil baris (selektivitas tinggi), indeks umumnya mengungguli pemindaian tabel karena mereka hanya perlu mengakses data yang relevan. Tetapi karena persentase baris yang dikembalikan meningkat, biaya pemindaian indeks meningkat karena beberapa pencarian utama mungkin diperlukan, dan mesin basis data harus melakukan operasi I/O acak tambahan. Pada beberapa ambang batas, seringkali sekitar 10-20% dari baris tabel tetapi tergantung pada lebar data dan perangkat keras, pemindaian tabel penuh menjadi lebih efisien. Ini karena biaya pemindaian tetap konstan terlepas dari selektivitas, cukup membaca tabel secara berurutan sekali.
Pemindaian indeks biasanya membaca lebih sedikit halaman daripada pemindaian tabel ketika kolom tertutup lebih sedikit atau lebih kompak daripada baris tabel penuh. Misalnya, indeks mungkin hanya menyertakan kolom yang diindeks tanpa data baris tabel penuh, membuatnya lebih tipis dan memungkinkan lebih banyak baris agar sesuai pada setiap halaman database. Ini mengurangi overhead I/O saat memindai indeks dibandingkan dengan memindai seluruh data tabel. Selain itu, beberapa indeks dapat disaring (indeks parsial) untuk mengecualikan baris yang tidak relevan, lebih lanjut mengurangi jejak pemindaian.
Di sisi lain, pemindaian meja penuh menulis lebih sedikit beban di sisi pemeliharaan basis data. Indeks memperkenalkan overhead selama operasi modifikasi data seperti memasukkan, memperbarui, dan menghapus. Setiap perubahan pada tabel membutuhkan indeks memperbarui, kadang -kadang mengarah pada peningkatan latensi dan penyimpanan overhead terutama jika banyak indeks ada di atas meja. Overhead ini juga dapat mempengaruhi konkurensi dan mengarah pada pertengkaran di lingkungan penulisan yang berat. Dengan demikian, pemindaian tabel, yang hanya membaca data dalam urutan alami tanpa pemeliharaan struktur tambahan, hindari biaya ini.
Pertimbangan penting lainnya adalah efek dari karakteristik caching dan perangkat keras. Pemindaian tabel manfaat dari I/O berurutan dan prefetching, memungkinkan sistem untuk membaca beberapa blok berdekatan secara efisien, seringkali dari memori jika di -cache. Sebaliknya, pemindaian indeks mengeluarkan I/O acak untuk mengambil blok data yang berbeda, terutama jika pemindaian indeks harus mencari pointer baris ke dalam penyimpanan tumpukan. Ini dapat membuat pemindaian indeks lebih lambat pada sistem dengan kinerja I/O acak disk yang lebih lambat, meskipun SSD dan kumpulan memori besar mempersempit celah ini. Situasi ini juga dapat tergantung pada spesifik seperti paralelisme dan kemampuan multi-threading dari mesin basis data, di mana pemindaian tabel paralel dapat secara signifikan meningkatkan throughput.
Selain itu, fragmentasi internal dan tata letak penyimpanan fisik mempengaruhi pertukaran kinerja. Pemindaian tabel pada meja yang terorganisir mungkin menderita catatan yang diteruskan, di mana baris telah dipindahkan ke halaman yang berbeda karena pembaruan, efisiensi pemindaian yang memburuk. Indeks berkerumun, yang menyimpan data yang diurutkan berdasarkan kunci, dapat menghindari masalah ini dan kadang -kadang membuat "pemindaian tabel" setara dengan pemindaian indeks berkerumun. Namun, manfaatnya datang dengan biaya pemesanan ulang yang mahal selama churn data berat.
Dari perspektif Query Optimizer, keputusan antara pemindaian indeks dan pemindaian tabel biasanya dibuat oleh model estimasi berbasis biaya, dengan mempertimbangkan statistik tentang distribusi data, jumlah baris, dan biaya perangkat keras. Pengoptimal menyeimbangkan biaya CPU, I/O, dan memori untuk memilih jalur akses yang paling efisien. Keputusan ini dapat dipengaruhi oleh faktor -faktor seperti memori yang tersedia, keadaan caching, dan pola kueri. Tidak ada ambang batas tetap antara kapan menggunakan satu atau yang lain; Titik crossover bervariasi per sistem dan beban kerja.
Singkatnya, trade-off antara menggunakan indeks dan pemindaian tabel meliputi:
- Kinerja vs. Volume Data: Indeks Mengungguli saat memfilter beberapa baris; Pemindaian tabel bisa lebih baik untuk pengambilan data besar.
- Pola I/O: Pemindaian Indeks Menyebabkan Bacaan I/O Acak; Pemindaian tabel manfaat dari I/O berurutan dan pembacaan multi-blok.
- Overhead pemeliharaan: Indeks meningkatkan biaya operasi tulis karena pembaruan pada struktur indeks; Pemindaian meja tidak menimbulkan ini.
- Efisiensi Penyimpanan: Indeks dapat kompak dengan mencakup lebih sedikit kolom; Proses pemindaian tabel baris penuh dan berpotensi lebih banyak data.
- Efek caching: pemindaian tabel dapat memanfaatkan caching data secara efektif, terutama dengan bacaan berurutan besar; Pemindaian indeks mungkin tidak mendapat manfaat sebanyak karena akses acak.
- Keputusan Pengoptimal: Pengoptimal kueri berbasis biaya secara dinamis memilih antara opsi-opsi ini berdasarkan statistik kueri dan spesifik beban kerja.
- Dampak tata letak data: Tabel tumpukan dapat dikenakan hukuman seperti catatan yang diteruskan selama pemindaian; Indeks berkerumun mengatur data secara fisik tetapi meningkatkan biaya pembaruan.