materi sistem berkas

Upload: adityaputra

Post on 18-Jul-2015

349 views

Category:

Documents


42 download

TRANSCRIPT

Sesi 1

SISTEM BERKASMateri Sistem Berkas 1. Konsep Dasar Sistem Berkas 2. Media Penyimpanan 3. Organisasi Berkas Primer 4. Organisasi Berkas Sequential 5. Organisasi Berkas Langsung 6. Organisasi Berkas dengan Banyak key 7. Organisasi Berkas Relatif 8. Organisasi Berkas Indeks Sequential 9. Manajemen Kolisi 10. Pengurutan Rekaman 11. Sort dan Merge File 12. Pengenalan Kontrol Input/Output

Sistem Penilaian Nilai Akhir = (40% x UTS) + (60% x UAS) UTS = (50% x nilai quiz) + (50% x nilai UTS) UAS = (50% x nilai tugas/diskusi) + (50% x nilai UAS)

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 1

Rencana Penjadwalan kuliah SESI 1 TANGGAL Senin/27 Feb 2012 (kls A) Rabu/29 Feb 2012 (kls B) 2 3 4 5 6 7 Senin/05 Mar 2012 (kls A) Rabu/07 Mar 2012 (kls B) Senin/12 Mar 2012 (kls A) Rabu/14 Mar 2012 (kls B) Senin/19 Mar 2012 (kls A) Rabu/21 Mar 2012 (kls B) Senin/26 Mar 2012 (kls A) Rabu/28 Mar 2012 (kls B) Senin/02 Apr 2012 (kls A) Rabu/04 Apr 2012 (kls B) Senin/09 Apr 2012 (kls A) Rabu/11 Apr 2012 (kls B) Sesuai Jadwal 8 9 10 11 12 13 14 Senin/30 Apr 2012 (kls A) Rabu/02 Mei 2012 (kls B) Senin/07 Mei 2012 (kls A) Rabu/09 Mei 2012 (kls B) Senin/14 Mei 2012 (kls A) Rabu/16 Mei 2012 (kls B) Senin/21 Mei 2012 (kls A) Rabu/23 Mei 2012 (kls B) Senin/28 Mei 2012 (kls A) Rabu/30 Mei 2012 (kls B) Senin/04 Juni 2012 (kls A) Rabu/06 Juni 2012 (kls B) Senin/11 Juni 2012 (kls A) Rabu/13 Juni 2012 (kls B) Sesuai Jadwal UAS (Bahan dari materi 8 s/d 12) Diskusi Tugas Diskusi Tugas Materi 12. Pengenalan Kontrol Input/Output Materi 11. Sort dan Merge File Materi 10. Pengurutan Rekaman Materi 9. Manajemen Kolisi UTS (Bahan dari materi 4 s/d 7) Materi 8. Organisasi Berkas Indeks Sequential Materi 5. Organisasi Berkas Langsung Materi 6. Organisasi Berkas dengan Banyak key Materi 7. Organisasi Berkas Relatif Materi 4. Organisasi Berkas Sequential Quiz (Bahan dari materi 1 s/d 3) Materi 3. Organisasi Berkas Primer Pengenalan Pokok materi selama satu semester Materi 1. Konsep Dasar Sistem Berkas MATERI

Materi 2. Media Penyimpanan

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 2

Materi 1 KONSEP DASAR SISTEM BERKASKomputer dapat menyimpan informasi dalam berbagai bentuk fisik tempat penyimpanan seperti pita magnetik, disk magnetic, disk optical. Sistem operasi memberikan pandangan logis yang sejenis dari tempat penyimpanan informasi. Bentuk penyimpanan abstraksi dari unit penyimpan informasi dalam bentuk fisik adalah file. Filefile dipetakan oleh sistem operasi ke dalam peralatan fisik. A. PENGERTIAN SISTEM BERKAS File/berkas adalah sekumpulan informasi yang saling berkaitan dan didefenisikan oleh pembuatnya. Umumnya berkas adalah sekumpulan bit, byte, record di mana artinya didefenisikan oleh pembuat dan pemakainya. File data dapat berbentuk numeric, alfabeth ataupun alfanumeric. File dapat berbentuk bebas seperti file teks atau terstruktur. Suatu file mempunyai nama dan diacu berdasarkan nama tersebut. Juga mempunyai komponen lain seperti tipe, waktu pembuatan, nama dan nomor account dari pembuatnya, besar ukuran file. Kita dapat menulis informasi, mengubah informasi, menambah dan menghapus informasi dalam file. Sistem berkas adalah suatu sistem untuk mengetahui bagaimana cara menyimpan data dari file tertentu dan organisasi file yang digunakan. Sistem berkas menyediakan pendukung yang memungkinkan programmer mengakses file tanpa menyangkut perincian karakteristik penyimpanan dan peralatan pewaktu. Sistem berkas mengubah pernyataan akses file menjadi instruksi/output level rendah. Sistem berkas adalah cara untuk mengambil informasi dari suatu file. Pengarsipan dan akses adalah : a) Cara untuk membentuk suatu arsip/file dan cara pencarian record-recordnya kembali. b) Sistem berkas dan akses adalah sistem pengorganisasian, pengelolaan dan penyimpanan data pada alat eksternal dan pada organisasi file tertentu. Pada sistem berkas dan akses penyimpanan data dilakukan secara fisik. c) Teknik yang digunakan untuk menggambarkan dan menyimpan record pada file disebut organisasi file. Berikut ini adalah 4 komponen sistem berkas : a) Disk Management. Menjelaskan bagaimana seharusnya menyusun blok-blok disk ke dalam file. b) Naming. Berguna bagi pemakai yang memungkinkan untuk menunjuk file dengan penamaan yaitu dengan mengenali blok-blok disk. c) Protection. Suatu cara untuk memproteksi pemakai-pemakai file dari pemakai lain. d) Reliability. File-file yang diperlukan ada tersedia jika terjadi kerusakan sistem . Setiap sistem operasi memiliki sistem tersendiri.

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 3

