sejarah komputer dan perkembangannya: 2013

ORGANISASI BERKAS

1) ORGANISASI BERKAS SEQUENSIAL

Orgaisasi berkas sequential adalah merupakan cara yang paling besar untuk mengoranisasikan kumpuan ricord-ricord dalam sebuah berkas.Dalam organisasi berkas sekuensial, pada waktu record ini dibuat, record-record direkam secara berurutan. Record pertama ditempatkan pada posisi pertama dalam berkas, record kedua ditempatkan pada posisi kedua dalam berkas dan seterusnya. Begitu pula pada waktu pengaksesan dan pada waktu berkas ini digunakan sebagai input, record-record harus diakses secara berurutan.

Ricord 1

Ricord 2

Ricord I – 1

Ricord I

Ricord I + 2

Ricord N - 1

Ricord N

Begnning File

End Of File

Gambar Strukrur Berkas Sequensial

1.1. PEMBUATAN BERKAS SEKUENSIAL

Pembuatan berkas sequensial meliputi penulisan record-record dalam

serangkaian yang diinginkan pada media penyimpanan.

Pembuatan berkas transaksi sekuensial meliputi tugas tugas:

ü Pengumpulan data.

ü Perubahan data dalam bentuk bahasa yang dapat dibaca oleh mesin.

ü Pengeditan data.

ü Pemeriksaan transaksi yang ditolak.

ü Penyortiran edit data.

1.2. PEMBUATAN BERKAS LAPORAN

Dalam Pembuatan berkas laporan sequensial dikenal 3 jenis record:

ü Header Record

Mencakup report header, page header, dan group header. Dikenal

sebagai informasi pengenal (identifying information).

ü Detail Record

Mencakup isi laporan yang umumnya disusun dalam kolom.

ü Footer Record

Mencakup report footer, page footer, dan group footer. Dikenal

sebagai informasi ringkasan (summary information).

1.3. RIETRIEVAL TERHADAP BERKAS SEKUENSIAL

Record pada berkas sequensial di retrieve secara berurutan. Urutan

dimana record tersebut ditulis pada berkas, menentukan urutan dimana record tersebut didapat kembali.

Retrieve dari sebuah berkas sekuensial dibagi 2, yaitu: report generation dan inquiry yang bergantung pada jumlah data yang dihasilkan.

Pada umumnya bekas sekuensial diakses dalam model report generation, karena record-record harus diakses secara berurutan, tentunya lebih efisien mengakses setiap record dari berkas tersebut.

Inquiry dari berkas sekuensial mengalami hambatan, karena organisasi berkas ini memerlukan pengaksesan record secara satu persatu. Namun ada inquiry yang memerlukan pengaksesan semua record dari berkas.

Contoh:

ü Beberapa jumlah mahasiswa yang berumur di atas 20 tahun?

ü Berapa jumlah pegawai yang mempunyai gaji di bawah Rp. 1.000.000.-

HIT RATIO

Banyaknya record yang harus diakses untuk mendapatkan informasi

yang diinginkan dibagi dengan banyaknya record dalam berkas tersebut.

Contoh:

Inquiry NPM: 10109207 memerlukan pengaksesan record sebanyak 10 dari 100 record yang ada dalam berkas mahasiswa.

Hit = 10 = 0.1

100

ü Semakin rendah hit ratio, semakin tidak baik bila menggunakan

organisasi sekuensial.

ü Semakin tinggi hit ratio, semakin baik bila menggunakan organisasi

sekuensial.

1.4. UPDATE TERHADAP BERKAS SEKUENSIAL

Master file berisi data yang relatif tetap, tetapi kadang kadang kita perlu mengadakan perubahan pada berkas tersebut.

Hal ini kita sebut sebagai proses update.

Frekuensi dimana sebuah master file harus di update bergantung pada faktor- faktor:

ü Tingkat perubahan data.

ü Ukuran dari master file.

ü Kebutuhan yang mendesak dari data yang sedang berjalan pada

master file.

ü File Activity Ratio

1.5. FILE ACTIVITY RATIO

Banyaknya record pada master file yang di update dibagi dengan banyaknya record pada master file.

Contoh:

Transaction file Master File

101 Bimo 75 101 Bimo jl.A 50

102 Amalia 70 103 Seno jl.C 30

103 Seno 60 104 Henni jl.Z 50

105 Pandu jl.D 70

File Activity Ratio = 1+1 = 0.5

ü Semakin tinggi file activity ratio, semakin lama proses peng-update-an master file.

ü Semakin tinggi kebutuhan akan data yang baru pada master file, maka semakin sering file tersebut diakses.

