FILE BERINDEKS MAJEMUK • File berindeks majemuk dimungkinkan membuat beberapa indeks berdasarkan lebih dari satu atribut. Indeks dibolehkan pada sembarang atribut bahkan semua atribut atau gabungan atribut. • Deskripsi file berindeks majemuk : Semua indeks dianggap sama (tidak ada atribut utama, semua indeks adalah record anchor). Tidak ada kebutuhan pengelolaan rantai ke file log/overflow (tdk ada file log).
• Komponen file berindek majemuk File utama, berisi data. File-file indeks. Pada file berindeks majemuk, record hanya dapat diakses melalui indeks. Tidak ada batasan penempatan record data. Panjang record dapat bervariasi dan lebih fleksibel dari file sekuen berindeks. 1
• Direktori File dengan banyak indeks berisi banyak komponen berbeda, maka kita harus dapat menentukan keberadaan indeks, cara organisasi dan letak. Untuk itu dapat digunakan direktori file.
• Struktur dan Pengaksesan Struktur pada struktur ini terdapat indeks sebanyak atribut di file, bahkan dapat membuat indeks dengan kunci gabungan beberapa atribut sekaligus. Indeksnya record anchor dan dapat diindeks lagi (multi indeks sampai ditempatkan dalam satu blok indeks). Format record rekord dapat mempunyai format seperti pada record struktur file sekuen dan record dapat juga berisi pasangan nama atribut –nilai atribut seperti file pile.
2
Struktur file indeks Perubahan atribut di file berindeks majemuk memerlukan penyisipan, penghapusan atau keduanya, maka indeksnya menggunakan indeks B-tree. Blok indeks di B-tree harus dijaga agar setidaknya memuat setengah, effectivefanout (yeff) = 0,69 y (diantara y dan y/2). Ketinggian B-tree adalah jumlah level yang merupakan fungsi yeff :
x yeff log n' dimana : n’ = jumlah rekord yang mempunyai nilai atribut yang dapat diindeks • Penggunaan File Berindeks majemuk Contoh penggunaan : sangat sering digunakan pada pengambilan data cepat (online access misalnya call center telkom).
3
• Analisis kinerja file berindeks majemuk digunakan dengan asumsi : 1. seluruh atribut di-indeks. 2. Indeks menggunakan B-tree. 3. Record data memakai struktur pile. 4. Indeks di indeks kembali 5. Indeks sudah stabil (yeff/y = 0,69) Ukuran rekord (R) Total ruang yang diperlukan adalah ruang file data & seluruh indeks - Ruang untuk file data, sama dengan ruang yang dibutuhkan file pile. Rmain = a’ (A + V + 2) - Ruang untuk seluruh indeks SItotal = 1,5 n a’ (Vindex + P) Jadi Rtotal = Rmain + Rindex = a’ (A + V + 2) + 1,5 a’ (Vindex + P) Jika Vindex = V maka : R = a’ ( A + 2,5 V + 1,5 P + 2) 4
Waktu Pengambilan Rekord Tertentu (TF) TF = x (s + r + btt) + s + r + btt = (x + 1) (s + r + btt) Dimana : x = ketinggian dari B-tree. Jika tiap indeks disimpan di satu selinder tunggal, maka beberapa seek dapat dihilangkan sehingga : TF = 2s + (x + 1) (r + btt) Waktu Pengambilan Rekord Tertentu (TN) Pencarian untuk rekord berikutnya didasarkan asumsi blok indeks terakhir berada di buffer sehingga hanya memerlukan pengambilan rekord data. TN = s + r + btt Waktu Penyisipan Rekord (TI) Untuk penambahan satu rekord, rekord ditempatkan disembarang daerah bebas dan kemudian a’ indeks yang mengacu ke atribut rekord ini diubah. TI = (1 + a’) s + (3 + 4a’) + (1 + 2a’) btt 5
Waktu Pembaharuan Rekord (TU) Mekanisme : 1. Pencarian record 2. Pembaruan terhadap data 3. Pengubahan indeks dimana data berubah Pebaruan melibatkan satu pengubahan rekord data dan sebanyak a indeks yang berubah TU = (4 + 2aupdate + 2a’) + (s + 2r + btt) Jika rekord yang diubah tidak perlu dipindahkan, maka sebanyak a’-aupdate yang tidak perlu diubah sehingga: TU = (4 + 4aupdate ) + (s + 2r + btt)
6
Waktu Pembacaan Seluruh Rekord (TX) Mempunyai dua kemungkinan yaitu: 1. secara serial (dibuat indeks “keseluruhan” ) TX = TF + (n - 1) TN 2. Jika pointer alokasi ruang dapat diikuti, pencarian dilakukan sekali per blok TX = n (R/t) Waktu Reorganisasi File (TY) Pada file berindeks majemuk mempunyai karakteristik: 1. Beberapa implementasi tidak membutuhkan reorganisasi. 2. Reorganisai hanya untuk menghilangkan ruang yang disebabkan penghapusan. Mekanisme reorganisasi biasanya dilakukan pada saat-saat: 1. Saat pemulihan (recovery). 2. Saat distribusi isian indeks sangat buruk, perlu rekonstruksi. 7
Mekanisme: 1. Reorganisasi file data 2. Reorganisasi seluruh file indeks Langkah : 1. Pembacaan seluruh rekord di file utama 2. Pembaruan terhadap seluruh file indeks 3. Tulis ke file sementara rekord file utama yang masih berlaku (bukan ditandai sebagai dihapus). Waktu yang diperlukan untuk pembaharuan satu file indeks : TY (one) = Tx + Tsort(n’) Sehingga: TY = 2 Tx + a Ty(one)
8
9