Contoh : FAT 32 pada Window 9x. NTFS pada Windows NT dan Windows XP. FAT 16 pada MS-DOS. Ext2,Ext3 dan Reiser pada Linux. Masingmasing file sistem mempuyai metode yang berbeda dalam pengaksesesan, pengorganisasian dan pengeloaan pada disk. B. PENGERTIAN ORGANISASI FILE Pengorganisasian merupakan suatu teknik yang dipakai untuk menggambarkan dan menyimpan record-record dalam sebuah berkas/file. Ada 4 teknik dasar dari organisasi berkas, yaitu : 1) Sequential 2) Relative 3) Indexed sequential 4) Multi key Secara umum berbeda dalam hal cara pengaksesannya, yaitu : 1) Direct acces, yaitu suatu cara pengaksesan record yang langsung, tanpa mengakses seluruh record yang ada. 2) Sequential Acces, yaitu suatu cara pengaksesan record yang didahului pengaksesan record-record didepannya. C. ISTILAH-ISTILAH DASAR Entitas : Adalah suatu objek yang dapat dibedakan dari lainnya. Objek disini dapat berupa barang, orang, maupun peristiwa. Contoh : Entitas gaji pegawai, entitas nomor telepon, entitas nilai ujian. Atribut : Adalah karakteristik yang menjadi ciri dari entitas. Contoh Entitas gaji pegawai terdiri dari atribut : NIP, nama, jem lembur, tunjangan, gaji pokok. Item Data : Tempat penyimpanan tiap atribut dari sebuah entitas. Contoh : Item data untuk nama mahasiswa. Biasa disebut field, namun dipakai untuk menunjukkan tempat dimana item data disimpan. Item data elementer : Adalah bagian lebih kecil dari item data. Contoh : item data Record Berkas/file tanggal dapat dibagi menjadi intem data elementer tanggal, bulan, dan tahun. : Adalah kumpulan item data yang saling berhubungan. : Adalah kumpulan record yang saling berhubungan.

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 4

D. HUBUNGAN FIELD, RECORD, DAN FILE Contoh : File Siswa yang berisi berikut ini NIM 11.01.0020 11.01.0057 11.01.0059 Nama Dinny Wahyu Widarti Alamat Singosari Blitar Sumedang Record

Field/Item data File siswa tersebut memiliki 3 field, yaitu NIM, Nama, dan Alamat. Juga memiliki 3 record, yaitu : 1) 11.01.0020 2) 11.01.0057 3) 11.01.0059 Dinny Wahyu Widarti Singosari Blitar Sumedang

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 5

Sesi 2

Materi 2 MEDIA PENYIMPANAN FILEA. PENYIMPANAN PRIMER Penyimpanan primer (primary memory) atau disebut juga Memori utama (main memory) dan memori internal (internal memory). Komponen ini berfungsi sebagai pengingat. Dalam hal ini, yang disimpan didalam memori dapat berupa data atau program. Penyimpanan primer dibedakan menjadi dua macam, yaitu : RAM Random-Access Memory adalah jenis memori yang isinya dapat diganti selama komputer dihidupkan dan mempunyai sifat bisa mengingat data/program selama terdapat arus listrik (komputer hidup). RAM dapat menyimpan dan mengambil data dengan sangat cepat. ROM Read-Only Memory adalah jenis memori yang hanya bisa dibaca. Disediakan oleh vendor komputer dan berisi program atau data. Selain itu ada pula Cache memory, yaitu memori yang memiliki kecepatan yang sangat tinggi yang digunakan sebagai perantara antara RAM dan CPU. B. PENYIMPANAN SEKUNDER Penyimpanan sekunder atau disebut secondary memory adalah penyimpanan data yang relative mampu bertahan dalam jangka waktu yang cukup lama di luar CPU maupun penyimpanan primer. Ada dua jenis penyimpanan sekunder, yaitu : 1. Serial/sequential access storage device(SASD) Contoh : Magnetic tape, punched card, punched paper tape 2. Direct access storage device (DASD) Contoh : Magnetic disk, floppy disk, C. JENIS MEDIA PENYIMPANAN FILE 1. Magnetic Tape