ü Semakin sering master file di-update, semakin tinggi biaya pemrosesannya.

Kebanyakan berkas sequential tidak dapat di-update langsung ditempat, karena untuk meng-update biasanya diperlukan berkas baru sebagai pengganti berkas lama

Pada gambar 7 menunjukkan system flow diagram untuk meng-update sebuah berkas sekuensial.

1.6. GENERATION FILE

Selama next cycle pada proses update, new master file yang sekarang

akan menjadi old master file. Menjadi banyaknya master file inilah yang disebut sebagai Generation File. File yang mempunyai nama yang sama, tetapi berbeda nomor generasinya. Jika old master sekarang merupakan generasi 1, maka new master berikutnya merupakan generasi 2, new master pada next cycle menjadi generasi 3, dst.

1.7. JENIS UPDATE

Ada 3 jenis update yang dapat dilakukan pada master file:

ü Insert a new record

ü Delete an existing record

ü Modify an existing record

Menangani Kesalahan

Dalam pelaksanaan update dapat ditemukan beberapa kesalahan,

seperti:

ü Insert record that already exists

ü Delete a record that does not exist

ü Modify a record that does not exist

Contoh:

Master File Trans –Type

101 101 1

102 103 2 1 : Delete

103 105 1 2 : Insert

104 107 3 3 : Modify

101 2

File Activity Ratio = 1

Contoh:

Sebuah master file berisi 10 record. Transaksi yang akan diproses

adalah sebagai berikut:

Rec-Id Trans – Type

111 2

111 1

96 3

400 1 1 : Insert

96 1 2 : Delete

111 2 3 : Modify

400 3

342 3

96 2

File Activity Ratio= 4

2) Organisasi Berkas Relatif

Organisasi Berkas Relatif adalah suatu cara yang efektif dalam mengorganisasi sekumpulan record yang membutuhkan akses sebuah record dengan cepat. Dalam berkas relatif ada hubungan antara key yang dipakai untuk mengidentifikasi record dengan lokasi record dalam penyimpanan sekunder. Urutan record secara logik tidak ada hubungannya dengan urutan secara fisik. Record tidak perlu tersortir secara fisik menurut nilai key.

FILE LOAD PROGRAM

Input Ricord

Direct File

1 2 3 4 5 6 7 8 9

Gambar 1.Organisasi Direct/Langsung

KeyValue Physical Position

I-1

I+1

I-1

COW	1
ZEBRA	2
- - -
APE	I-1
EEL	I
DOG	I+1
- - -
CAT	I-1
BAT	I

Beginning of File

End Of File

Gambar 2. Dasar Organisasi Berkas Relatif

Bagaimana record yang ke-N dapat ditemukan?. Dalam hal ini, perlu kita buat hubungan yang akan menterjemahkan antara NILAI KEY dan ADDRESS.

Hubungan ini dinyatakan sebagai R, yang merupakan fungsi pemetaan:

R(NILAI KEY) ADDRESS

dari nilai key ke address dalam penyimpanan sekunder.

2.1. PROSES

Pada waktu sebuah record ditulis kedalam berkas relatif, fungsi pemetaan R digunakan untuk menterjemahkan NILAI KEY dari record menjadi ADDRESS, dimana record tersebut disimpan.

Begitu pula pada waktu akan me-retrieve record dengan nilai key tertentu, fungsi pemetaan R digunakan terhadap nilai key tersebut, untuk menterjemahkan nilai key itu menjadi sebuah address dalam penyimpanan sekunder, dimana record tersebut ditemukan. 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.

Juga dimungkinkan untuk mengakses record-record dalam berkas relatif secara berurutan, tetapi perlu diketahui bahwa nilai key tidak terurut secara logik.

Contoh:

Record pada gambar 2, di-retrieve secara berurutan;

COW, ZEBRA, … , APE, EEL, DOG, … , CAT, BAT

Karena kemampuan mengakses record tertentu secara cepat, maka organisasi berkas relatif paling sering digunakan dalam proses interactive.

Contoh:

Sebuah on-line sistem perbankan yang mempunyai sebuah master file dan sebuah transaksi file. Field ACCOUNT NUMBER dipakai sebagai nilai key untuk kedua berkas tersebut. Pada saat nilai key ACCOUNT NUMBER dimasukan kedalam transaksi, nilai key tersebut akan meretrieve secara langsung record yang ada pada master file.

Jika Trans-Type = ‘I’, maka BALANCE ACCOUNT akan ditampilkan di layar.

