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 :

  1. 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 :

  1. 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

  1. 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 :

  1. 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 < 0.5 pada linear probing akan menghasilkan synonim yang mengelompok

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 < 0.5 pada double hashing akan menghasilkan synonim yang berpencar

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 < 0.5  :  Double Hashing  =  Linear Probing

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

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: