organisasi sequential - rudist.files.wordpress.com · organisasi berkas •organisasi berkas...

Organisasi SequentialRudi Susanto | rudist87@gmail.com

Organisasi Berkas

• Organisasi Berkas SekuensialRekaman disimpan di dalam file secaraberuntun berdasarkan waktu pemasukannya(rekaman yang masuk lebih dulu memilikiindeks / alamat yang lebih kecil dari yang dimasukkan kemudian)

• Organisasi Berkas LangsungRekaman disimpan tidak secara beruntun, namun pada alamat yang didasarkan padakunci rekaman

• Organisasi Berkas Sekuensial BerindeksRekaman disimpan secara beruntun namunditambahkan dengan adanya indeks yang akan mempermudah penemuan rekamankembali

2rudist87@gmail.com

Organisasi Berkas Sekuensial

• Rekaman disimpan pada alamat-alamat difile secara beruntun

• Rekaman yang masuk terlebih duluakan disimpan di alamat yang lebihkecil daripada rekaman yang masuksesudahnya

3rudist87@gmail.com

Organisasi Berkas Sekuensial

• Dalam berkas sekuensial, rekaman yang kei+1 akan diletakkan tepat sesudah rekamanke i, contoh :

• Untuk menemukan sebuah rekaman harusdilakukan proses pencarian terlebihdahulu

1 2 3 ……... i i+1 i+2 …… N-1 n

4rudist87@gmail.com

Metode Akses

The access method determines how records can be retrieved: sequentially or randomly.

5rudist87@gmail.com

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.

6rudist87@gmail.com

Penyisipan Record

• Penyisipan– Lambat

• Pencarian sequential untuk mencari posisi yang akanditempati record.

• Jika ada tempat yang cukup pada halaman yang dicari,maka tulis record.

• Jika tidak cukup tempat, maka akan dipindahkansejumlah record ke halaman berikutnya.

• Jika tidak ada tempat yang kosong, maka akan dilakukanpenyusunan yang berulang-ulang sampai ditemukantempat yang cukup.

– Dapat menggunakan “overflow” untukmempersingkat waktu.

7rudist87@gmail.com

Modifikasi dan PenghapusanRecord

• Modifikasi

– Lambat• Pencarian sequential

• Melakukan modifikasi

• Penulisan ulang record

• Penghapusan

– Lambat• Pencarian sequential

• Memberi tanda pada record atau mengosongkantempat dari record yang dihapus

• Penulisan ulang record

8rudist87@gmail.com

Kinerja File Sequensial

• Record size

• Fetch Record

• Time Fetch

• Next Record

• Time Insert

rudist87@gmail.com 9

Record Size File Sequential

• Kebutuhan file penyimpanan untuk file sequensialmengunakan foemat record tetap (fixed) yangtergantung pada sejumlah semua atribut yangmungkin = a

• Ukuran tetap menghasilkan sejumlah field danukuran rata-ratanya

• R = a. V

a : Jumlah attribut/field

V : Ukuran rata – rata nilai atribut (byte)

rudist87@gmail.com 10

Fetch Record (TF) File Sequential

• Waktu yang digunakan untuk mengambilsatu record

• TF=1/2.nR/t’

N=jumlah record

t’=bulk tranfer rate

R=record size

• Pencarian menggunakan Binary Search

11rudist87@gmail.com

Time Fetch File Sequential

• Pencarian record pada Sequensial file dapatdilakukan 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 sudahditemukan, baru dilakukan pencarian kelevel record.

rudist87@gmail.com 12

Pencarian

• Pencarian Sekuensial

• Pencarian Biner

rudist87@gmail.com 13

Pencarian Secara Sekuensial

• Memproses rekaman-rekaman dalamberkas sesuai urutan keberadaan rekaman-rekaman tersebut sampai ditemukanrekaman yang diinginkan atau semuarekaman terbaca

14rudist87@gmail.com

rudist87@gmail.com 15

Contoh

• Misalkan akan mencari nama mahasiswa“Dewi”, maka akan diperlukan probe (aksesterhadap lokasi record yang berbeda) sebanyak 5 kali. Apakah yang harusdilakukan agar kinerja pembacaan recordlebih baik?

16rudist87@gmail.com

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 … … …

17rudist87@gmail.com

Kunci

• Untuk membaca “Dewi” hanya diperlukan 2 probe, lebih kecil dibanding sebelum berkasdiurutkan

.Kunci1 <kunci2 <kunci3 <…kunci I <…kunci n

18rudist87@gmail.com

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 ?

19rudist87@gmail.com

Pencarian Biner

• Membandingkan kunci yang dicari denganrekaman pada posisi tengah dari berkas.

• Bila sama (kasus 1) berarti rekaman yang diinginkan sudah ditemukan, atau kalau tidaksama (kasus2) berarti separuh dari rekaman-rekaman dalam berkas akan dieliminasi dariperbandingan yang selanjutnya.

• Bila yang terjadi adalah kasus 2 maka prosespembandingan terhadap rekaman pada posisitengah dilanjutkan menggunakan rekaman-rekaman yang tersisa

20rudist87@gmail.com

Proc pencarian_biner/* n buah rekaman diurutkan menaik menurut kunci rekaman

*/AWAL :=1Akhir := nWhile AWAL ≤ AKHIR do

tengah := [ (awal+akhir)/2]if kunci (cari) = kunci (tengah)

then pencarian berakhir.else if kunci(cari) > kunci (tengah)

then AWAL := TENGAH + 1else AKHIR := TENGAH – 1

endrekaman tidak ditemukan

end pencarian_biner

21rudist87@gmail.com

• Contohflowchar binary search

• Mid (Tengah) = [ (awal + akhir)/2 ]

rudist87@gmail.com 22

Penjelasan

• Jika kunci cari < kunci tengah, maka bagianberkas mulai dari kunci tengah sampai akhirberkas dieliminasi.

• Jika kunci cari > kunci tengah , maka bagianberkas mulai dari depan sampai dengankunci tengah dieliminasi.

• Jika Awal >Akhir maka rekaman tidakditemukan

• Pembulatan angka untuk hasil nilai tengahadalah pembulatan ke bawah

23rudist87@gmail.com

Contoh

Berikut akan dicari rekaman dengan kunci 49,berapa probe yang dilakukan untukmendapatkannya?

Keterangan :

Bilangan yang dicetak tebal menunjukkanrekaman yang sedang dibandingkan dantanda kurung membatasi bagian berkas yangtersisa yang masih harus diperbandingkan.

Tanda [ untuk AWAL dan tanda ] untukAKHIR.

24rudist87@gmail.com

Binary Search

25rudist87@gmail.com

Binary Search

26rudist87@gmail.com

Binary Search

27rudist87@gmail.com

Soal

• Berikut akan dicari rekaman dengan kunci (a)27, (b)28 berapa probe yang dilakukanuntuk mendapatkannya?

rudist87@gmail.com 28

Tugas!

1. Diketahui rekaman-rekaman dengan kunci34, 44, 51, 56, 690, 890, 1060, 2876, 3570, dan3999, berapa Probe diperlukan untukmenemukan reakaman dengan kunci 51, 1060dan 895 menggunakan pencarian biner?

2. Berapa probe yang dibutuhkan untuk mencari tanggal 25 dalam bulan September 2016sesuai penanggalan.

a) Pencarian dilakukan menggunakan pencarian sequential

b) Pencarian dilakukan menggunakan pencarian biner

rudist87@gmail.com 29

Terima kasih

rudist87@gmail.com 30