1

ORGANISASI FILE

File diorganisasikan secara logik sebagai barisan rekord.

Rekord-rekord harus dipetakan ke blok-blok disk. Pemetaan ini

dilakukan pada lapisan bawah sistem manajemen file. File

merupakan bentukan di sistem operasi untuk penyimpanan data.

Blok-blok berukuran tetap pada satu media dan ditentukan oleh disk

dan sistem operasi, namun rekor-rekord dapat beragam ukuran.

Macam-macam Organisasi File

Organisasi File Dasar

Dua struktur file paling dasar, yaitu :

1. Pile ( tumpukan )

2. File sekuen berurut ( sequential file )

Struktur file dengan dilengkapi indeks, yaitu :

1. File sekuen berindeks ( indexed sequential file )

2. File berindeks majemuk (multiply indexed file)

Struktur file spesifik keperluan sistem komputer, yaitu :

1. File hash ( hashed file atau direct file )

2. File multiring (multiring file)

Pembahasan struktur file meliputi :

1. Deskripsi struktur file

2. Struktur dan pengaksesan

2

3. Penggunaan struktur file

4. Analisis kinerja

Pentingnya Pemilihan Organisasi File

1. Kebutuhan akan waktu tanggap yang cepat terhadap perangkat

lunak. Kecepatan perangkat lunak ditentukan oleh cara

perangkat lunak diprogram, dan pemilihan struktur/organisasi

file merupakan komponen yang signifikan dalam menentukan

kecepatan tanggap tersebut.

2. Perangkat lunak harus mudah dalam penggunaannya.

Perangkat lunak dibangun tidak hanya diukur dari kemudahan

implementasi, tapi juga kemudahan dalam penggunaannya.

3

1. File Pile

Struktur pile merupakan struktur paling sederhana. Struktur ini

merupakan basis evaluasi struktur lain.

File pile mempunyai karakteristik sebagai berikut :

1. mempunyai record tetap

2. mempunyai record yang field-fieldnya sama

3. disimpan dalam urutan kedatangan sehingga menumpuk satu

dengan yang lainnya.

4. pengaksesan yang dilakukan terhadap suatu record harus

terlebih dahulu melewati record-record sebelumnya.

5. tidak mempunyai urutan berdasarkan criteria tertentu.

Struktur dan Pengaksesan

Properti struktur Pile

1. Data tidak dianalisis, dikategorikan, atau harus memenuhi

definisi atau ukuran field tertentu.

2. Panjang record dapat bervariasi dan elemen-elemen data tidak

perlu serupa.

Karakteristik struktur Pile

1. Biasanya data ditumpuk secara kronologis

2. Tak ada keterkaitan antara ukuran file, record dan blok

3. Elemen data dapat beragam, berbeda untuk tiap record (berisi

atribut dan nilai)

4

4. Data harus disimpan secara lengkap beserta nama dan

atributnya, tidak cuma nilai atributnya

Komponen File Pile

- Hanya file yang berisi data bereserta nama atribut

Struktur dan Pengaksesan

Record berelasi dengan suatu obyek atau kejadian di dunia nyata.

Record berisi elemen-elemen (field-field) data. Tiap elemen

mempunyai identifikasi, dan identifikasi pada pile berupa penulisan

nama elemen secara eksplisit, misalnya :

umur = 20

dimana nilai elemen data adalah 20, dan nama deskripsi adalah

umur.

Operasi Penyisipan Record

Record-record disimpan segera setelah record sebelumnya Record-

recor ditempatkan di file sesuai urutan kedatangannya. Record yang

baru ditempatkan ke akhir file. Jika blok terakhir tidak mencukupi,

maka blok baru diminta ke sistem operasi untuk ditambahkan dan

record ditempatkan di blok terakhir tersebut.

Operasi Pencarian

Pada pile hanya terdapat pengakesan secara berturutan. Tidak

dimungkinkan pengambilan record secara acak tanpa membaca

record-record sebelumnya. Pencarian menggunakan metode

pencarian berturutan (linier serach) yang sangat lama. Karena

banyak operasi yang bergantung pada proses pencarian seperti

5

pembacaanm pembaruan (up date) dan penghapusan, maka seluruh

operasi yang bergantung pada operasi pencarian ini akan dilakukan

dengan sangat lambat.

Operasi Pembaruan

Pembaruan (up date) record dilakukan dengan membaca blok-blok

file secara berurutan ke memori utama untuk mencari blok yang

memuat record. Setelah ditemukan, maka record diubah, setelah

selesai, maka blok ditulis kembali ke penyimpanan sekunder.

Penggunaan Pile

Penggunaan file pile :

� File-file sistem

� File log (pencatat kegiatan)

� File-file penelitian/medis

� File teks

� Config.sys

Analisis Kinerja File Pile

A) Ukuran Record (R)

Ukuran record adalah :

R = a’ ( A +V + 2)

dimana :

a’ = rata-rata jumlah field pada satu record

6

A = panjang rata-rata nama (deskripsi) atribut

V = panjang rata-rata nilai atribut

B) Waktu Pengambilan Record Tertentu (T F)

Waktu untuk menemukan lokasi record pada pile adalah lama karena

semua record harus ditelusuri sampai menemukan lokasi item satu

data.

Mekanisme

Penelusuran sekuen dari record awal sampai menemukan record

yang dicari.

TF = ½ n

′tR

dimana :

n = jumlah record

R = ukuran record

t’ = bulk transfer rate

C) Waktu Pengambilan Record Berikutnya (T N)

Mekanisme

Penelusuran sekuen dari record awal sampai menemukan record

yang dicari

TN = TF

D) Waktu Penyisipan Record (T I)

Mekanisme

7

Penyisipan dilakukan di akhir file

Mekanisme penyisipan record adalah :

1. Cari akhir file (End Of File), diperlukan waktu sebesar seek time

(s)

2. Cari sektor yang tepat, diperlukan waktu sebesar rotational

latency (r)

3. Lakukan transfer data, diperlukan waktu sebesar btt

4. Read/write block data, diperlukan sebesar TRW

TI = s + 3r +btt

E) Waktu Pembaruan Record (T U)

Mekanisme

1. Mencari posisi record yang diperbarui

2. Memeriksa apakah ukuran tempat record masih memenuhi

syarat, yaitu :

� Bila ukuran record baru < record lama, maka dilakukan

penimpaan record

� Bila ukuran record baru = record lama, maka dilakukan

penimpaan record

� Bila ukuran record baru > record lama, maka dilakukan

penghapusan dan penyisipan record baru di akhir file

Terdapat dua kasus :

1. Hanya dilakukan Penimpaan, tanpa Penyisipan di a khir file

Pembaruan dengan penimpaan :

TU = TF + TRw , TRW ≅ 2r

8

2. Dilakukan Penandaan Hapus dan Penyisipan di akhi r file

Pembaruan dengan penghapusan dan penyisipan di akhir file :

TU = TF + TRw + TI

F) Waktu Pembacaan Seluruh Record (T X)

Mekanisme

Membaca dari record awal sampai akhir

Terdapat 2 kasus :

Bila urutan record tidak dipedulikan :

TX = 2 TF = n

t'

R

atau

TX = b

t'

B

Pembacaan Terurut atribut tertentu, terdapat 2 cara :

1. Pembacaan N kali

Bila pembacaan record menurut atribut tertentu, berarti

dilakukan n kali operasi get next (TN)

TX = n TN = nTF

2. Dilakukan Pengurutan lebih dahulu

TX = Tsort (n) = TX (sequential)

G) Waktu Reorganisasi File (T Y)

9

� Jika jumlah record tambahan selama satu periode adalah o dan

jumlah record yang ditandai hapus adalah d. File telah tumbuh

dari n menjadi n+o+d, sehingga waktu pengkopian file :

TY = (n+o)

't

R + (n+o+d)

't

R

2. File Sekuen Berurutan

Struktur sekuen berurutan adalah file berurut (ordered file) dimana

keberurutan record-record di file menurut suatu kriteria.

File Sekuen mempunyai karakteristik sebagai berikut :

1. atribut data dikategorikan. Record berisi semua nilai data atribut

dengan urutan dan posisi yang sama.

2. record-record data terurut dalam satu aturan/kriteria tertentu.

Kriteria ini dapat melibatkan satu field atau lebih, umumnya

adalah kunci record.

Komponen File Sekuen

Komponen file sekuen, yaitu :