Adalah alat penyimpanan data untuk berkas besar, yang di akses dan diprosessecara sequential. Magnetic tape dibuat dari bahan plastik tipis yang dilapisi oleh besi magnet oksida pada satu sisinya, berwarna merah kecoklatan. Magnetic tape adalah model pertama dari secondary memory. Tape ini digunakan untuk merekam audio, video dan untuk menyimpan informasi berupa sinyal komputer. Panjang tape pada umumnya 2400 feet, lebarnya 0.5 inch dan tebalnya 2 mm. Data disimpan dalam bintik kecil yang bermagnit dan tidak tampak pada bahan plastik tersebut. Contoh : cassette tape dan kaset video

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 6

2. Magnetic Disk

Adalah piranti penyimpanan sekunder yang paling banyak dijumpai pada sistemkomputer. Magnetic disk terdiri dari logam yang kaku atau plastic yang fleksibel. Pada saat disk digunakan, motor drive berputar dengan kecepatan yang sangat tinggi. Ada sebuah readwrite head yang ditempatkan diatas permukaan piringan tersebut. Permukaan disk terbagi atas beberapa track yang masih terbagi lagi menjadi beberapa sector. Fixedhead disk memiliki satu head untuk tiaptiap track, sedangkan Movinghead disk (atau sering dikenal dengan nama hard disk) hanya memiliki satu head yang harus dipindahpindahkan untuk mengakses dari satu track ke track yang lainnya. Contoh : Floppy disk (disket), hardisk. 3. Optical Disk Optical disk tidak menggunakan bahan yang bersifat magneti sama sekali. Optical disk menggunakan bahan spesial yang dapat diubah oleh sinar laser menjadi memiliki spot-spot yang relatif gelap atau terang. contoh dari optical disk ini adalah CD-RW dan DVD-RW.

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 7

Sesi 3

Materi 3 ORGANISASI BERKAS PRIMEROrganisasi berkas akan mempelajari struktur yang tepat untuk mengorganisasi: Jumlah rekaman yang besar Berkas dengan kinerja tertentu Informasi yang diolah dengan cara yang berbeda untuk keperluan yang berbeda Informasi yang memungkinkan dilakukannya tugas-tugas khusus Menyelesaikan permasalahan dengan cara yang berbeda dari yang selama ini dilakukan A. ORGANISASI BERKAS Terdapat tiga oganisasi berkas primer, yaitu sekuensial, langsung, dan sekuensial berindeks. Masing-masing organisasi tersebut memiliki cara memproses atau mengakses berkas. Organisasi Sekuensial Sekuensial berindeks Langsung Akses Sekuensial Sekuensial atau langsung langsung

Sebagai contoh, terdapat sejumlah unit informasi yang disebut rekaman yang mengandung data mengenai entitas individual. Rekaman tersebut dapat diuraikan menjadi unit-unit yang lebih kecil, yang disebut medan-medan yang mengandung nilainilai khusus bagi atribut-atribut yang mewakili individu tersebut. B. MEDAN DATA Medan berisi nilai dasar yang membentuk sebuah rekaman. Isi sebuah medan bergantung pada atribut yang dimiliki oleh individu pemilik rekaman. Nilai tersebut pada saatnya nanti akan dimanipulasi oleh proses komputasi. Nilai-nilai dalam medan harus tunduk pada deskripsi tentang tipe nilai, kapasitas byte maksimum, domain dan seterusnya yang dimiliki oleh medan tersebut. Rekaman yang disimpan dalam berkas pada umumnya memiliki medan yang berfungsi khusus, yaitu sebagai identitas rekaman yang memiliki sifat pembeda baik internal maupun eksternal. Medan tanggal yang umumnya dimiliki oleh sebuah rekaman merupakan contoh yang unik. Medan tersebut bisa memiliki kapasitas byte maksimum 8, dan disusun dari 3 medan yang lebih elementer, yaitu tanggal (2digit), bulan (2digit), tahun (4digit). Data tanggal paling baik dinyatakan dalam tipe bilangan, mengingat tanggal memiliki kemungkinan untuk diperbandingkan (lebih tua atau lebih muda), proses dengan aritmatik sederhana (menghitung umur) dan sebagainya. Pemilihan tipe data yang paling sesuai dengan kebutuhan yang disyaratkan oleh sistem yang sedang dibangun merupakan hal yang penting. Suatu domain yang spesifik, sangat baik bila diuraikan dalam satu tipe dan satu representasi. Representasi yang tidak sesuai akan menyebabkan hilangnya informasi yang sulit untuk dilacak kembali.

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 8

C. REKAMAN DATA Medan ke-1 Medan ke-2 Medan ke-n Rekaman merupakan koleksi berbagai medan yang berisi beberapa item data elementer. Beberapa medan dapat berhubungan satu dengan yang lainnya karena mereka melakukan deskripsi suatu hal yang spesifik, misalnya tentang seseorang , tentang sebuah subyek, atau suatu kejadian. Informasi tentang seseorang mahasiswa misalnya, dapat disimpan dengan cara berikut : Rekaman mahasiswa Nama Mahasiswa Nomor Mahasiswa tersebut dapat Jenjang Program Studi disimpan dengan nama-nama Dosen Wali SPP Data lain medan Nama

Rekaman

