Mengapa itu dibutuhkan?

 Ketika data disimpan pada perangkat penyimpanan berbasis disk, itu disimpan sebagai blok data.  Blok-blok ini diakses secara keseluruhan, menjadikannya operasi akses disk atom.  Blok disk disusun dengan cara yang hampir sama dengan daftar tertaut;  keduanya berisi bagian untuk data, penunjuk ke lokasi simpul berikutnya (atau blok), dan keduanya tidak perlu disimpan secara bersamaan.

 Karena kenyataan bahwa sejumlah catatan hanya dapat diurutkan pada satu bidang, kami dapat menyatakan bahwa pencarian pada bidang yang tidak diurutkan memerlukan Pencarian Linear yang membutuhkan akses N / 2 blok (rata-rata), di mana N adalah nomor  blok yang terbentang tabel.  Jika bidang itu adalah bidang non-kunci (mis. Tidak berisi entri unik) maka seluruh tablespace harus dicari di akses blok N.

 Sedangkan dengan bidang yang diurutkan, Pencarian Biner dapat digunakan, yang memiliki akses blok log2 N.  Juga karena data diurutkan diberi bidang non-kunci, sisa tabel tidak perlu dicari untuk nilai duplikat, setelah nilai yang lebih tinggi ditemukan.  Dengan demikian peningkatan kinerja sangat besar.

 Apa itu pengindeksan?

 Pengindeksan adalah cara menyortir sejumlah catatan pada berbagai bidang.  Membuat indeks pada bidang dalam tabel membuat struktur data lain yang menyimpan nilai bidang, dan penunjuk ke catatan yang terkait dengannya.  Struktur indeks ini kemudian disortir, memungkinkan Pencarian Biner dilakukan di dalamnya.

 Kelemahan dari pengindeksan adalah bahwa indeks ini membutuhkan ruang tambahan pada disk karena indeks disimpan bersama dalam sebuah tabel menggunakan mesin MyISAM, file ini dapat dengan cepat mencapai batas ukuran sistem file yang mendasarinya jika banyak bidang dalam tabel yang sama diindeks  .

 Bagaimana cara kerjanya?

 Pertama, mari garis besar skema tabel basis data sampel;

 Nama bidang Jenis data Ukuran pada id disk (kunci primer) INT yang tidak ditandatangani 4 byte pertama Nama Char (50) 50 byte lastName Char (50) 50 byte emailAddress Char (100) 100 byte

 Catatan: char digunakan sebagai pengganti varchar untuk memungkinkan ukuran yang akurat pada nilai disk.  Basis data sampel ini berisi lima juta baris dan tidak terindeks.  Kinerja beberapa pertanyaan sekarang akan dianalisis.  Ini adalah kueri yang menggunakan id (bidang kunci yang diurutkan) dan yang menggunakan nama depan (bidang yang tidak disortir tanpa kunci).

 Contoh 1 - bidang yang diurutkan vs yang tidak disortir

 Dengan basis data sampel kami r = 5.000.000 catatan ukuran tetap memberikan panjang catatan R = 204bytes dan mereka disimpan dalam tabel menggunakan mesin MyISAM yang menggunakan ukuran blok standar B = 1.024 byte.  Faktor pemblokiran tabel adalah bfr = (B / R) = 1024/204 = 5 catatan per blok disk.  Jumlah total blok yang diperlukan untuk menahan tabel adalah N = (r / bfr) = 5000000/5 = 1.000.000 blok.

 Pencarian linear pada bidang id akan membutuhkan rata-rata N / 2 = 500.000 akses blok untuk menemukan nilai, mengingat bahwa bidang id adalah bidang kunci.  Tetapi karena bidang id juga disortir, pencarian biner dapat dilakukan dengan rata-rata log2 1000000 = 19,93 = 20 akses blok.  Secara instan kita bisa melihat ini adalah peningkatan yang drastis.

 Sekarang bidang firstName bukan diurutkan atau tidak bidang kunci, sehingga pencarian biner tidak mungkin, juga tidak nilai-nilai yang unik, dan dengan demikian tabel akan membutuhkan pencarian sampai akhir untuk N = 1.000.000 akses blok yang tepat.  Situasi inilah yang ingin diperbaiki pengindeksan.

 Mengingat bahwa catatan indeks hanya berisi bidang yang diindeks dan penunjuk ke catatan asli, masuk akal bahwa itu akan lebih kecil daripada catatan multi-bidang yang ditunjuknya.  Jadi indeks itu sendiri membutuhkan lebih sedikit blok disk daripada tabel aslinya, yang karenanya membutuhkan lebih sedikit blok akses untuk beralih melalui.  Skema untuk indeks pada bidang firstName diuraikan di bawah ini;

 Nama bidang Tipe data Ukuran pada disk firstName Char (50) 50 byte (record pointer) Spesial 4 byte

 Catatan: Pointer di MySQL panjangnya 2, 3, 4 atau 5 byte tergantung ukuran tabel.

 Contoh 2 - pengindeksan

 Diberikan basis data sampel kami r = 5.000.000 catatan dengan panjang catatan indeks R = 54 byte dan menggunakan ukuran blok standar B = 1.024 byte.  Faktor pemblokiran indeks adalah bfr = (B / R) = 1024/54 = 18 catatan per blok disk.  Jumlah total blok yang diperlukan untuk menahan indeks adalah N = (r / bfr) = 5000000/18 = 277.778 blok.

 Sekarang pencarian menggunakan bidang firstName dapat memanfaatkan indeks untuk meningkatkan kinerja.  Hal ini memungkinkan untuk pencarian indeks biner dengan rata-rata log2 277778 = 18,08 = 19 akses blok.  Untuk menemukan alamat catatan aktual, yang memerlukan akses blok lebih lanjut untuk dibaca, menjadikan totalnya menjadi 19 + 1 = 20 akses blok, jauh sekali dari 1.000.000 akses blok yang diperlukan untuk menemukan kecocokan Nama depan pada tabel yang tidak diindeks.  .

 Kapan itu harus digunakan?

 Mengingat bahwa membuat indeks memerlukan ruang disk tambahan (277.778 blok tambahan dari contoh di atas, peningkatan ~ 28%), dan terlalu banyak indeks dapat menyebabkan masalah yang timbul dari batas ukuran sistem file, pemikiran yang cermat harus digunakan untuk memilih yang benar  bidang untuk diindeks.

 Karena indeks hanya digunakan untuk mempercepat pencarian bidang yang cocok dalam catatan, masuk akal bahwa bidang pengindeksan yang hanya digunakan untuk output hanya akan membuang-buang ruang disk dan waktu pemrosesan saat melakukan operasi penyisipan atau penghapusan, dan dengan demikian  harus dihindari.  Juga mengingat sifat pencarian biner, kardinalitas atau keunikan data adalah penting.  Pengindeksan pada bidang dengan kardinalitas 2 akan membagi data menjadi dua, sedangkan kardinalitas 1.000 akan mengembalikan sekitar 1.000 catatan.  Dengan kardinalitas yang rendah, keefektifannya dikurangi menjadi semacam linier, dan pengoptimal kueri akan menghindari penggunaan indeks jika kardinalitas kurang dari 30% dari jumlah catatan, secara efektif membuat indeks menjadi pemborosan ruang.
Oleh AgusDev

Juni 24, 2020

Artikel Terkait

<