Organisasi Sequential Rudi Susanto |
[email protected]
Organisasi Berkas • Organisasi Berkas Sekuensial Rekaman disimpan di dalam file secara beruntun berdasarkan waktu pemasukannya (rekaman yang masuk lebih dulu memiliki indeks / alamat yang lebih kecil dari yang dimasukkan kemudian) • Organisasi Berkas Langsung Rekaman disimpan tidak secara beruntun, namun pada alamat yang didasarkan pada kunci rekaman • Organisasi Berkas Sekuensial Berindeks Rekaman disimpan secara beruntun namun ditambahkan dengan adanya indeks yang akan mempermudah penemuan rekaman kembali
[email protected]
2
Organisasi Berkas Sekuensial • Rekaman disimpan pada alamat-alamat di file secara beruntun • Rekaman yang masuk terlebih dulu akan disimpan di alamat yang lebih kecil daripada rekaman yang masuk sesudahnya
[email protected]
3
Organisasi Berkas Sekuensial • Dalam berkas sekuensial, rekaman yang ke i+1 akan diletakkan tepat sesudah rekaman ke i, contoh : 1
2
3
……...
i
i+1
i+2
……
N-1
n
• Untuk menemukan sebuah rekaman harus dilakukan proses pencarian terlebih dahulu
[email protected]
4
Metode Akses
The access method determines how records can be retrieved: sequentially or randomly.
[email protected]
5
Aplikasi • Applications – that need to access all records from beginning to end. • Because you have to process each record, sequential access is more efficient and easier than random access. • Sequential file is not efficient for random access.
[email protected]
6
Penyisipan Record • Penyisipan – Lambat • • • •
Pencarian sequential untuk mencari posisi yang akan ditempati record. Jika ada tempat yang cukup pada halaman yang dicari, maka tulis record. Jika tidak cukup tempat, maka akan dipindahkan sejumlah record ke halaman berikutnya. Jika tidak ada tempat yang kosong, maka akan dilakukan penyusunan yang berulang-ulang sampai ditemukan tempat yang cukup.
– Dapat menggunakan mempersingkat waktu.
[email protected]
“overflow”
untuk
7
Modifikasi dan Penghapusan Record • Modifikasi – Lambat • Pencarian sequential • Melakukan modifikasi • Penulisan ulang record
• Penghapusan – Lambat • Pencarian sequential • Memberi tanda pada record atau mengosongkan tempat dari record yang dihapus • Penulisan ulang record
[email protected]
8
Kinerja File Sequensial • Record size
• Fetch Record • Time Fetch • Next Record • Time Insert
[email protected]
9
Record Size File Sequential • Kebutuhan file penyimpanan untuk file sequensial mengunakan foemat record tetap (fixed) yang tergantung pada sejumlah semua atribut yang mungkin = a • Ukuran tetap menghasilkan sejumlah field dan ukuran rata-ratanya • R = a. V a : Jumlah attribut/field V : Ukuran rata – rata nilai atribut (byte)
[email protected]
10
Fetch Record (TF) File Sequential • Waktu yang digunakan untuk mengambil satu record • TF=1/2.nR/t’ N=jumlah record
t’=bulk tranfer rate R=record size • Pencarian menggunakan Binary Search
[email protected]
11
Time Fetch File Sequential • Pencarian record pada Sequensial file dapat dilakukan beberapa cara antara lain: • Sequential search Pencarian yang dilakukan secara serial dimulai dari record 1,2,3 dan seterusnya
• Binary search Pencarian bukan dilakukan record per record tetapi blok per blok. Bila blok yang memuat record yang dicari sudah ditemukan, baru dilakukan pencarian ke level record.
[email protected]
12
Pencarian • Pencarian Sekuensial
• Pencarian Biner
[email protected]
13
Pencarian Secara Sekuensial • Memproses rekaman-rekaman dalam berkas sesuai urutan keberadaan rekamanrekaman tersebut sampai ditemukan rekaman yang diinginkan atau semua rekaman terbaca
[email protected]
14
[email protected]
15
Contoh • Misalkan akan mencari nama mahasiswa “Dewi”, maka akan diperlukan probe (akses terhadap lokasi record yang berbeda) sebanyak 5 kali. Apakah yang harus dilakukan agar kinerja pembacaan record lebih baik?
[email protected]
16
Sorting Nama Mhsw
Nomor Mhsw
Fakultas
Jurusan
Dosen Pembimbin g
SPP
Data Lain
Budiawan
…
Teknik
Informatika
…
…
…
Dewi
…
Teknik
Informatika
…
…
…
Iis
…
Teknik
Informatika
…
…
…
Komar
…
Teknik
Informatika
…
…
…
Nur Ahmad
…
Teknik
Informatika
…
…
…
Samin
…
Teknik
Informatika
…
…
…
Susiana
…
Teknik
Informatika
…
…
…
Surya Angkasa
…
Teknik
Informatika
…
…
…
Tri Rahayu
…
Teknik
Informatika
…
…
…
Zeni
…
Teknik
Informatika
…
…
…
[email protected]
17
Kunci
.
• Untuk membaca “Dewi” hanya diperlukan 2 probe, lebih kecil dibanding sebelum berkas diurutkan Kunci1
[email protected]
18
Soal a) Berapa banyak Probe yang dibutuhkan untuk mendapatkan “Juli” pada urutan nyata bulan-bulan dalam system penanggalan? b)
Berapa Probe yang dibutuhkan untuk mendapatkan ”Rabu” pada urutan nyata hari-hari dalam sistem waktu?
c) L = {4,12,9,-2,12,7,1,100}
Tahukah kamu dimana posisi 12 yang pertama ?
[email protected]
19
Pencarian Biner • Membandingkan kunci yang dicari dengan rekaman pada posisi tengah dari berkas. • Bila sama (kasus 1) berarti rekaman yang diinginkan sudah ditemukan, atau kalau tidak sama (kasus2) berarti separuh dari rekamanrekaman dalam berkas akan dieliminasi dari perbandingan yang selanjutnya. • Bila yang terjadi adalah kasus 2 maka proses pembandingan terhadap rekaman pada posisi tengah dilanjutkan menggunakan rekamanrekaman yang tersisa
[email protected]
20
Proc pencarian_biner /* n buah rekaman diurutkan menaik menurut kunci rekaman */ AWAL :=1 Akhir := n While AWAL ≤ AKHIR do tengah := [ (awal+akhir)/2] if kunci (cari) = kunci (tengah) then pencarian berakhir. else if kunci(cari) > kunci (tengah) then AWAL := TENGAH + 1 else AKHIR := TENGAH – 1 end rekaman tidak ditemukan end pencarian_biner
[email protected]
21
• Contoh flowchar binary search • Mid (Tengah) = [ (awal + akhir)/2 ]
[email protected]
22
Penjelasan • Jika kunci cari < kunci tengah, maka bagian berkas mulai dari kunci tengah sampai akhir berkas dieliminasi. • Jika kunci cari > kunci tengah , maka bagian berkas mulai dari depan sampai dengan kunci tengah dieliminasi. • Jika Awal >Akhir maka rekaman tidak ditemukan • Pembulatan angka untuk hasil nilai tengah adalah pembulatan ke bawah
[email protected]
23
Contoh Berikut akan dicari rekaman dengan kunci 49, berapa probe yang dilakukan untuk mendapatkannya? Keterangan : Bilangan yang dicetak tebal menunjukkan rekaman yang sedang dibandingkan dan tanda kurung membatasi bagian berkas yang tersisa yang masih harus diperbandingkan. Tanda [ untuk AWAL dan tanda ] untuk AKHIR.
[email protected]
24
Binary Search
[email protected]
25
Binary Search
[email protected]
26
Binary Search
[email protected]
27
Soal • Berikut akan dicari rekaman dengan kunci (a)27, (b)28 berapa probe yang dilakukan untuk mendapatkannya?
[email protected]
28
Tugas! 1. Diketahui rekaman-rekaman dengan kunci 34, 44, 51, 56, 690, 890, 1060, 2876, 3570, dan 3999, berapa Probe diperlukan untuk menemukan reakaman dengan kunci 51, 1060 dan 895 menggunakan pencarian biner? 2. Berapa probe yang dibutuhkan untuk mencari tanggal 25 dalam bulan September 2016 sesuai penanggalan. a) Pencarian dilakukan menggunakan pencarian sequential b) Pencarian dilakukan menggunakan pencarian biner
[email protected]
29
Terima kasih
[email protected]
30