Page 163 - E-Modul Sistem Basis Data
P. 163
akan ditelusuri sebelum baris data yang diseleksi ditemukan, di saat operasi
pencarian dihentikan.
Sehingga untuk atribut key ini, E. (br/2).
Meskipun algoritma ini menjadi tidak efisien dalam banyak kasus, ia dapat
diterapkan terhadap file apa pun, tidak peduli apakah tersebut terurut atau tidak dan
memiliki indeks atau tidak.
• Aa (pencarian biner/binary search).
Jika file terurut berdasarkan sebuah atribut, dan kondisi seleksi (dala bentuk
pembandingan) melibatkan atribut tersebut, maka kita dape menggunakan
algoritma pencarian biner untuk menemukan baris data yang memenuhi kondisi
seleksi tersebut. Algoritma ini dibentuk terhadap blok file, dengan estimasi
sebagai berikut:
Bagian pertama, yakni [log2 (br)], merupakan estimasi biaya un mencari
baris data pertama yang memanfaatkan algoritma pencaria biner. Sementara
banyaknya baris data yang akan memenuhi konda seleksi adalah SCA, r), dan akan
menempati [SCIA, r)/f blok file yang anggota pertamanya telah dibaca (sehingga
dikurangi dengan 1).
Jika kondisi seleksi berbentuk persamaan terhadap atribut yang menjadi key
pada tabel r, sehingga SCIA, r) = 1, maka estimasi biaya query menjadi E-flog. (b)
151