1. File utama

10

2. File transaction log berstruktur pile

Struktur dan Pengaksesan

Struktur

1. Satu deskripsi tunggal diterapkan ke semua record di file

sekuen. Semua record identik.

2. Jika terdapat penambahan atribut baru ke record, seluruh file

harus direorganisasi, yaitu :

Setiap rekord ditulis ulang dengan ruang kosong (space) untuk

item data baru.

3. Bentuk record tetap (fixed record) mempermudah

pengaksesan.

Implementasi

1. Rekord-rekord dilink satu dengan yang lainnya seperti linked-

list secara terurut.

2. Rekord-rekord disimpan terurut secara fisik. Implementasi ini

meminimalkan pengaksesan blok sehingga meningkatkan

kinerja pengaksesan sekuen

Penyisipan

1. Penyisipan dilakukan di file pile, disebut file log transaksi

(transaction log file) atau file overflow. Penyisipan di file log

dilakukan sampai ukuran file besar.->80% terisi

2. Pembaruan secara batch dilakukan saat reorganisasi file.

11

Mekanisme Reorganisasi

1. File log transaksi diurutkan berdasar atribut kunci

2. Dilakukan penggabungan (file utama dan file log transaksi yang

terurut) menjadi file sekuen yang baru

Penggunaan File Sekuen

Penggunaan file sekuen :

� Commercial batch-oriented processing, dimana pembaruan

terhadap seluruh record diolah secara periodik

� Konsep file master dan file transaksi digunakan untuk

organisasi ini

� Penggabungan data dari sejumlah file sekuen diperlukan file

terurut sehingga seluruh data ditemukan dalam sekali

pencarian

Contoh :

� Monthly billing untuk perusahaan listrik, telepon dan

sebagainya

� Payroll application

Analisis Kinerja File Sekuen

A) Ukuran Record (R)

Penyimpanan file sekuen menggunakan format rekord tetap, dengan

sifat sebagai berikut :

- Rekord untuk nama atribut dihilangkan atau tidak digunakan

karena tiap rekord beratribut sama.

12

- Deskripsi atribut hanya satu untuk seluruh file

Ukuran record adalah :

R = a V

dimana :

a = jumlah field pada satu record

V = panjang rata-rata nilai atribut

B) Waktu Pengambilan Record Tertentu (T F)

Waktu pencarian record di file sekuen bergantung metode pencarian.

Ada 3 metode pencarian :

1. Pencarian secara sekuen (sequential search)

2. Pencarian biner (binary search)

3. Pencarian dengan penebakan (probing search)

B.1 Pencarian Secara Sekuen

Pencarian ini digunakan jika argumen pencarian adalah

menggunakan atribut bukan kunci

Terdapat dua kasus, yaitu :

1. Belum terbentuk file log

2. Telah terbentuk file log

Belum terbentuk file log

TF = ½ b (B/t’)

13

atau

TF = ½ n (R/t’)

Telah terbentuk file log (overflow) sebesar o

Waktu rata-rata pencarian record ke file log transaksi adalah

setengah o, yaitu = ½ o, maka :

TFo = O’ (R/t’)

= ½ O (R/t’)

TF = ½ (n+o) (R/t’)

B.2 Pencarian Biner

Pokok-pokok pencarian biner pada struktur file sekuen :

1. Argumen pencarian adalah atribut kunci

2. Pencarian dimulai mengakses tengah file, membaginya secara

berulang sesuai hasil perbandingan nilai kunci rekord dengan

nilai yang dicari

3. Saat satu blok diambil, record pertama dan terakhir diperiksa

untuk mengetahui keberadaan record di blok itu

4. Jumlah pengambilan bergantung pada jumlah blok

5. Jumlah pengaksesan blok yang diharapkan adalah 2log(b)

Terdapat dua kasus :

1. Belum terbentuk file log

2. Telah terbentuk file log

Belum terbentuk file log

14

TF = 2log(b) (s+r+btt+c)

= 2log(n/Bfr) (s+r+btt+c)

Telah terbentuk file log (overflow) sebesar o

Waktu rata-rata pencarian record ke file log transaksi adalah

setengah o, yaitu = ½ o, maka :

TFo = O’ (R/t’)

= ½ O (R/t’)