Jika Trans-Type = ‘C’ atau ‘D’, maka record-record dari master file Customer Account akan dimodifikasi dengan AMOUNT dan DATE yang ada di transaction file, dimana ACCOUNT NUMBER yang menentukan lokasi record dalam berkas tersebut.

Catatan:

ü Kita tidak perlu mengakses semua record master file, cukup mengakses langsung record yang dikehendaki.

ü Record dari berkas relatif dapat di-update langsung tanpa perlu merekam kembali semua record.

ü Keuntungan dari berkas relatif ini adalah kemampuan mengakses record secara langsung. Sebuah record dapat di retrieve, insert, modifikasi atau di delete, tanpa mempengaruhi record lain dalam berkas yang sama.

Ada 3 teknik dasar yang digunakan untuk menyatakan fungsi pemetaan R, dimana R(NILAI KEY) ADDRESS

1. Direct Mapping (Pemetaan Langsung)

2. Directory Look Up (Pencarian Tabel)

3. Calculation (Kalkulasi)

2.2. TEKNIK PEMETAAN LANGSUNG

Teknik ini merupakan teknik yang sederhana untuk menterjemahkan nilai

record key menjadi address. Ada 2 cara dalam pemetaan langsung, yaitu:

1. Absolute Addressing (Pengalamatan Mutlak)

2. Relative Addressing (Pengalamatan Relatif)

2.2.1.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. Pada waktu record tersebut disimpan, lokasi penyimpanan record (nomor silinder, nomor permukaan, nomor record) bila dipakai Cylinder Addressing atau (nomor sektor, nomor record) bila dipakai Sector Addressing harus ditentukan oleh pamakai.

2.2.2.Keuntungan dari Pengalamatan Mutlak

ü Fungsi pemetaan R sangat sederhana.

ü Tidak membutuhkan waktu lama dalam menentukan lokasi record pada penyimpanan sekunder.

2.2.3.Kelemahannya

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

2.2.4.Pengalamatan Relatif

R(NILAI KEY) ADDRESS

NILAI KEY = ALAMAT RELATIF

Alamat relatif dari sebuah record dalam sebuah berkas adalah urutan record tersebut dalam berkas. Sebuah berkas dengan N record mempunyai record dengan alamat relatif dari himpunan (1,2,3, …, N -2, N -1). Record yang ke I mempunyai alamat relatif I atau I – 1 (bila mulai dihitung dari 0).

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

2.2.6.Kelemahannya

ü Alamat Relatif adalah bukan device dependent.

ü Alamat Relatif adalah address space dependent.

ü Terjadinya pemborosan ruangan.

2.3. TEKNIK PENCARIAN TABEL

Dasar pemikiran pendekatan pencarian tabel adalah sebuah tabel atau direktori dari nilai key dan address. Untuk menemukan sebuah record dalam berkas relatif, pertama dicari dalam direktori nilai key dari record tersebut, yang akan menunjukan alamat dimana record tersebut berada dalam penyimpanan.

Data dalam direktori tersebut disusun secara urut menurut nilai key, sehingga pencarian nilai key dalam direktori lebih cepat dengan binary search dibanding sequential search. Alternatif lain, direktori dapat disusun dalam Binary Search Tree, M-way Search Tree atau B-Tree.

Directory

Key Addres File Relative Alamat Relative

APE	I-1
BAT	N
CAT	N-1
-
COW	1
DOG	I-1
EEL	I
-
ZEBRA	2

I-1

I+1

N-1

COW

ZEBRA

APE

EEL

DOG

CAT

BAT

Directoty

APE , I-1

BAT. N

CAT , N-1

COW. 1

DOG , I+1

EEL. I

ZEBRA , 2

Gambar 5. Berkas Relative dengan Struktur Pohon

2.3.1.Keuntungan dari Pencarian Tabel

ü Sebuah 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.

2.4. TEKNIK KALKULASI ALAMAT

R (NILAI KEY) ADDRESS

Adalah dengan melakukan kalkulasi terhadap nilai key, hasilnya adalah alamat relatif. Ide dasar dari kalkulasi alamat adalah mengubah jangkauan nilai key yang mungkin, menjadi sejumlah kecil alamat relatif. Salah satu kelemahan dari teknik pengalamatan relatif adalah ruang harus disediakan sebanyak jangkauan nilai key, terlepas dari berapa banyak nilai key.

Salah satu masalah dari teknik ini adalah ditemukannya alamat relatif yang sama untuk nilai key yang berbeda.

Keadaan dimana:

R(K1) = R(K2) disebut benturan

K1 K2 atau collision

Sedangkan nilai key K1 dan K2 disebut synomin. Synonim adalah dua atau lebih nilai key yang berbeda pada hash ke home address yang sama.

2.4.1.Teknik-teknik yang terdapat pada Kalkulasi Alamat

ü Scatter storage techniques

ü Randomizing techniques

ü Key-to-address transformation methods

ü Direct addressing techniques

ü Hash table methods

ü Hashing

Disini yang akan kita bahas mengenai teknik hashing. Kalkulasi terhadap

nilai key untuk mendapatkan sebuah alamat disebut fungsi hash.

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

2.4.3.Kelemahannya

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

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

2.4.5.Beberapa fungsi Hash yang umum digunakan:

ü Division Remainder

ü Mid Square

ü Folding

2.5. DIVISION REMAINDER

Pada division remainder, alamat relatif dari suatu nilai key merupakan

sisa dari hasil pembagian nilai key tersebut dengan suatu bilangan yang

disebut sebagai bilangan pembagi.

Contoh:

Bila DIV adalah pembagi, KEY adalah nilai key dan ADDR adalah alamat relatif, maka dalam bahasa Pascal, fungsi R(NILAI KEY) ADDRESS dapat di implementasikan:

ADDR := KEY MOD DIV

Dalam bahasa COBOL:

DIVIDE KEY BY DIV GIVING TEMP REMAINDER ADDR

Sisa pembagian (sebagai hasil dari fungsi MOD pada Pascal), dapat

dijabarkan sebagai berikut:

ADDR := KEY - DIV * TEMP

ADDR Harus merupakan bilangan integer.

2.5.1.Banyak faktor yang harus dipertimbangkan dalam pemilihan

pembagi:

ü Jangkauan dari nilai key yang dihasilkan dari opersi KEY MOD DIV adalah 0 sampai DIV-1. Nilai dari DIV menentukan ukuran "relatif address space". Jika diketahui berkas relatif terdiri dari N record dan dianggap hanya satu record dapat disimpan dalam sebuah alamat relatif, maka akan didapat DIV > N.

ü Pembagi harus diseleksi untuk mengurangi benturan. Riset menunjukkan bahwa pembagi yang berupa bilangan genap akan cenderung jelek, terutama dengan nilai key-nya yang dominan ganjil.

ü Menurut riset dari W.Buchholz, sebaiknya pembagi itu merupakan bilangan prima. Tetapi riset lain dari V.Y.Lum, menyatakan pembagi yang bukan bilangan prima akan memberikan hasil yang sama baik, seperti bilangan prima.

ü Menurut pendapatnya, bukan bilangan prima yang mempunyai faktor prima kurang dari 20 akan dapat memberikan jaminan hasil yang lebih baik.

ü Walaupun kita telah menentukan pembagi dengan baik untuk mengatasi benturan, bila ruang alamat dari berkas relatif mendekati penuh, maka peluang terjadinya benturan akan meningkat. Untuk mengukur kepenuhan berkas 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. Jika load factor lebih besar dari 0.7 atau 0.8 maka berkas tersebut harus diperbesar dan di reorganisasi.

Jadi jika kita ingin menyimpan sebanyak n record pada suatu berkas dan load factor adalah 0.8, maka max. banyak record pada berkas adalah 1.25 n.

0.8 = max

max = 1.25 n

Contoh:

Kita ingin membuat berkas yang terdiri dari 4000 record. Load Factor (Faktor muat) = 0.8 maka max. banyak record pada berkas:

(1.25) n = (1.25) x 4000

= 5000

Bilangan pembagi: 5003

123456789 = 24676 sisa 2761 + 1

5003 (alamat relatif)

987654321 = 197412 sisa 2085 + 1

5003 (alamat relatif)

Jadi alamat relatif didapat dari sisa pembagian + 1

2.6. MID SQUARE HASHING

Untuk mendapatkan alamat relatif, nilai key dikuadratkan, kemudian

beberapa digit diambil dari tengah.

Dari nilai key yang dikuadratkan kita cari tengah-tengahnya.

Jumlah nilai key yang dikuadratkan:

nilai key 123456789 = 17 digit.

Untuk alamat relatif = 17 = 8.5

Kita mulai dari digit ke 8 dihitung dari kiri, maka alamat relatif = 8750 (karena ditentukan 4 digit sebagai alamat relatif).

2.7. HASHING BY FOLDING

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

Contoh:

Nilai key 123456789 dan alamat relatif sebanyak 4 digit. Nilai key dibagi

menjadi bagian-bagian yang terdiri dari 4 digit, mulai dari sebelah kanan.

2345

6789

2345

6789

Menghasilkan:

23 4 5

9 8 7 6 +

1 3 2 2 1

(alamat relatif)

2.7.1.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 kadangkadang 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.7.2.Pendekatan terhadap masalah Collision

Ada 2 pendekatan dasar untuk menetapkan dimana K2 harus disimpan,

yaitu:

Open Addressing

Separate Overflow

2.7.3.Open Addressing

Menemukan address yang bukan home address untuk K2 dalam berkas relatif.

Contoh:

K1 = 1 K2 = 1

R1 R2

2.7.4.Separate Overflow

Menemukan address untuk K2 diluar dari primary area dalam berkas relatif, yaitu di overflow area yang dipakai hanya untuk menyimpan

record-record yang tak dapat disimpan di home address nya.

Contoh:

K1 = 1 K2 = 1

Overflow area

Ada 2 teknik untuk mengatasi Collision:

ü Linier Probing, yang merupakan teknik open addresing.

ü Double Hashing, yang dapat dipakai selain open addressing atau separate overflow.

2.7.5.Linear Probing

Salah satu cara menemukan lokasi record yang tak dapat disimpan di home address nya adalah dengan menggunakan Linear Probing, yang merupakan sebuah proses pencarian secara sequential/linear dari home address sampai lokasi yang kosong.

2.7.6.Double Hashing

Pendekatan lain dalam menemukan lokasi sebuah record pada waktu record tersebut tidak dapat disimpan dalam home address nya adalah dengan menggunakan Double Hashing, yang akan memakai fungsi hash kedua terhadap hasil dari fungsi hash pertama. Address dari record yang di hash kembali dapat terletak pada primary area atau di separate overflow area.

Keuntungan dari metode separate overflow adalah menghindari keadaan dimana dapat terjadi metode open addressing untuk sebuah record yang tak disimpan dalam home address nya menggantikan record lain yang terakhir di hash ke home address nya.

Masalah ini dapat dihindari dengan open addressing sederhana dengan memindahkan record yang sebelumnya ke lokasi lain (dengan probing atau hashing kembali) dan menyimpan record yang baru ketempat yang kosong.

Metode ini membutuhkan pengeluaran tambahan untuk pemeliharaan berkas. Berkas relatif dibagi menjadi 2 berkas , yaitu: Primary Area dan Overflow Area.

2.7.7.Perbandingan Linear Probing dan Double Hashing

Berkas dengan load factor kurang dari 0.5 pada linear probing akan menghasilkan synonim yang mengelompok, sedangkan double hashing synonimnya berpencar.

Load Factor < 0.5 : Double Hashing = Linear Probing.

Load Factor > 0.8 : Double Hashing > Linear Probing.

2.7.8.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 address nya.

Contoh:

KEY HOME ADDRESS ACTUAL ADDRESS

Adams 20 20

Bates 21 21

Coll 20 22

Dean 21 23

Evans 24 24

Flint 20 25

R20 R21 R22 R23 R24 R25

Adams

Bates ..

Coll ..

Dean ..

Evans ..

Flint ..

…..

HOME PRIMARY DATA OVERFLOW

ADDRESS AREA AREA

Adams ..

Bates ..

Evans ..

Coll …

Dean ..

Flint

20 0

21 1

22 2

23 3

Gambar 12. Hashing dengan Synonim Chaining

2.7.9.Bucket Addressing

Pendekatan lain dalam mengatasi collision adalah hash ke dalam block atau bucket yang dapat memberikan tempat sejumlah record.

Contoh:

Sebuah berkas relatif mempunyai relatif address space dari 0 sampai M dan sebuah bucket berukuran B record, address space akan terdiri dari B(M+1) record. Jika file terdiri dari N record, maka:

Factor Muat = N

B(M + 1)

B record dapat semuanya di hash kedalam relatif address yang sama

tanpa menyebabkan collision.

Pada saat sebuah bucket penuh, beberapa tempat baru harus ditemukan untuk record tersebut. Pendekatan dari masalah bucket penuh pada dasarnya sama dengan pendekatan untuk mengatasi collision dengan record addressing.

Jika open addressing dipakai, space dicari untuk bucket berikutnya

(misal dengan linear probing) atau dalam bucket lainnya (misal dengan

double hashing).

Jika teknik separate overflow yang dipakai, record baru ditempatkan dalam suatu himpunan bucket yang dirancang khusus untuk tempat record yang tak dapat ditampung pada bucket primer. Bucket ini disebut bucket overflow.

Record-record yang disimpan dalam sebuah 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.

Satu keuntungan penting dari penggunaan bucket yang dapat menampung banyak record ini adalah record dengan panjang yang berbeda dapat dipakai.

Contoh:

KEY HOME ADDRESS

Green 30

Hall 30

Jenk 32

King 33

Land 33

Mark 33

Nutt 33

BUCKET BUCKET CONTENTS

ADDRESS

Green ..	Hall ..

Jenks ..
King ..	Land ..	Marks ..

OverFlow

Nutt

Gambar Bucket Adrressing

3) Organisasi Berkas Index Sequential

Organisasi Berkas Index Sequential adalah salah satu cara yang paling efektif untuk mengorganisasi kumpulan record-record yang membutuhkan akses record secara sekuensial maupun akses record secara individu berdasarkan nilai key adalah organisasi berkas indeks sekuensial.

Jadi berkas indeks sekuensial merupakan kombinasi dari berkas sekuensial dan berkas relatif.

Adapun jenis akses yang diperbolehkan, yaitu:

ü Akses Sequential

ü Akses Direct

Sedangkan jenis prosesnya adalah:

ü Batch

ü Interactive

Struktur berkas Index Sequential

ü Index Binary Search Tree

ü Data Sequential

Indeksnya digunakan untuk melayani sebuah permintaan untuk mengakses sebuah record tertentu, sedangkan berkas data sekuensial digunakan untuk mendukung akses sekuensial terhadap seluruh kumpulan record-record.

2.8. STRUKTUR POHON

Sebuah pohon (tree) adalah struktur dari sekumpulan elemen, dengan

salah satu elemennya merupakan akarnya atau root, dan sisanya yang lain merupakan bagian-bagian pohon yang terorganisasi dalam susunan berhirarki, dengan root sebagai puncaknya.

Contoh umum dimana struktur pohon sering ditemukan adalah pada penyusunan silsilah keluarga, hirarki suatu organisasi, daftar isi suatu buku dan lain sebagainya.

Contoh:

Handoko

Andi Reni

Anton Yana Mardi Riri

Tedi Susi Roni Dewi Dodi Irma Rudi Nurul

Gambar Silsilah Keluarga

Akar pohon (root) adalah Handoko.

Secara rekursif suatu struktur pohon dapat didefinisikan sebagai berikut:

ü Sebuah simpul tunggal adalah sebuah pohon.

ü Bila terdapat simpul n, dan beberapa sub-pohon T1,T2,...,Tk, yang tidak saling berhubungan, yang masing-masing akarnya adalah n1,n2,..., nk, dari simpul/sub pohon ini dapat dibuat sebuah pohon baru dengan n sebagai akar dari simpul-simpul n1,n2,...,nk.

….

…..

Gambar Definisi Struktur Pohon

2.9. POHON BINER

Salah satu tipe pohon yang paling banyak dipelajari adalah pohon biner.

Pohon Biner adalah pohon yang setiap simpulnya memiliki paling

banyak dua buah cabang/anak.

(1) (2) (3) (4) (5)

Gambar Beberapa Contoh Pohon Biner

Perhatikan gambar 4 beriku

MAMMOTH

N/2

COW

EEL

ZEBRA

BAT

CAT

APE

Posisi Sequential Data File

1	APE
2	BAT
3	CAT
4	COW
5	DOG
6	EEL
:	:
N	ZEBRA

Gambar Binary Search Tree dan Sequential File

Pada gambar 4 memperlihatkan struktur berkas indeks sekuensial dengan sebuah indeks berikut pointer yang menuju ke berkas data sekuensial.

Pada contoh gambar tersebut, indeksnya disusun berdasarkan binary search tree. Indeksnya digunakan untuk melayani sebuah permintaan untuk mengakses sebuah record tertentu, sedangkan berkas data sekeunsial digunakan untuk mendukung akses sekuensial terhadap seluruh kumpulan record-record.

2.10. IMPLEMENTASI ORGANISASI BERKAS INDEKS SEKUENSIAL

Ada 2 pendekatan dasar untuk mengimplementasikan konsep dari organisasi berkas indeks sekuensial:

ü Blok Indeks dan Data (Dinamik)

ü Prime dan Overflow Data Area (Statik)

Kedua pendekatan tersebut mengunakan sebuah bagian indeks dan sebuah bagian data, dimana masing-masing menempati berkas yang terpisah.

Alasannya:

Karena mereka diimplementasikan pada organisasi internal yang berbeda. Masing-masing berkas tersebut harus menempati pada alat penyimpan yang bersifat Direct Access Storage Device (DASD).

2.11. BLOK INDEKS DAN DATA

Jika sebuah permintaan untuk mengakses record tertentu, misal kita ingin mengakses dengan nilai key BAT, indeks dengan tingkat tertinggi (dalam hal ini blok indeks 3-1) yang pertama yang akan dicari pada contoh ini, pointer dari AARDVARK menunjuk blok indeks 2-1. Pointer yang ditunjuk pada kotak tersebut adalah pointer yang berisikan AARDVARK, yang akan menunjuk ke blok indeks 1-1. Pointer berikutnya yang akan ditunjuk adalah pointer yang berisi BABOON, yang selanjutnya akan menunjuk blok data 2. Blok data ini akan mencari untuk record dengan key tujuan, yaitu BAT, dimana pada blok ini record tersebut ditemukan.

Permintaan untuk akses data dalam urutan sekuensial dilayani dengan mengakses blok data dalam urutan sekuensial. Sebagai catatan blok data merupakan urutan secara logik dan bukan urutan secara fisik. Dalam hal ini, blok data harus dihubungkan secara bersama dalam urutan secara logik, seperti terlihat pada gambar 5.

Misal:

Setiap blok data mempunyai ruang yang cukup untuk menampung 5 record dan setiap blok indeks mempunyai ruang yang cukup untuk menyimpan 4 pasang (nilai key, pointer).

Parameter ini biasanya sudah dilengkapi dengan rutin dukungan sistem manajemen data, pada saat berkas binatang ini dibentuk.Jika kita menginginkan penyisipan maupun penghapusan terhadap isi berkas, maka blok indeks dan blok data akan dibuat dengan sejumlah ruang bebas, yang biasanya disebut sebagai padding dan pada gambar ditunjukkan sebagai irisan.

Permintaan:

INSERT APE

INSERT AIREDALE

Hanya blok data 1 yang digunakan dan hasilnya ditunjukkan pada gambar 6.

Entry pada blok harus diletakan berdasarkan urutan sekuensial ascending.

Permintaan:

INSERT ARMADILLO

Pencarian dari struktur indeks menyatakan bahwa ARMADILLO seharusnya menempati blok data 1, tetapi blok tersebut sudah penuh.

Untuk mengatasi keadaan tersebut, blok data 1 dipecah dengan memodifikasi blok indeks 1-1.

Separuh dari isi blok data, tetap menempati blok tersebut dan separuhnya lagi dipindahkan ke blok yang baru dibuat, yaitu blok data 1A. Hasilnya ditunjukkan pada gambar 7.

Permintaan:

INSERT CAT

INSERT BEAR

INSERT BOBCAT

Akan mengisi blok data 2, tetapi blok data tersebut harus dipecah menjadi blok data 2 dan 2A.

Blok indeks 1-1 sudah penuh dan tidak dapat memuat pointer pada blok data 2A, sehingga inipun harus dipecah, dengan cara mengubah penafsiran indeks tingkat 2.

Jika blok indeks pada tingkat paling tinggi (dalam hal ini indeks tingkat

3) sudah penuh, maka harus dipecah, sehingga sebuah indeks tingkat yang baru akan ditambahkan pada indeks tree.

Maka seluruh pencarian langsung, memerlukan pengaksesan empat blok indeks dan sebuah blok data. Hasilnya ditunjukkan pada gambar 8

2.12. PRIME DAN OVERFLOW DATA AREA

Pendekatan lain untuk mengimplementasikan berkas indek sekuensial

adalah berdasarkan struktur indek dimana struktur indek ini lebih ditekankan pada karakteristik fisik dari penyimpanan, dibandingkan dengan distribusi secara logik dari nilai key.

Entry pada indeks ini adalah dalam bentuk:

nilai key terendah, nomor track

Dalam sebuah track data, tracknya disimpan secara urut berdasarkan

nilai key.

Tingkat pertama dari indeks dalam berkas indeks dinamakan master

index.

Entry pada indeks ini adalah dalam bentuk:

nilai key tertinggi, pointer

Tingkat kedua dari indeks dinamakan cylinder index.

Indeks ini berisi pointer pada berkas prime data dan entry-nya dalam

bentuk:

nilai key tertinggi, nomor cylinder

Jika sebuah permintaan untuk mengakses record tertentu, misal kita

akan mengakses dengan nilai key BAT, pertama akan dicari pada master index. Karena BAT ada di depan LYNX, maka pointer dari LYNX akan menunjuk ke cylinder index. Karena BAT ada di depan ELEPHANT, maka pointer dari ELEPHANT akan menunjuk ke track 0 dari cylinder 1. Karena BAT ada di belakang BABOON dan di depan COW, maka pointer dari BABOON akan menunjuk ke track 2, yang mencari secara sekuensial, sampai BAT ditemukan.