Mahasiswa, Nomor Mahasiswa, Jenjang, Program Studi, Dosen Wali, SPP, dan lain-lain. Kunci primernya merupakan suatu medan, atau gabungan beberapa medan, yang secara unik membedakan satu rekaman dengan yang lainnya, sedangkan semua medan yang tersisa merupakan kunci skunder dari atribut. Sebagai contoh: medan Nama Mahasiswa ataupun Nomor Mahasiswa mungkin merupakan kunci primer, sedangkan medan Jenjang, Program Studi, dan yang lain merupakan kunci skunder. D. BERKAS DATA Sebuah berkas merupakan koleksi dari rekaman-rekaman yang sama, yang diletakkan dalam peralatan penyimpanan data komputer. Salah satu tipe peralatan penyimpanan eksternal, dari berbagai alternatif, adalah penggerak disk dengan disk magnetiknya. Sebuah berkas akan memiliki nama yang dikenal oleh sistem operasi, dan mempunyai struktur atau organisasi yang ditentukan oleh program pengakses berkas. Berikut ini adalah contoh berkas tentang mahasiswa di universitas: Nama Dian Kartika Syda Arlin Yuniati Sunaryono Zainul Yenny Noorma Mustafa Kusmiyati Susiana Dewi Dwi 11.50.025 11.55.024 11.55.024 11.30.014 S1 S1 S1 DIII Sistem Informasi Teknik Informatika Teknik Informatika Manajemen Informatika Dinny Wahyu Widarti, S.Kom Sistem Berkas - 9 Sugeng 500.000 Made Made Made 500.000 500.000 400.000 11.50.011 11.30.012 11.30.013 11.55.024 11.50.021 S1 DIII DIII S1 S1 Sistem Informasi Manajemen Informatika Manajemen Informatika Teknik Informatika Sistem Informasi Sugeng 500.000 Sugeng 500.000 Made 400.000 Sugeng 500.000 Made 400.000 Nomor 11.50.001 Jenjang Program Studi S1 Sistem Informasi Dosen Wali Made SPP Data lain 500.000 Mahasiswa Mahasiswa

Dalam merancang sebuah berkas untuk menyimpan semua rekaman yang menggambarkan tentang mahasiswa sebuah universitas, bukanlah gagasan yang baik bila beberapa tipe rekaman di campur-aduk, missal rekaman mahasiswa dengan daftar matakuliah yang ditawarkan, dalam sebuah berkas yang sama. Sebaliknya, mempunyai berbagai berkas yang berbeda juga mengundang berbagai kesulitan dikemudian hari. Untuk mengulangi kesulitan-kesulitan tersebut, para pakar berusaha mencari jalan keluar. Akhirnya ditemukan suatu alternatif yaitu menggabungkan rekaman-rekaman milik semua mahasiswa untuk semua jurusan dalam sebuah berkas.

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 10

Sesi 5

Materi 4 ORGANISASI BERKAS SEKUENSIALDalam organisasi ini, record-record direkam secara berurutan pada waktu berkas ini dibuat dan harus diakses secara berurutan pada waktu berkas ini digunakan sebagai input. Berkas sekuensial sangat cocok untuk akses yang sekuensial, misalnya dalam aplikasi dimana sebagian besar atau semua rekaman akan diproses. Sebagai contoh adalah membuat daftar mahasiswa dalam sebuah program studi. Melakukan akses secara sekuensial berarti proses akan berpindah dari satu rekaman ke rekaman berikutnya secara langsung. 1 2 3 i i+1 i+2 n-1 n

Pencarian secara sekuensial adalah memproses rekaman rekaman dalam berkas sesuai urutan keberadaan rekaman rekaman tersebut sampai ditemukan rekaman yang diinginkan atau semua rekaman terbaca. Berkas sekuensial juga dapat diproses secara tunggal dan langsung, jika diketahui subskripnya. Tetapi bagaimana kalau subskrip yang dimiliki bukan identitas utama rekaman, misal Nama Mahasiswa pada file berikut ini :Nama Mahasiswa Dian Kartika Syda Arlin Yuniati Sunaryono Zainul Yenny Noorma Mustafa Kusmiyati Susiana Dewi Dwi Nomor Induk Mahasiswa 11.50.001 11.50.011 11.30.012 11.30.013 11.55.024 11.50.021 11.50.025 11.55.027 11.55.028 11.30.014 S1 S1 DIII DIII S1 S1 S1 S1 S1 DIII Sistem Informasi Sistem Informasi Manajemen Informatika Manajemen Informatika Teknik Informatika Sistem Informasi Sistem Informasi Teknik Informatika Teknik Informatika Manajemen Informatika Jenjang Program Studi Dosen Wali Made Sugeng Made Made Sugeng Sugeng Sugeng Made Made Made 500.000 500.000 400.000 400.000 500.000 500.000 500.000 500.000 500.000 400.000 SPP Data lain

Pembacaan harus dilakukan secara sekuensial. Rekaman demi rekaman, sampai Nama Mahasiswa yang sesuai ditemukan. Misalnya untuk pembacaaan rekaman dengan Nama Mahasiswa = Sunaryono, diperlukan probe (akses terhadap lokasi yang berbeda) sejumlah 4 kali. Yang harus dilakukan agar kinerja pembacaan rekaman lebih baik, maka rekamanrekaman dalam berkas mahasiswa tersebut diurutkan untuk mendapatkan pengurutan yang linier berdasarkan nilai kunci rekaman. Baik secara alphabetis maupun numeris. Hasil pengurutannya adalah sbb :

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 11