TF = 2log(b) (s+r+btt+c) + T fo

= 2log(n/Bfr) (s+r+btt+c) + ½ O (R/t’)

Dimana c adalah waktu pemrosesan record

Pencarian dengan penebakan

Dilakukan akses langsung (direct access) berdasar :

1. Perkiraan posisi record di file

2. Dilanjutkan pencarian sekuen

Nilai untuk penebakan awal didasarkan potensi harapan kemunculan.

Perhitungan waktu yang diperlukan sulit ditentukan.

C) Waktu Pengambilan Record Berikutnya (T N)

Mekanisme

Karena terdapat pengurutan rekord di file sekuen, maka peluang

rekord penerus di blok yang sama dengan rekord sebelumnya adalah

tinggi. Peluang menemukan rekord penerus di blok berikutnya

ditentukan jumlah rekord, yaitu (1/Bfr)

15

TN = waktu transfer 1 blok x nilai probabilitas

= btt x 1/Bfr

= btt/Bfr

D) Waktu Penyisipan Record (T I)

Mekanisme :

1. Rekord-rekord disisipkan sesuai urutan kunci

2. Terdapat dua cara penyisipan, yaitu :

- Untuk file berukuran kecil dapat dilakukan penggeseran

rekord-rekord agar sesuai urutan yang ditentukan

- Menyisipkan dulu ke log transaksi

Cara pertama : Cari, Geser, dan Sisip

1. Cari lokasi yang cocok menurut kunci

2. Menggeser rekord-rekord sesudah letak penyisipan

3. Sisipkan rekord yang baru

TI = TF + ½ (n/Bfr) (btt+ T RW)

= n (R/ t’)+n (r/Bfr)

Cara kedua : Memakai File log Transaksi

Mengumpulkan rekord-rekord baru ke file baru yaitu file log transaksi

TI = s + 3r +btt + (T Y/o)

E) Waktu Pembaruan Record (T U)

Terdapat dua kemungkinan pembaruan terhadap rekord, yaitu :

16

1. Pembaruan terhadap bukan kunci

2. Pembaruan terhadap kunci

Pembaruan terhadap bukan kunci

Mekanisme :

1. Cari rekord tersebut

2. Perubahan dilakukan dengan penimpaan nilai baru

TU = TF + TRw

Pembaruan terhadap kunci

Mekanisme :

1. Cari rekord tersebut

2. Hapus rekord yang diperbarui dari file utama

3. Sisipkan rekord yang telah diperbarui ke log transaksi

TU = TF (main) + T I (file log)

Kasus khusus : Pembaruan secara batch

Pembaruan dapat dilakukan secara batch, yaitu menumpuk dengan

pembaruan secara sekaligus. Pembaruan batch ini agar rekord-

rekord di satu blok dilakukan dengan sekali pencarian tidak lagi

diperlukan pencarian yang berulang kali.

TU = TN + TI

17

Ukuran log transaksi

o = d + 2v

F. Waktu Pembacaan Seluruh Record (T X)

Mekanisme

1. Pembacaan dilakukan terhadap file utama dan log transaksi

2. Data diproses secara serial

3. Log transaksi diurutkan lebih dulu, mempermudah pembacaan

sekuen

Terdapat 2 kasus :

1. File log belum terlalu besar

2. File log telah terlalu besar

File log belum terlalu besar :

1. Dilakukan pembacaan dari awal sampai akhir

2. Ikuti jalur ke file log bila rekord berikutnya di file log

Waktu pembacaan dari awal sampai akhir file

TX = Tsort (o) + (n+o)

t'

R

dimana

O = n insert + 2v +d

nnew = nold + n insert + d

File log telah terlalu besar

18

Bila file log telah terlalu besar, maka langkah terbaik adalah sekaligus

dilakukan reorganisasi, sehingga

TX = TY

G. Waktu Reorganisasi File (T Y)

Mekanisme

1. Proses penggabungan terhadap file utama dan log transaksi

2. Proses penggabungan akan lebih efektif, apabila file log

diurutkan berdasar kunci

TY = Tsort (o) + nold (R/t’) + o(R/t’) + n new(R/t’)

Bila jumlah record yang dihapus adalah d+v, maka

TY = Tsort (o) + 2(n+o) (R/t’)