Permintaan untuk mengakses data secara sekuensial akan dilayani

dengan mengakses cylinder dan track dari berkas data prime secara urut.

Misal setiap track dari berkas prime data mempunyai ruang yang cukup untuk menampung 5 record (jika penyisipan dan penghapusan terhadap berkas dilakukan, maka akan dibentuk padding).

Permintaan:

INSERT APE

INSERT AIREDALE

Akan mudah dilayani. Hanya track data 1 dari cylinder 1 yang akan digunakan dan hasilnya ditunjukkan pada gambar 10.

Permintaan:

INSERT ARMADILLO

Agak sulit ditangani. Pencarian struktur indeks menyatakan bahwa ARMADILLO seharusnya menempati track 1 dari cylinder 1, tetapi track tersebut sudah penuh.

Untuk mengatasi keadaan tersebut diperlukan overflow data area. Overflow data area ini merupakan berkas yang terpisah dari prime data area, tetapi overflow area ini ditunjukan oleh entry prime data area.

Hasilnya ditunjukkan pada gambar 11.

Karena ARMADILLO seharusnya berada setelah kelima entry pada track

1 dari cylinder 1, tetapi karena track ini sudah penuh, maka ARMADILLO dipindahkan ke overflow data area. Indeks track dari cylinder 1 harus dimodifikasi untuk memperlihatkan bahwa ada sebuah record pada overflow area yang secara logik seharusnya menempati pada akhir dari track 1, sehingga penambahan dari entry itu adalah:

<ARMADILLO,ovfl-ptr>

Dengan ovfl-ptr adalah:

<cylinder, track, record>

Permintaan:

INSERT CAT

INSERT BEAR

INSERT BOBCAT

Akan mengisi track 2 dari cylinder 1 pada prime data area, tetapi pengisian tersebut mengakibatkan penggunaan overflow area.

Perhatikan CAT dipindahkan ke overflow area, karena entry pada prime track tidak hanya harus dalam urutan, tetapi juga entry tersebut harus mendahului suatu entry overflow dari track tersebut.

Hasilnya ditunjukkan pada gambar 12.

Permintaan:

INSERT ANT

Deklarasi Berkas Indeks Sekuensial Dalam Bahasa COBOL

I. MULTI KEY

Multi – Key adalah : Organisasi yang dapat mempunyai sebuah file yang di akses dengan banyak cara Tehnik dasar multi key

Ada 2 teknik dasar untuk pemberian hubungan antara sebuah indeks dan data record dari berkas, yaitu : Inversion,Multi-list Banyak sistem informasi interaktif memerlukan dukungan dari berkas banyak key.
Contoh :
Sebuah sistem perbankan yang mempunyai beberapa pemakai (user), seperti kasir, pegawai kredit, manajer cabang, pegawai bank, nasabah dan lain-lain. Semuanya memerlukan akses data yang sama dengan format record

Adanya pemakai yang berbeda memerlukan akses record-record ini dalam cara yang berbeda.
Kasir                          : Mengidentifikasikan record account menurut nilai ID.
Kredit                         :Akses semua record menurut nilai OVERDRAW LIMIT atau semua record account dengan nilai SOCNO.
Manajer Cabang     : Akses semua record menurut Branch dan Type.
Pegawai Bank         : Membuat laporan berkala untuk semua record ccount yang disortir berdasarkan ID.
Nasabah                   :Memerlukan akses recordnya dengan memberikan ID yang dimilikinya atau kombinasi dari NAME, SOCNO dan Type.
Satu pendekatan yang dapat mendukung semua jenis akses adalah dipunyainya banyak berkas yang berbeda. Setiap berkas diorganisasi untuk melayani satu jenis keperluan.

Maka untuk contoh sistem perbankan di atas harus ada :

ID : untuk melayani kasir, pegawai bank dan nasabah.

OVERDRAW LIMIT : untuk melayani pegawai kredit.
SOCNO : untuk melayani pegawai kredit.

GROUP-CODE : untuk melayani manajer cabang.

NAME, SOCNO dan TYPE : untuk melayani nasabah.

Jadi kita mempunyai 5 file, semuanya mempunyai record yang sama. Kelima file itu hanya
berbeda dalam organisasi dan cara aksesnya.

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.

sejarah komputer dan perkembangannya

widget

Minggu, 15 Desember 2013

sistem berkas swquensial

memasang widget

cara mudah pasang sms pada blog