Nama Mahasiswa Yuniati Sunaryono Dewi Dwi Dian Kartika Syda Arlin Yenny Noorma Mustafa Zainul Kusmiyati Susiana

Nomor Induk Mahasiswa 11.30.012 11.30.013 11.30.014 11.50.001 11.50.011 11.50.021 11.50.025 11.55.024 11.55.027 11.55.028

Jenjang DIII DIII DIII S1 S1 S1 S1 S1 S1 S1

Program Studi Manajemen Informatika Manajemen Informatika Manajemen Informatika Sistem Informasi Sistem Informasi Sistem Informasi Sistem Informasi Teknik Informatika Teknik Informatika Teknik Informatika

Dosen Wali Made Made Made Made Sugeng Sugeng Sugeng Sugeng Made Made

SPP 400.000 400.000 400.000 500.000 500.000 500.000 500.000 500.000 500.000 500.000

Data lain

Berkas diatas berisi rekaman mahasiswa urut berdasar Nomor Induk Mahasiswa. Kolom Nomor Induk Mahasiswa menunjukkan nilai yang urut dari kecil ke besar. Dengan demikian , hanya n/2 rekaman yang perlu diperiksa rekaman-demirekaman untuk menemukan rekaman yang diinginkan. Kalau pembacaan diteruskan melewati posisi dimana rekaman seharusnya berada (mengingat berkas sudah diurutkan), maka proses pencarian dihentikan. Untuk membaca Sunaryono hanya diperlukan 2 probe, lebih kecil disbanding berkas sebelum diurutkan. Namun teknik tersebut masih kurang memuaskan untuk berkas dengan jumlah rekaman yang lebih besar. A. PENCARIAN BINER (BINARY SEARCH) Pencarian Biner dalah membandingkan kunci yang dicari dengan rekaman pada posisi tengah dari berkas. Bila sama (Kasus 1) rekaman yang diinginkan sudah ditemukan. Jika tidak sama (kasus 2), berarti separuh rekaman-rekaman dalam berkas akan dieliminasi dari perbandingan yang selanjutnya. Bila yang terjadi pada kasus 2, maka proses perbandingan terhadap rekaman pada posisi di tengah dilanjutkan menggunakan rekaman-rekaman yang tersisa. Jumlah probe (yang diperlukan untuk membaca sebuah rekaman) pada sebuah berkas dengan rekaman yang sudah diurutkan, dapat diperkecil dengan menggunakan teknik pencarian biner. Jika kunci cari < kunci tengah maka bagian berkas mulai dari kunci tengah sampai akhir berkas dieliminiasi. sebaliknya jika kunci cari > kunci tengah, maka bagian berkas mulai dari depan sampai dengan kunci tengah dieliminiasi. Dengan mengulang proses perbandingan terhadap rekaman tengah, maka lokasi rekaman yang diinginkan akan ditemukan atau diketahui bahwa rekaman yang diinginkan tersebut tidak berada dalam berkas.

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 12

Algoritma pencarian biner: Proc pencarian_biner */ n buah rekaman dalam berkas diurutkan menaik menurut kunci rekaman */ AWAL := 1 AKHIR := n While AWAL kunci(tengah) Then AWAL := Tengah + 1 Else AKHIR := tengah - 1 End Rekaman tidak ditemukan End pencarian_biner

B. PENCARIAN INTERPOLASI Pencarian interpolasi (asumsinya kunci rekaman numeris) menentukan posisi yang akan dibandingkan berikutnya berdasar posisi yang di estimasi dari sisa rekaman yang belum diperiksa. Pencarian interpolasi tidak mencari posisi tengah, seperti algoritma pencarian biner, melainkan menentukan posisi berikutnya. Proc pencarian_interpolasi */ n buah rekaman dalam berkas diurutkan menaik menurut kunci rekaman */ AWAL := 1 AKHIR := n While AWAL kunci(BERIKUT) Then AWAL := BERIKUT + 1 Else AKHIR := BERIKUT - 1 End Rekaman tidak ditemukan End pencarian_interpolasi

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 13

Sesi 6

Materi 5 ORGANISASI BERKAS LANGSUNGPengguna teknologi pada umumnya dan teknologi informasi pada khususnya merasa bahwa waktu yang diperlukan untuk memperoleh suatu informasi masih terlalu lama. Metode pencarian biner maupun interpolasi masih belum dapat mengimbangi ketidaksabaran manusia terhadap penyediaan informasi yang cepat dan akurat. Perkembangan media perekam data dalam hal kemampuan untuk menampung volume data yang sangat besar harus diimbangi dengan peningkatan teknik pencarian kembali data yang tersimpan.

