STRUKTUR DAN ORGANISASI DATA 1
BAB I
ORGANISASI FILE dan FILE SEQUENTIAL
Merupakan suatu teknik/cara yang digunakan menyatakan dan menyimpan record-record dalam sebuah file.
Penyimpanan atau dalam penulisan karakter demi karakter didalam external memory, harus diatur sehingga komputer bisa dengan mudah menemukan kembali data-data yang tersimpan didalamnya.
Organisasi file sequential juga merupakan cara paling dasar untuk mengorganisasikan kumpulan record record dalam sebuah file .
4 Teknik Dasar Organisasi File :
Sequential
Organisasi File Sequential merupakan suatu cara penyimpanan dan pembacaan data yang dilakukan secara berurutan. Data yang ada akan disimpan sesuai dengan urutan masuknya. Data pertama dengan nomor berapapun, akan disimpan ditempat pertama, demikian dengan data berikutnya yang juga akan disimpan ditempat berikutnya.
Begitu pula dalam melakukan pembacaan data, dilakukan secara berurutan, maksudnya pembacaan akan dimulai dari data paling pertama dan dilanjutkan dengan data berikutnya sehingga data yang dimaksud bisa ditemukan
Proses
Dalam organisasi file sekuential record-recordnya harus diakses secara berurutan, maka file sekuential lebih sering menggunakan batch processing dari pada interactive processing.
Batch merupakan suatu proses yang dilakukan secara group atau kelompok.
Interactive merupakan suatu proses yang dilakukan secara satu persatu, yaitu record demi record.
Operasi File sequential terdiri dari : Penyisipan Record, Penghapusan
Record dan Perubahan Isi Record
Pembuatan File Sequential
Yang meliputi penulisan record-record dalam serangkaian yang diinginkan pada media penyimpanan.
Yang termasuk pembuatan file sequential :
☺Pengumpulan data
Proses dimana data yang ada dikumpulkan secara berurut berdasarkan klasifikasi yang membedakannya. Pada tahap pengumpulan data ini, semua data akan diurutkan secara bertahap dan terorganisir dengan baik. Contohnya database kemahasiswaan seperti menampilkan IPK, menampilkan mata kuliah dan menmpilkan Biodata mahasiswa.
☺Perubahan data dalam bentuk bahasa yan dapat dibaca oleh mesin
☺Pemasukan data
Data-data yang telah dibedakan dan dikumpulkan akan secara permanent dimasukkan (di input) kedalam suatu device penyimpanan. Device (media) penyimpanan ini dapat berupa memori atau device penyimpanan lainnya. Contohnya adalah Data pribadi dan KRS Mahasiswa.
☺Pengeditan data
Data yang ada dikumpulkan dan proses input data juga telah dilakukan maka proses selanjutnya adalah editing. Data yang telah di input akan diubah (edit). Yang berlangsung berdasarkan pengguna atau user. User sangat dominan dalam proses ini, sebab proses pengeditan data yang ada berdasarkan perintah kerja dari user.
☺Pemerikasaan tranksaksi yang ditolak
☺Penyortiran data yang telah diedit
Setelah user melakukan pengeditan pada data-data yang ada, maka selanjutnya data yang telah di edit tersebut kan di sortir. Dalam proses penyortiran ini, peran user juga sangat dominan dalam mempengaruhi hasil dari penyortiran yang dilakukan.
Begitu pula pada waktu pengaksesan dan pada waktu file ini digunakan sebagai input, record-record harus diakses secara berurutan.
Jika ingin menambah record pada file sequential, maka record tersebut akan tercetak pada akhir berkas .
3 jenis record pembuatan file laporan sequential
Header record
Meliputi report header page header dan group header. Biasa disebut sebagai informasi pengenal ( identifying information )
Detail record
Meliputi isi laporan yang umumnya disusun dalam kolom .
Footer record
Meliputi report footer page footer dan group footer. Biasa disebut sebagai informasi ringkasan ( Summary information ) .
Media penyimpanan file sequential
SASD seperti maknetic tape
DASD seperti maknetic disk, alasannya komputer dihubungkan dengan sedikit tape drive sehingga tidak cukup untuk menunjang program aplikasi yang banyak membutuhkan file sequential
Keuntungan Sequential File :
Merupakan organisasi file yang sederhana
Jarak setiap aplikasi yang tersimpan sangat jelas
Metode penyimpanan didalam memory sangat sederhana, sehingga efisien untuk menyimpan record yang besar
Sangat murah untuk digunakan, sebab medianya cukup menggunakan magnetic tape.
Kemampuan untuk mengakses record berikutnya secara cepat
Kerugian Sequential File :
Jika diperlukan perubahan data, maka seluruh record yang tersimpan didalam master file, harus semuanya diproses
Data yang tersimpan harus sudah urut (sorted)
Posisi data yang tersimpan sangat susah untuk uptodate, sebab master file hanya  bisa berubah saat proses selesai dilakukan
Tidak bisa dilakukan pembacaan secara langsung
BAB II
FILE RELATIF
Merupakan suatu teknik/cara yang efektif dalam mengorganisasi sekumpulan record yang membutuhkan akses record dengan cepat. Dalam file relatif ada hubungan antara key yang dipakai untuk mengidentifikasi record dengan lokasi record dalam penyimpanan sekunder.
Record tidak perlu tersortir secara fisik menurut nilai key.
Untuk mencari record ke-N. Buat hubungan yang akan menerjemahkan antara NILAI KEY dan ADDRESS.
Hubungan ini dinyatakan sebagai R, yang merupakan fungsi pemetaan.
R(NILAI KEY)  →  ADDRESS
õ Tidak perlu mengakses semua record master file, cukup mengakses langsung record yang dikehendaki.
õ Record dari file relatif dapat diupdate langsung tanpa perlu merekam kembali  semua record.
Proses
Record ditulis ke dalam berkas relatif, fungsi pemetaan R digunakan untuk menerjemahkan NILAI KEY dari record menjadi ADDRESS, dimana record disimpan.
Organisasi file relatif paling sering digunakan dalam proses interaktif
Pola Akses
Merupakan penentuan akses berdasarkan field tertentu. Dalam file relatif tidak perlu mengakses record secara berurutan (consecutive).
Media Penyimpanan File Relatif
Organisasi berkas relatif ini tidak menguntungkan bila penyimpanan sekundernya berupa media SASD seperti magnetic tape. Berkas relatif harus disimpan dalam media DASD seperti magnetic disk atau drum.
Retrieval terhadap File Relatif
pada waktu akan me-retrieve record dengan nilai key tertentu, fungsi pemetaan R digunakan terhadap nilai key tersebut, untuk menerjemahkan nilai key itu menjadi sebuah address dalam penyimpanan sekunder, dimana record tersebut ditemukan.
ð Retrieval merupakan pengaksesan file dengan tujuan untuk mendapatka informasi
3 teknik dasar yang digunakan untuk menyatakan fungsi pemetaan R, dimana
R(NILAI KEY) → ADDRESS
♣ Teknik Pemetaan Langsung
Merupakan teknik yang sederhana untuk menerjemahkan nilai record key menjadi address.
2 cara pemetaan langsung :
a. Teknik Absolute Addressing (Pengalamatan Mutlak)
R(NILAI KEY)  →  ADDRESS
NILAI KEY Â Â Â Â = ALAMAT MUTLAK
Jika nilai key yang diberikan oleh pemakai program sama dengan address sebenarnya dari record tersebut pada penyimpanan sekunder.
Keuntungan dari pengalamatan mutlak
Fungsi pemetaan R sangat sederhana
Tidak membutuhkan waktu lama dalam menentukan lokasi record pada penyimpanan sekunder
Kelemahannya dari pengalamatan mutlak
Pemakai harus mengetahui dengan pasti record-record yang disimpan secara fisik
Alamat mutlak adalah device dependent, perbaikan atau pengubahan device, dimana berkas berada akan mengubah nilai key
Alamat mutlak adalah address space dependent, reorganisasi berkas relatif akan menyebabkan nilai key berubah.
b. Teknik Relative Addressing (Pengalamatan Relatif)
R(NILAI KEY) → ADDRESS
NILAI KEY Â Â Â = ALAMAT RELATIF
Alamat relatif dari record dalam file adalah urutan record tersebut dalam file.
Keuntungan dari pengalamatan relatif
Fungsi pemetaan R sangat sederhana
Nilai key dari sebuah record dapat ditentukan lokasi recordnya dalam sebuah penyimpanan sekunder tanpa memerlukan waktu proses yang berarti.
Kelemahannya dari pengalamatan relatif
Alamat relatif adalah bukan device dependent
Alamat relatif adalah address space dependent
Terjadinya pemborosan ruangan.
Ruang harus disediakan sebanyak jangkauan nilai key, terlepas dari berapa banyak nilai key.
Ditemukannya alamat relatif yang sama untuk nilai key yang berbeda.
Teknik Pencarian Tabel.
Dasar pemikiran pendekatan pencarian tabel adalah tabel atau direktori dari nilai key dan address.
Keuntungan Pencarian Tabel
Record dapat diakses dengan cepat, setelah nilai  key dalam direktori ditentukan
Nilai key dapat berupa field yang mudah dimengerti seperti PART  NUMBER,  NPM, karena nilai  key  tersebut  akan diterjemahkan menjadi alamat
Nilai key adalah address  space  independent,  dimana reorganisasi berkas tak akan memepengaruhi nilai key, yang berubah adalah alamat dalam direktori
Teknik Kalkulasi Alamat
R(NILAI KEY)  → ADDRESS
Adalah dengan melakukan kalkulasi terhadap nilai key, hasilnya adalah alamat relatif.
R(K1)Â =Â R(K2) Â Â Â disebut benturan
K1     ≠ K2       atau collision
nilai key K1 dan K2 disebut synomin.
Synonim adalah dua atau lebih nilai key yang berbeda pada hash ke home address yang sama.
Teknik Kalkulasi Alamat
Scatter storage techniques
Randomizing techniques
Key-to-address transformation methods
Direct addressing techniques
Hash table methods
Hashing merupakan Kalkulasi terhadap nilai key untuk mendapatkan sebuah alamat disebut fungsi hash.
Keuntungan pemakaian Hashing
Nilai key yang sebenarnya dapat dipakai karena diterjemahkan kedalam sebuah alamat.
Nilai key adalah address space independent bila berkas direorganisasi, fungsi hash berubah tetapi nilai key tetap.
Kelemahannya pemakaian Hashing :
Membutuhkan waktu proses dalam mengimplementasikan fungsi hash.
Membutuhkan waktu proses dan akses I/O dalam mengatasi benturan.
Hashing dapat digunakan bersama-sama dengan pencarian tabel.
Penampilan fungsi hash bergantung pada :
Distribusi nilai key yang dipakai
Banyaknya nilai key yang dipakai relatif terhadap ukuran dari ruang alamat.
Banyaknya record yang dapat disimpan pada alamat tertentu tanpa menyebabkan benturan.
Teknik yang dipakai untuk mengatasi benturan
Beberapa fungsi hash yang umum digunakan :
Division Remainder
alamat relatif dari suatu nilai key merupakan sisa dari hasil pembagian nilai key tersebut dengan suatu bilangan yang disebut sebagai bilangan pembagi.
Untuk mengukur kepenuhan file relatif digunakan Load Factor (Faktor Muat).
Load Factor =    banyak record dalam berkas
max. banyak record dalam berkas
Biasanya load factor yang sering digunakan adalah 0.7 atau 0.8.
Load factor lebih besar dari 0.7 atau 0.8 maka berkas tersebut harus diperbesar dan direorganisasi.
Jika ingin menyimpan sebanyak n record pada suatu file dan load factor adalah 0.8, maka max. banyak record pada file adalah 1.25 n.
0.8 = Â Â n
max
max = 1.25 n
Mid Square Hashing
Untuk mendapatkan alamat relatif, nilai key dikuadratkan, kemudian beberapa digit diambil dari tengah .
c. Folding Hashing
Untuk mendapatkan alamat relatif, nilai key dibagi  menjadi beberapa bagian, setiap bagian (kecuali bagian terakhir) mempunyai jumlah digit yang sama dengan alamat relatif.
Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah.
Hasilnya, digit yang tertinggi dibuang (bila diperlukan).
Perbandingan fungsi Hash
Teknik Division Remainder memberikan penampilan yang terbaik secara keseluruhan.
Teknik Mid Square dapat dipakai untuk file dengan load factor cukup rendah akan memberikan penampilan baik tetapi kadang-kadang dapat menghasilkan penampilan  yang  buruk  dengan  beberapa collision.
Teknik folding adalah teknik yang paling mudah dalam perhitungan tetapi dapat memberikan hasil yang salah, kecuali panjang nilai key = panjang address.
2 pendekatan dasar untuk menetapkan dimana K2 harus disimpan :
a. Open Addressing
Menemukan address yang bukan home address untuk K2 dalam berkas relatif.
b. Separate Overflow
Menemukan address untuk K2 diluar dari primary area dalam file relatif, yaitu di overflow area yang dipakai hanya untuk menyimpan record-record yang tak dapat disimpan di home addressnya.
2 teknik untuk mengatasi collision :
Linier Probing, yang merupakan teknik open addresing.
cara menemukan lokasi record yang tak dapat disimpan di home addressnya dan proses pencarian secara sequential/linear dari home address sampai lokasi yang kosong.
File dengan load factor <>
b. Double Hashing, yang dapat dipakai selain open addressing atau separate overflow.
cara menemukan lokasi sebuah record pada waktu record tersebut tidak dapat disimpan dalam home addressnya dan akan memakai fungsi hash kedua terhadap hasil dari fungsi hash pertama.
File dengan load factor <>
Address dari record yang dihash kembali dapat terletak pada primary area atau di separate overflow area.
Metode ini membutuhkan pengeluaran tambahan untuk pemeliharaan berkas.
File relatif dibagi menjadi 2 file , yaitu :
Primary area dan Overflow area
Keuntungan metode separate overflow adalah
menghindari keadaan dimana dapat terjadi metode open addressing untuk sebuah record yang tak disimpan dalam home addressnya menggantikan record lain yang terakhir di hash ke home addressnya. Masalah ini dapat dihindari dengan open addressing atau separate overflow sederhana dengan memindahkan record yang sebelumnya ke lokasi lain (dengan probing atau hashing kembali) dan menyimpan record yang baru ketempat yang kosong.
Perbandingan Linear Probing dan Double Hashing
Load Factor <>
Load Factor > 0.8 : Double Hashing > Linear Probing
±Synonim Chaining
Pendekatan pemecahan collision yang mengakses synonim dengan fasilitas link list untuk record-recordnya dalam kelas ekivalen. Adapun link list record-record dengan home address yang sama tak akan mengurangi jumlah collision, tetapi akan mengurangi waktu akses untuk me-retrieve record-record yang tak ada di home addressnya.
±Bucket Addressing
Pendekatan lain dalam mengatasi collision adalah hash ke dalam block atau bucket yang dapat memberikan tempat sejumlah record.
Record-record yang disimpan dalam bucket dapat dikelola dalam :
Dapat disisipkan dalam urutan berdasarkan penempatannya di bucket.
Dapat dipertahankan urutan nilai key-nya.
Bucket addressing ini umum dipakai.
Ukuran dari sebuah bucket dapat ditentukan oleh ukuran track atau sektor dalam DASD. Ukuran bucket umumnya sama dengan ukuran block untuk file.
Keuntungan penggunaan bucket dapat menampung banyak record dengan panjang yang berbeda dapat dipakai
BAB III
FILE INDEX SEQUENSIAL
Merupakan cara paling efektif untuk mengorganisasi kumpulan record-record yang membutuhkan akses record secara sequential maupun akses record secara individu berdasarkan nilai key.
Teknik penyimpanan yang dilakukan, menggunakan suatu index yang isinya berupa bagian dari data yang sudah tersortir.
Index diakhiri dengan adanya pointer (penunjuk) yang menunjukkan secara jelas posisi data yang selengkapnya. Index yang ada juga merupakan record-key (kunci record), sehingga kalau record key ini dipanggil, maka seluruh data juga akan ikut terpanggil.
Struktur File Index Sequential
Index  → Binary Search Tree
Data    →  Sequential
Indeksnya digunakan untuk melayani sebuah permintaan untuk mengakses record tertentu
File data sequential digunakan untuk mendukung akses sequential terhadap seluruh kumpulan record-record
Struktur Pohon
Pohon (tree) adalah struktur dari sekumpulan elemen
Salah satu elemennya merupakan akarnya atau root, dan sisanya yang lain merupakan bagian-bagian pohon yang terorganisasi dalam susunan berhirarki, dengan root sebagai puncaknya.
Pohon Biner
Tipe pohon yang paling banyak dipelajari adalah pohon biner. Pohon Biner adalah pohon yang setiap simpulnya memiliki paling banyak dua buah cabang / anak.
Implementasi Organisasi File Indeks Sequential
2 pendekatan dasar untuk mengimplementasikan konsep dari organisasi file indeks sequential :
☺ Blok Indeks dan Data (Dinamik)
File indeks dan file data diorganisasikan dalam blok.
File indeks memilii struktur tree, sedangkan file data mempunyai struktur sequential dengan ruang bebas yang didistribusikan antar populasi record.
☺ Prime dan Overflow Data Area (Statik)
Berdasarkan struktur indeks dimana struktur indeks ini lebih ditekankan pada karakteristik fisik dari penyimpanan, dibandingkan dengan distribusi secara logik dari nilai key.
Indeksnya ada beberapa tingkat, misalnya tingkat cylinder indeks dan tingkat track indeks.
Berkas datanya secara umum diimplementasikan sebagai 2 berkas, yaitu Prime Area Dan Overflow Area.
Kedua pendekatan tersebut menggunakan bagian indeks dan bagian data, dimana masing-masing menempati file yang terpisah.
Karena diimplementasikan pada organisasi internal yang berbeda. Masing-masing file tersebut harus menempati pada alat penyimpan yang bersifat Direct Access Storage Device (DASD).
Untuk membayangkan penyimpanan data dengan menggunakan teknik index sequential ini, bisa melihat daftar isi pada sebuah buku. Pada bagian disebelah kiri disebut sebagai index data yang berisi bagian dari data yang ada. Index data kemudian diakhiri dengan pointer yang menunjukkan posisi keseluruhan isi data.
Sebuah data yang terdiri Nomor, Nama, NL1, Nl2, dan NL3 bisa disimpan dengan menggunakan Nomor sebagai Index. Apabila data tersebut dicetak, maka akan dihasilkan suatu data yang berurutan berdasar Nomor. Nomor yang ada akan tersusun dengan urutan dari kecil keurutan yang lebih besar.
Dari data yang ada, juga bisa dibuat Nama sebagai Index. Apabila data tersebut dicetak, maka akan dihasilkan suatu data yang berurutan berdasar Nama. Nama yang ada akan tersusun dengan urutan dari kecil keurutan yang lebih besar.
Index data akan dibaca pertama kali oleh komputer, dan dikarenakan didalam index data juga terdapat address maka data yang dicari bisa segera diketemukan. Data yang sudah terekam dalam methoda index-sequential juga dapat dilakukan pembacaan secara sequential. Key-field akan dibaca pertama kali secara sequential, dan untuk selanjutnya record yang dituju akan diketemukan.
Keuntungan Index Sequential File
Sangat cocok untuk digunakan menyimpan batch data ataupun individual data. Dibanding sequential file, pemanggilan data menjadi lebih cepat
Kerugian Index Sequential File
Access (pemanggilan) data tidak bisa disamakan dengan random (direct access file). Memerlukan adanya ruangan extra didalam memory untuk menyimpan index data. Memerlukan adanya hardware dan software yang lebih kompleks.
BAB IV
FILE MULTYKEY
Merupakan organisasi file yang memperbolehkan record diakses oleh lebih dari satu key field.
Pengulangan data dari beberapa file bukan merupakan cara yang baik untuk mengakses record dengan berbagai cara. Dan cara ini memerlukan space (ruang) yang besar di storage dan kesulitan pada waktu peng-update-an record secara serentak.
Untuk itu digunakan organisasi file banyak key, umumnya diimplementasikan dengan pembentukan banyak indeks untuk memberikan akses yang berbeda terhadap record data.
Mungkin juga cara ini memakai banyak link-list terhadap record. Dan sebuah indeks dapat dibentuk dengan beberapa cara, misal sebagai tabel binary search tree atau B-tree.
Banyak teknik yang dipakai untuk organisasi berkas dengan banyak key. Pendekatan bergantung pada pembentukan indeks yang dapat memberi akses langsung dengan banyak nilai key.
2 teknik dasar pemberian hubungan antara indeks dan data record dari berkas :
Inversion
Inversi merupakan pendekatan dasar untuk memberikan hubungan antara sebuah indeks dan data record dari file
Inverted file merupakan key pada indeks inversi mempunyai semua nilai key dimana masing-masing nilai key mempunyai penunjuk ke record yang bersangkutan
Indeks inversi yang sederhana dibentuk sebagai tabel.
Indeks inversi dapat dibuat bersama relatif file atau indeks sequential
Primary key merupakan key dipakai untuk menentukan struktur storage dari file disebut,
sedangkan key yang lainnya disebut secondary key.
Completely inverted merupakan file yang mempunyai indeks inversi untuk setiap data field
Partialy inverted file merupakan file yang bukan completely inverted tapi paling sedikit mempunyai satu indeks inversi
Variasi dari struktur indeks inversi adalah pemakaian secondary key dan primary key dari indirect addressing.
Pendekatan ini membiarkan file yang direorganisasi dan restructure secara fisik tanpa menyebabkan indeks file.
Multi-list
Merupakan pendekatan lain memberikan hubungan antara indeks dan data record dari file.
Multi-list file mempunyai indeks untuk setiap secondary key.
Untuk nilai key hanya memiliki penunjuk untuk data record pertama dengan nilai key . Data record memiliki penunjuk untuk data record selanjutnya dengan nilai key dan seterusnya. Maka terdapat linked-list dari data record untuk setiap nilai dari secondary key. Nilai key harus diurut.
Struktur indeks adalah tabel dengan indirect addressing dan mempunyai hubungan data record yang disusun menurut ID secara ascending.
SUMBER :
detty.staff.gunadarma.ac.id
ana.staff.gunadarma.ac.id
elearning.gunadarma.ac.id
http://mukharom1.wordpress.com/2009/10/28/struktur-dan-organisasi-data-1/
Tidak ada komentar:
Posting Komentar