A. KUNCI SEBAGAI ALAMAT REKAMAN YANG UNIKUntuk mendapat rekaman yang diasosiasikan dengan suatu kunci primer, sangat diharapkan agar proses langsung menuju ke alamat tempat rekaman dengan kunci tertentu disimpan. Hal tersebut mungkin terjadi apabila satu kunci rekaman juga merupakan alamat lokasi rekaman. Untuk aplikasi rekaman berisi nomor induk mahasiswa, terdapat 8 digit (kunci rekaman yang merupakan gabungan 2 digit tahun angkatan + 2 digit kode program studi + 4 digit nomor urut), maka diperlukan lokasi sebanyak 99.999.999. Dengan demikian waktu pencarian akan sangat baik, yaitu 1 probe untuk setiap rekaman yang dicari. Akan tetapi, teknik tersebut memiliki kerugian karena diperlukan ruang yang sangat besar untuk menampung semua rekaman. Untuk menampung data NIM mahasiswa diperlukan ruang yang besar, meski jumlah mahasiswa mungkin hanya 500, pasti ada beberapa nomor yang kosong karena beberapa alasan, misalnya sudah lulus, mengundurkan diri, drop-out, cuti, dan sebagainya. Sehingga tidak semua ruang dimanfaatkan.

B. KONVERSI KUNCI REKAMAN MENJADI SATU ALAMAT YANG UNIKContoh klasik yang menggambarkan fenomena konversi kunci rekaman adalah sistem reservasi penerbangan. Jika suatu maskapai penerbangan memiliki nomor penerbangan dari 1 sampai 999, ingin memantau reservasi pesawat selama setahun yang jumlah harinya 1 sampai 366 (1 tahun), maka nomor penerbangan dan hari-ke dapat dihubungkan untuk mendapatkan lokasi rekaman yang berisi data reservasi penerbangan pada hari tertentu.LOKASI = NOMOR PENERBANGAN + HARI-KE DALAM TAHUN INI

Dengan simbol + menandakan hubungan, maka untuk menyediakan semua kemungkinan penerbangan diperlukan ruang alamat sebesar 999366 unit. Jumlah tersebut dapat direduksi sampai dengan 30% bila digunakan kombinasi:LOKASI = HARI-KE DALAM TAHUN INI + NOMOR PENERBANGAN

Karena kecil kemungkinan dalam satu maskapai terdapat lebih dari 100 penerbangan, maka ruang alamat maksimum yang diperlukan adalah 36699. Dinny Wahyu Widarti, S.Kom Sistem Berkas - 14

C. MENENTUKAN ALAMAT DENGAN KONVERSI KUNCIDiperlukan satu fungsi untuk memetakkan cakupan nilai kunci yang lebih luas ke dalam cakupan yang lebih sempit nilai alamat. Fungsi yang dikenal dengan fungsi hash akan melakukan pemetaan sebagaimana diharapkan. Hash (kunci) kemungkinan alamat Keluaran dari proses hashing bukan lagi alamat yang unik, melainkan kemungkinan alamat bagi kunci yang di hash. Alamat untuk menempatkan alamat yang diperoleh dari fungsi hash disebut home-address untuk rekaman tersebut. Tidak ada batasan mengenai bentuk fungsi yang akan memetakkan kunci ke cakupan alamat, tetapi diharapkan fungsi tersebut menghasilkan kemungkinan alamat yang: Mampu mendistribusi kunci secara merata ke dalam cakupan alamat. Hal tersebut dimaksudkan untuk mengurangi terjadinya kolisi. Kolisi terjadi bila hasil hashing dua kunci rekaman yang berbeda menunjuk ke alamat yang persis sama. Dapat dieksekusi dengan efisien. Hal tersebut dimaksudkan agar waktu pembacaan dapat ditekan seminimal mungkin. Maka fungsi hashing dapat dipandang dari 2 aspek, yaitu: Fungsi hash itu sendiri Metode untuk meresolusi kolisi Mekanisme resolusi kolusi diperlukan untuk mengatasi terjadinya jumlah rekaman yang dikonversikan ke suatu lokasi melebihi kapasitasnya. Dalam bahasan ini diasumsikan bahawa satu lokasi memiliki kapasitas satu rekaman. Berikut adalah beberapa fungsi hash, dimulai dari yang paling sering digunakan. a) Hashing dengan Kunci Modulus N Satu fungsi hash yang paling popular dan paling sering diimplementasikan adalah modulus N, f (kunci) = kunci mod N dengan N sebagai ukuran tabel atau berkas. Hasil fungsi modulus adalah sisa pembagian kunci oleh N. Sabagai contoh untuk N=12 maka: 30 mod N = 6 40 mod N = 4 Keuntungan fungsi ini hanya menghasilkan nilai dalam rentang ruang alamat (0) sampai dengan (N-1) b) Hashing dengan Kunci Modulus P Fungsi hashing Kunci mod P merupakan variasi fungsi modulus N, rumusnya adalah: f (kunci) = kunci mod P dengan P sebagai bilangan prima terkecil yang lebih besar atau sama dengan N. dan N adalah ukuran tabel. P ini kemudian menjadi ukuran tabel baru yang menggantikan N. Contoh: untuk N=12 maka P=13 30 mod P = 4 40 mod P = 1

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 15

c) Hashing dengan Pemotongan Alternatif lain untuk fungsi hashing adalah pemotongan. Sebagai contoh adalah para pegawai negeri sipil di Indonesia. Para pegawai memiliki NIP (Nomor Induk Pegawai) dengan panjang total 9 digit, terdiri atas 3 digit pertama sebagai identitas departemen, sementara 6 digit terakhir adalah nomor urutnya. Bila ingin dijadikan 6 digit saja, maka bisa dilakukan pemotongan jumlah digit. Pemotongan bisa dilakukan dibagian mana saja, tentunya dengan konsekuensi masing-masing. Pada kasus NIP, jika pemotongan dilakukan pada bagian belakang, akan diperoleh sejumlah alamat yang memiliki 3 digit yang sama (identitas departemen) sehingga kemudian kolisinya akan lebih besar dibanding bila pemotongan dilakukan di bagian depan. d) Hashing dengan Lipatan Fungsi ini melipat digit pada batasan yang ditentukan berdasarkan kondisi digit awal dan digit yang akan dihasilkan. Sebagai contoh 9 digit NIP akan direduksi menjadi 3 digit, maka digit awal di bagi 3, kemudian dilipat pada batas antar-bagian. Contoh : 5 8 3 9 7 6 1 2 4 Kunci asli tersebut ditulis pada selembar kertas. Batasan dimana lipatan akan dilakukan ditandai dengan garis . Penjumlahan dari susunan tersebut adalah: 385 976 421 ----- + Jika penjumlahan dilakukan dengan mengabaikan carry maka diperoleh alamat 672, sedangkan jika tidak mengabaikan carry maka hasilnya 782. e) Hashing dengan Penggeseran Hashing dengan penggeseran memiliki proses yang serupa dengan hashing lipatan, bedanya setelah ditentukan batasan. Digit asli dipotong kemudian digeser dan dihitung hasil jumlahnya. 583 976 124 ----- + Yang diperoleh alamat yang berbeda yaitu 573 (tanpa carry). Jika kedua hasil penjumlahan tersebut diterapkan dengan menggunakan carry dan hanya tiga digit yang paling kanan saja yang digunakan, maka diperoleh 683. f) Hashing dengan Pengkuadratan Hashing dengan penguadratan adalah fungsi hashing dengan menguadratkan kunci. Hasil penguadratan ini kemudian dapat dikombinasi dengan pemotongan atau lipatan untuk mendapatkan alamat yang diperbolehkan. Sebagai contoh, penguadratan kunci 782 akan menghasilkan kemungkinan alamat 117. F(782) = 117 Dinny Wahyu Widarti, S.Kom Sistem Berkas - 16

g) Hashing dengan Konversi Radix Dalam konversi radix, kunci dianggap dalam base selain 10 yang kemudian dikonversi ke dalam basis 10, misal kunci 5 6 7 8 dalam base 13 akan menghasilkan 12098, diperoleh dari: 5678Posisi: 3 2 1 0

Hasil tersebut masih dapat dikombinasi dengan fungsi hash lain (pemotongan atau lipatan) untuk mendapatkan digit alamat yang diinginkan.

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 17

Sesi 7

Materi 6 ORGANISASI BERKAS DENGAN BANYAK KUNCIA. METODE ORGANISASI Ada banyak teknik yang dipakai untuk organisasi file dengan banyak kunci. Berikut ini dua teknik dasar untuk pemberian hubungan antara sebuah index dan data record dari file, yaitu: 1. Inverted 2. Multilist Banyak bahasa program kompilator tidak memberikan kemampuan untuk mendukung organisasi file banyak kunci. Karenanya diperlukan paket program tambahan untuk mendukung sistem pengolahan data manajemen yang hampIr semuanya menggunakan organisasi file banyak kunci. Contoh sebuah sistem perbankan yang mempunyai beberapa pemakai seperti kasir, pegawai kredit, manajer cabang, pegawai bank, nasabah, dll. Semuanya memerlukan akses data yang sama dengan format record sebagai berikut:ID NAMA DEPAN AKHIR KODE GROUP CABANG TYPE NO SOSIAL SOCIATY SALDO OVERDRAW LIMIT

Adanya pemakai yang berbeda memerlukan akses record-record ini dengan cara yang berbeda. Seorang kasir hendak mengidentifikasi sebuah record account menurut IDnya. Seorang pegawai kredit memerlukan akses semua record menurut nilai overdrawlimit atau semua record account dengan sebuah nilai No Sosial Sociaty. Seorang manajer cabang hendak membuat laporan berkala untuk semua record account yang disortir berdasarkan ID. Seorang nasabah memerlukan akses recordnya dengan memberikan ID yang dipunyainya atau kombinasi dari Nama, No Sosial Sociaty, dan Type. Satu pendekatan yang dapat mendukung semua jenis akses adalah dipunyainya banyak file yang berbeda. Setiap file diorganisasi untuk melayani satu jenis keperluan. Untuk contoh adalah sistem perbankan di atas, harus ada: a. File account yang organisasinya sekuensial dengan nilai kunci ID (untuk melayani kasir, pegawai bank, dan nasabah). b. File account yang organisasinya sekuensial dengan record diurut menurut Overdraw-Limit (untuk melayani pegawai kredit). c. File account yang organisasinya relatif dengan kunci No SS (untuk melayani pegawai kredit). d. File account yang organisasinya sequensial dengan record diurut menurut kode group (melayani manajer cabang). e. File account yang organisasinya relative dengan nilai kunci Nama, NoSS dan Type (untuk melayani nasabah) Kita memiliki 5 file yang semuanya mempunyai record yang sama. Kelima file ini hanya berbeda dalam organisasinya dan cara aksesnya.

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 18

Pengulangan data dari beberapa file bukan merupakan cara yang baik untuk mengakses record dengan berbagai cara. Lagi pula cara ini memerlukan ruang yang besar di penyimpanan dan kesulitan pada waktu pemutakhiran record secara serentak. File dengan organisasi banyak kunci adalah cara terbaik untuk mengatasi masalah di atas. File ini menggunakan indeks dan bukan pengulangan data seperti cara diatas. Konsep dari akses banyak kunci umumnya diimplementasikan dengan pembentukan banyak indeks untuk memberikan yang berbeda terhadap record. Cara ini menggunakan linked-list. B. FILE TERBALIK (INVERTED FILE) 1. Metode Akses pada File Terbalik (Inverted File Access method) Setiap daftar file yang dibalik, alamat atau key untuk semua record memiliki atribut yang sama. Contoh: Bagian File Personel Alamat Record Nomor Pegawai 101 28541 102 35879 103 47853 104 50917 File Inverted dengan Index Umur Umur Alamat Record 18-25 104, 26-35 102, 103, 36-45 101, Beberapa file diperlukan jika mempertimbangkan untuk melokasikan record yang memakai 1 atau lebih atribut. Data diperlukan untuk menjelaskan hubungan dan alamat record yang ditunjukkan dengan file-file inverted yang diketahui sebagai pengeluaran tambahan data. 2. Contoh Pemakaian File Terbalik No.Rec 1 1234 : Adam : SBD : 2 5678 : Bruce : SB : 3 9012 : Clarck : SBD : 4 3456 : David : SB : 5 7890 : Erik : PSI : 6 DIRECTORY Search Key Address List SB 2,4 PSI 5 SBD 1,3

Umur 43 27 32 24

3 4 0 0 0

DATAFILE No.Rec 1 1234 : Adam : SBD : 2 5678 : Bruce : SB : 3 9012 : Clarck : SBD : 4 3456 : David : SB : 5 7890 : Erik : PSI :

Pengindekan dengan Pengalamatan tidak langsung yaitu: 1. Inversion bisa menggunakan kunci yang bukan nilai yang unik. Seperti indeks berdasarkan kunci Kode-Group. Dinny Wahyu Widarti, S.Kom Sistem Berkas - 19

Kode-Group ID Tipe-Cabang DT 001 111111, 201431, 310103 DT 002 198121 NW 001 112131, 208432 NW 002 291821 NE 002 300123 2. Struktur Index Inversion menggunakan Pengalamatan tidak langsung dengan nilai No.Soc. No.Society 001234123 123456789 399142131 412631467 459463001 513014265 713214622 821346211 C. FILE MULTILIST File multilist mempunyai sebuah indeks untuk setiap kunci sekunder. Organisasi multilist berbeda dengan file terbalik dimana dalam indek inverse untuk sebuah nilai kunci mempunyai sebuah petunjuk untuk data record pertama dengan nilai kunci, sedangkan dalam indeks multilist untuk sebuah nilai kunci mempunyai hanya sebuah petunjuk untuk data record pertama dengan nilai kunci. Data record mempunyai sebuah penujuk untuk data record selanjutnya dengan nilai kunci dan seterusnya. Karena terdapat sebuah linked-list dari data record untuk setiap nilai dari kunci sekunder. Contoh File data dengan struktur MultiList:Alamat Record 1 2 3 4 5 6 7 8 ID 111111 112131 198121 201431 208432 291821 300123 310103 Nama Amor Joni Hendar Peter Andini Arianti Hardi Tahue Kode_Group Tipe_cabang DT001 NW001 DT002 DT001 NW001 NW002 NE002 DT001 Next 201431 208432 355812 310103 511211 0. 696123 686116 No.Society 459463001 821346211 713214622 399042131 12345678 001234123 412631467 513014265 Saldo 100.75 2311.20 191.87 3142.93 95.26 146.92 3000.00 243.63 Batas Penarikan 0. 100. 200 100 0. 0. 100 0. Next 208432 201431 0. 300123 291821 3101103 386132 324196

ID 291821 208432 201431 300123 111111 310103 198121 112131

Pada tabel dibawah ini menunjukkan multi-list untuk kunci sekunder Kode-group. Setiap data record mempunyai tempat penunjuk untuk mengakses record selanjutnya.Kode_Group Tipe_cabang DT001 NW001 DT002 DT001 NW001 NW002 NE002 DT001 ID 111111 112131 198121 201431 208432 291821 300123 310103

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 20

Nilai kunci harus diurut, struktur indek adalah tabel dengan indirect addressing dan mempunyai hubungan data record yang disusun menurut ID secara menaik. Hasil sebuah struktur multilist adalah sebuah kunci sekunder yang mempunyai nilai unik atau tunggal. Ini berarti ada N data record maka ada N nilai kunci sekunder dalam indeks yang menunjukkan record pertama. Contoh pengindekan untuk File MultiList:Kode_Group Tipe_cabang DT001 NW001 DT002 DT001 NW001 NW002 NE002 DT001 ID 111111 112131 198121 201431 208432 291821 300123 310103 Panjang 4 4 3 1 2 3 1 1 2

Dinny Wahyu Widarti, S.Kom

Sistem Berkas - 21