ORGANISASI FILE

Macam-macam Organisasi File

Organisasi File Dasar

Dua struktu file paling dasar, yaitu:

1. Pile (Tumpukan)

2. File sekuen berurut (sequential File atau Ordered File)

Untuk file Pile dan file Sekuensial, keduanya merupakan organisasi file yang struktur penyimpanannya tidak dilengkapi dengan kemampuan pengaksesan data secara cepat.

Struktur file dengan dilengkapi indeks, yaitu:

1. File sekuen berindeks (indexed sequential file)

2. File berindeks maajemuk (multiply indexed file)

Indeks digunakan untuk memudahkan pencapaian data, sehingga waktu pencarian datanya lebih cepat bila dibandingkan dengan kedua oranisasi file sebelumnya yaitu organisasi file Pile dan file Sekuensial.

Struktur file spesifik keperluan system komputer, yaitu:

1. File hash (hashed file atau direct file)

2. File multiring (multiring file)

Kedua organisasi file diatas merupakan jenis organisasi file yang memiliki tipe pengaksesan data dengan menggunakan metode komputasi spesifik untuk mencapai data.

Dengan mengetahui kinerja struktur file secara kuantitatif maka pemilihan struktur file yang tepat dapat dilakukan. Bila struktur file dasar tidak dapat memenuhi kebutuhan maka kita dapat menggabungkan struktur-struktur tersebut untuk memenuhi kebutuhan operasi-operasi dari aplikasi.

STRUKTUR FILE SEKUENSIAL

KARAKTERISTIK

File sekuensial disebut juga ordered file. Karena karakteristik terpenting dari jenis file ini adalah keberurutan record-record dalam file menurut suatu kriteria. Berbeda dengan file pile yang memiliki format yang bervariasi, file sekuensial memiliki format record yang sama. Maksudnya setiap record pada file sekuensial memiliki jumlah atribut, nama atribut, urutan atribut, tipe dan panjang field atribut yang sama.

Record-record pada file sekuensial diurutkan berdasarkan key tertentu. Key adalah identifikasi unik dari record yang digunakan untuk membedakan satu record dengan record lainnya. Dengan adanya key, maka bisa dilakukan proses pengurutan yang mengakibatkan waktu akses yang semakin cepat. Key berupa satu atribut atau lebih. Deskripsi dari nama atribut dapat disimpan dalam header file. File header berisi informasi mengenai file yaitu jumlah record yang ada, ukuran record, struktur field di record, kunci record yang digunakan, dan sebagainya.

Karakteristik file sekuensial adalah:

Atribut-atribut data dikategorikan. Record berisi semua nilai data atribut dengan urutan dan posisi yang sama.
Record-record data terurut dalam satu aturan/criteria tertentu. Criteria ini dapat melibatkan satu field atau lebih, umumnya adalah kunci record.

Komponen File Sekuensial

Komponen file sekuensial terdiri dari:

Master File (file utama atau file data)
File transaction log berstruktur pile

Pada file sekuensial, data yang tersimpan dalam file utama, merupakan data yang sudah terurut, Berikut ini merupakan contoh dari file utama:

No Block	No Rec	Nrp	Nama	Jurusan	Ortu	Kota
001	1	0322001	Heni	Elektro	Sujadi	Bogor
	2	0322002	Bayu	Elektro	Giman	Kudus
	3	0322003	Cahya	Elektro	Sapan	Banjar
002	1	0322004	Karim	Elektro	Kardi	Madiun
	2	0322005	Harno	Elektro	Saso	Jakarta
	3	0322006	Yudha	Elektro	Naryo	Tasik
003	1	0323001	Weni	Industri	Hendra	Madiun
	2	0323002	Ferry	Industri	Dudung	Medan
	3	0323003	Pupun	Industri	Pupon	Nganjuk
004	1	0325001	Ismani	IF
	2	0325002	Yerry	IF
	3	0325003	Siono	IF

Sedangkan file transaksi pada file sekuensial merupakan data yang belum terurut. Berikut ini merupakan contoh dari file transaksi :

No Block	No Rec	Nrp	Nama	Jurusan	Ortu	Kota
001	1	0322007	Nyoman	Elektro	Ketut	Malang
	2	0325004	Sayed	IF	Rahmat	Bogor
	3	0323004	Dian	Industri	Hadi	Banjar
002	1	0325005	Amri	IF	Warno	Cianjur
	2	0310001	Utami	Kedokteran		Cirebon
	3	0322008	Siska	Elektro	Sukono	Tasik

Perbandingan dengan file pile:

Dengan konstrain sekuens dan record tetap, maka terjadi

v Peningkatan efisiensi

v Penurunan fleksibilitas

Pembaruan terhadap file sekuen tidak mudah dilakukan

Struktur dan Pengaksesan

Struktur:

Satu skripsi tunggal diterapkan ke semua record di file sekuen. Semua record identik.
Jika terdapat penambahan atribut baru ke record, seluruh file harus di reorganisasi, yaitu: setiap record ditulis ulang dengan ruang kosong (space) untuk item data baru.
Bentuk record tetap (fixed record) mempermudah pengaksesan.

Implementasi

Sebutan file sekuen adalah bila file memenuhi dua criteria file sekuen, yaitu record-record data diurut dalam satu sekuen/aturan tertentu. Terdapat dua implementasi utama file sekuen, yaitu :

Record-record di link satu dengan lainnya seperti linked-list secara terurut.
Record-record di simpan terurut secara fisik. Implementasi ini meminimalkan pengaksesan blok sehingga meningkatkan kinerja pengaksesan sekuen. Pada analisis, implementasi ini yang digunakan.

Penyisipan

Penyisipan dilakukan di file pile, disebut file log transaksi (transaction log file) atau file overflow. Penyisipan di file log dilakukan sampai ukuran file pile berukuran besar.
Pembaruan secara batch dilakukan saat reorganisasi file.

Mekanisme Reorganisasi

File log transaksi diurut (sort) berdasar atribut kunci.
Dilakukan penggabungan (file utama dan file log transaksi yang terurut) menjadi file sekuen baru.

Penyisipan dan penghapusan record merupakan hal yang bermasalah karena urutan record-record di file harus selalu di jaga. Untuk menyisipkan maka harus ditemukan lokasi record baru, dan kemudian membebaskan lokasi yang akan ditempati yang mungkin melibatkan pergeseran banyak record lain, setelah dilakukan penulisan pada blok data maka blok data itu kembali dituliskan ke penyimpanan sekunder. Cara ini sungguh tidak efisien.

Untuk mengatasi banyaknya pergeseran ini maka lebih baik menggunakan overflow file atau transaction file. Penyisipan dilakukan dengan penulisan ke overflow file di akhir file. Secara periodic, overflow file digabungkan dengan file utama untuk membentuk satu file sekuen yang terurut seluruhnya. Hal ini membuat penyisipan menjadi efisien, tapi menimbulkan penurunan kinerja pada pencarian record karena begitu tidak ditemukan di file utama yang dicari secara pencarian biner maka harus dilakukan pencarian linear pada overlow file.

Penggunaan File Sekuen

Penggunaan:

v Commercial batch-oriented processing, dimana pembaruan terhadap seluruh record diolah secara periodic.

v Konsep file master dan file transaksi digunakan untuk organisasi ini

v Penggabungan data dari sejumlah file sekuen diperlukan file terurut sehingga seluruh data ditemukan dalam sekali pencarian ke arah depan.

Contoh:

v Monthly billing untuk perusahaan listrik, air bersih, telepon, dan sebagainya.

v Payroll application.

Analisis Kinerja File Sekuen

A. Ukuran Record (R)

Penyimpanan file sekuen menggunakan format record tetap, dengan sifat berikut:

v Ruang untuk nama atribut dihilangkan atau tidak digunakan karena tiap record beratribut sama.

v Deskripsi atribut hanya satu untuk seluruh file, sehingga kebutuhan “ruang” untuk nama atribut hanya dapat diabaikan.

B. Waktu Pengambilan Record Tertentu (T_F)

Waktu pencarian record di file sekuen bergantung metode pencarian. Terdapat 3 metode pencarian yang dapat diterapkan pada file sekuen, yaitu:

1. Pencarian secara sekuen atau linear search

2. Pencarian biner (binary search)

3. Pencarian dengan penebakan (probing search)

Pencarian secara sekuen atau linear search

Pencarian ini digunakan jika argument pencarian adalah menggunakan atribut bukan kunci. Pencarian data dilakukan secara berurutan dari awal sampai akhir tanpa menggunakan key.

Perhitungan:

Terdapat dua kasus, yaitu :

Belum terbentuk file log
Telah terbentuk file log

Belum terbentuk file log

T_F= ½ waktu pencarian seluruh blok

= ½ b (B/t’)

Atau (karena ukuran file adalah bB atau nR)

T_F= ½ n (R/t’)

Telah terbentuk file log (Overflow) sebesar o

Waktu rata-rata pencarian record ke file log transaksi adalah setengah o, yaitu o’ = ½ o, maka :

T_FO= 0’ (R/t’)

= ½ 0 (R/t’)

T_Ffile sekuen dengan file log transaksi sebesar o adalah:

T_F= ½ (n+0) (R/t’)

Digunakan bulk transfer rate (t’) karena pembacaan file sekuen dari awal, melewati gap dan batas silinder sampai menemukan blok berisi record di inginkan.

Pencarian biner (binary search)

Pokok-pokok pencarian biner

Argument pencarian adalah atribut kunci
Pencarian dimulai mengakses file tengah, membaginya secara berulang sesuai hasil perbandingan nilai kunci record dengan nilai yang dicari.
Saat satu blok diambil, record pertama dan terakhir diperiksa untuk mengetahui keberadaan record di blok itu.
Jumlah pengambilan (fetch) tidak bergantung jumlah record (n), tapi bergantung jumlah blok (b=n/Bfr)
Jumlah pengaksesan blok yang diharapkan adalah ²log (b)

Terdapat dua kasus, yaitu :

Belum terbentuk file log
Telah terbentuk file log

Tengah = [ (awal + akhir)/2 ]

- Jika kunci cari < kunci tengah, maka bagian berkas mulai dari kunci tengah sampai akhir berkas dieliminasi.

- Jika kunci cari > kunci tengah, maka bagian berkas mulai dari depan sampai dengan kunci tengah dieliminasi.

- Jika Awal >Akhir maka rekaman tidak ditemukan

- Pembulatan angka untuk hasil nilai tengah adalah pembulatan ke bawah

C. Waktu Pengambilan Record Berikutnya (T_N)

Karena terdapat pengurutan record di file sekuen, maka peluang record penerus (successor record) di blok yang sama dengan record sebelumnya adalah tinggi. Peluang menemukan record penerus di blok berikutnya ditentukan jumlah record, yaitu (1/Bfr)

Perhitungan:

T_N= waktu transfer 1 blok x nilai probabilitas

= btt x 1/Bfr

= btt/Bfr

D. Waktu Penyisipan Record (T_l)

Mekanisme :

1. Record-record disisipkan sesuai urutan kunci

2. Terdapat dua cara penyisipan yaitu:

· Untuk file berukuran kecil dapat dilakukan pergeseran record-record agar sesuai urutan yang ditentukan

· Menyisipkan dulu ke log transaksi

Cara pertama: cari, Geser dan Sisip

Langkah-langkah penyisipan record yaitu:

Cari lokasi yang cocok menurut kunci
Menggeser record-record sesudah letak penyisipan
Sisipkan record yang baru

STRUKTUR FILE SEKUENSIAL BERINDEKS

PENGERTIAN BERKAS INDEKS SEKUENSIAL

Selain organisasi berkas sequential dan relative yang telah dibahas sebelumnya, berikut akan dibahas mengenai organisasi berkas index sequential. Contoh sederhana dari organisasi ini adalah susunan data yang ada di sebuah buku kamus. Kita bisa mengakses buku kamus tersebut secara sequential (berurutan), maupun melalui index (daftar isi)nya. Jadi, file organization index sequential adalah file yang disusun sedemikian rupa sehingga dapat diakses secara sequential maupun secara direct (langsung), atau kombinasi keduanya, direct dan sequential.

Ada dua pendekatan dasar dalam menyusun organisasi berkas semacam ini, yaitu (1) blok index dan data, dan (2) prime dan overflow data area. Untuk cara pertama, kita menyusun data dengan lebih memperhatikan ke data yang bersifat logik, bukan fisik. Jadi, data dan index diorganisasikan ke dalam blok-blok. Blok-blok index (daftar isi dalam buku kamus) diorganisasi secara sequential (consecutive) dan bertingkat-tingkat (misal setiap blok hanya berisi 4 record index yang berisi key field dan pointer). Setiap tingkat akan menuju ke blok data (misal setiap blok hanya berisi 5 record data) di tingkat selanjutnya dan seterusnya menuju ke blok data yang akan mendapatkan record yang dicari secara direct (lihat skema di buku referensi hal. 60).

Bila dilakukan penyisipan data dan blok tertentu (tempat data baru itu) sudah penuh (tidak ada tempat kosong/ padding lagi), maka akan dilakukan reorganisasi blok dengan membentuk blok baru.Tentu, mungkin saja perubahan ini akan berdampak pada isi blok index-nya.

Pendekatan kedua adalah dengan lebih memperhatikan aspek karakteristik dari hardware (fisik) alat penyimpanan datanya. Biasanya disimpan di hard disk yang memiliki cylinder dan track. Caranya hampir sama dengan cara di pendekatan pertama, hanya di sini lebih ditekankan pada aspek fisik. Jadi, yang bertingkat-tingkat adalah cylender-nya dan blok datanya ditulis secara consecutive di setiap track (misalkan 1 cylinder berisi 4 track, nomor 0 sampai 3). Index (pencarian data) tertinggi disebut dengan master index, dari master index berturut-turut menuju ke blok-blok index tingkat berikutnya hingga meraih record data yang berada di track-nya.

Bila dilakukan penyisipan data dan track tertentu (tempat data baru itu) sudah penuh (tidak ada tempat kosong/ padding lagi), maka akan dilakukan reorganisasi track dengan membentuk track baru.Tentu, track baru itu di luar prime data file-nya, yaitu di overflow data area-nya.

Sebelum kita mengarah pada definisi dari Organisasi Berkas Indeks Sequential, lebih baik terlebih dahulu kita pahami dulu satu persatu dari pengertian Organisasi Berkas Indeks Sequential tersebut.

Organisasi File debut juga sebagai suatu teknik atau cara yang digunakan untuk menyatakan dan menyimpan record–record dalam sebuah file.
Campuran organisasi berkas langsung dengan organisasi berkas sekuensial
Cocok untuk aplikasi yang memakai kedua jenis cara pengaksesan (langsung dan sekuensial)
Sangat berguna kalau kita pada suatu saat perlu mengakses satu record saja, dan pada saat yang lain perlu mengakses banyak rekord sekaligus
Sedangan pengertian dari Index Sequential File merupakan perpaduan terbaik dari teknik Sequential dan random file. Pada teknik penyimpanan yang dilakukan, menggunakan suatu index yang isinya berupa bagian dari data yang sudah tersortir. Index ini diakhiri denga adanya suatu pointer (penunjuk) yang bisa menunjukkan secara jelas posisi data yang selengkapnya. Index yang ada juga merupakan record-key (kunci record), sehingga kalau recordkey ini dipanggil, maka seluruh data juga akan ikut terpanggil.

Jadi, organisasi berkas indeks sequential adalah Berkas/file yang disusun sedemikian rupa sehingga dapat diakses secara sequential maupun secara direct (langsung) atau kombinasi keduanya, direct dan sequential.

Contoh sederhana dari organisasi ini adalah susunan data yang ada di sebuah buku kamus. Kita bisa mengakses buku kamus tersebut secara sequential (berurutan), maupun melalui index (daftar isi) nya.

Struktur Dasar

Dalam komputer, grup-grup infomasi beserta hirarkinya adalah sbb:

File yang diorganisasikan dengan struktur sekuensial berindeks disebut ISAM (Indexed Sequential Access Method)

Ada dua pendekatan dasar dalam menyusun organisasi berkas semacam ini, yaitu :
Blog Index dan Data

Prime dan Over flow Area

Untuk cara pertama, kita menyusun data dengan lebih memperhatikan ke data yang bersifat logik, bukan fisik. Jadi, data dan index diorganisasikan ke dalam blok-blok. Blok-blok index diorganisasi secara sequential (consecutive) dan bertingkat-tingkat (misal setiap blok hanya berisi 4 record index yang berisi key field dan pointer).
Setiap tingkat akan menuju ke blok data (misal setiap blok hanya berisi 4 record data) di tingkat selanjutnya dan seterusnya menuju ke blok data yg akan mendapatkan record yg dicari secara direct.

Prime dan Overflow Data Area

Pendekatan lain untuk mengimplementasikan berkas indeks sequential adalah berdasarkan struktur indeks dimana struktur indeks ini lebih ditekankan pada karakteristik hardware (fisik) dari penyimpanan, dibandingkan dengan distribusi secara logik dari nilai key.

Pengaksesan Secara Sequential

Pengaksesan atau pengolahan atau pemrosesan data yang dilakukan secara sequential adalah dengan melakukan akses yang dimulai dari baris teratas dari sebuah tabel dan selanjutnya berurut ke baris-baris berikutnya (di bawahnya). Jadi, jika kita akan mencari suatu record dan kebetulan record tersebut ada di nomor 10, maka, mau tidak mau record nomor 1 hingga nomor 9 harus kita lalui terlebih dulu.

Pengaksesan Secara Random

Pengaksesan atau pengolahan atau pemrosesan data yang dilakukan secara random adalah dengan melakukan akses yang dimulai dari baris berapa saja dari sebuah tabel dan selanjutnya terserah ke baris-baris mana saja untuk akses berikutnya.

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.

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.

Implementasi Organisasi Berkas Indeks Sequential

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

Blok Indeks dan Data (Dinamik)
Prime dan Overflow Data Area (Statik)

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

Blok Indeks Dan Data

Pada pendekatan ini kita menyusun data dengan lebih memperhatikan ke data yang bersifat logik, bukan fisik, jadi berkas indeks dan berkas data diorganisasikan dalam blok.

Berkas indeks mempunyai struktur tree
Berkas data mempunyai struktur sequential dengan ruang bebas yang didistribusikan antar populasi record.

Prime dan Overflow Data Area

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. Misalnya, setiap cylinder dari alat penyimpanan mempunyai 4 track. Pada berkas binatang ada 6 cylinder yang dialokasikan pada prime data area. Track pertama (nomor 0) dari setiap cylinder berisi sebuah indeks pada record key dalam cylinder tersebut.

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

Entry pada indeks ini adalah dalam bentuk :

nilai key tertinggi, pointer

Tingkat kedua dari indeks dinamakan cylinder indeks.

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

nilai key tertinggi, nomor cylinder

Permintaan untuk mengakses data secara sequential 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).

Faktor–faktor yang mempengaruhi dalam proses pemilihan organisasi file

yaitu Karakteristik dari penyimpanan yang digunakan, Volume dan frekuensi dari transaksi yang diproses, Respontime yang diperlukan. Cara memilih organisasi file tidak terlepas dari 2 aspek utama, yaitu Model penggunaannya dan Model operasi file.

Struktur Pohon pada System

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.

Blok Indeks Dan Data

Pada pendekatan ini kita menyusun data dengan lebih memperhatikan ke data yang bersifat logik, bukan fisik, jadi berkas indeks dan berkas data diorganisasikan dalam blok.
Berkas indeks mempunyai struktur tree

Berkas data mempunyai struktur sequential dengan ruang bebas yang didistribusikan antar populasi record. Pada gambar tersebut ada N blok data dan 3 tingkat dari indeks. Setiap entry pada indeks mempunyai bentuk (nilai key terendah, pointer), dimana pointer menunjuk pada blok yang lain, dengan nilai key-nya sebagai nilai key terendah. Setiap tingkat dari blok indeks menunjuk seluruh blok, kecuali blok indeks pada tingkat terendah yang menunjuk ke blok data.

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

Contoh sederhana dari organisasi ini adalah susunan data yang ada di sebuah buku kamus. Kita bisa mengakses buku kamus tersebut secara sequential (berurutan), maupun melalui index (daftar isi)nya. Jadi, file organization index sequential adalah file yang disusun sedemikian rupa sehingga dapat diakses secara sequential maupun secara direct (langsung), atau kombinasi keduanya, direct dan sequential.

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 sequential digunakan untuk mendukung akses sequential terhadap seluruh kumpulan record-record.

¨ 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 1. 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 2. Definisi struktur pohon

¨ 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 3. Beberapa contoh Pohon Biner

Pada gambar tersebut 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.

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

Tambahan:

Untuk cara pertama, kita menyusun data dengan lebih memperhatikan ke data yang bersifat logik, bukan fisik. Jadi, data dan index diorganisasikan ke dalam blok-blok. Blok-blok index (daftar isi dalam buku kamus) diorganisasi secara sequential (consecutive) dan bertingkat-tingkat (misal setiap blok hanya berisi 4 record index yang berisi key field dan pointer). Setiap tingkat akan menuju ke blok data (misal setiap blok hanya berisi 5 record data) di tingkat selanjutnya dan seterusnya menuju ke blok data yang akan mendapatkan record yang dicari secara direct (lihat skema di buku referensi hal. 60).

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

¨ BLOK INDEKS DAN DATA

Pada pendekatan ini berkas indeks dan berkas data diorganisasikan dalam blok. Berkas indeks mempunyai struktur tree, sedangkan berkas data mempunyai struktur sekuensial dengan ruang bebas yang didistribusikan antar populasi record.

Teknik Pengalamatan

Untuk menyimpan data ke dalam memori komputer, tentu memori tersebut diberi identitas (yang disebut dengan alamat/ address) agar ketika data tersebut diperlukan kembali, komputer bisa mendapatkannya sesuai dengan data yang pernah diletakkan di sana.

Untuk media penyimpanan yang bersifat sequential access storage device (SASD) seperti kaset (magnetic tape), alamat tersebut tidak terlalu dipusingkan karena pasti data disimpan secara berurutan (sequential/consecutive) mulai dari depan hingga ke akhir bagian dari pita kaset. Begitu juga dengan data yang diorganisasi secara sequential, di alamat manapun data disimpan, data akan tetap diakses secara berurutan pula, mulai dari record pertama hingga ke record terakhir.

Lain halnya dengan data yang diorganisasi secara relative yang disimpan di media penyimpanan yang bersifat direct access storage device (DASD), karena data yang akan diraih kembali, dituju langsung ke alamatnya tanpa melalui records lainnya (belum tentu dimulai dari data yang paling awal disimpan), maka alamat memori memegang peranan penting. Untuk itu, di catatan ini akan diterangkan beberapa cara melakukan penempatan data di memori agar kelak dapat diraih kembali dengan tepat, yang diberi judul “Teknik Pengalamatan.”

Teknik pengalamatan ini hampir sudah tidak diperlukan lagi oleh pemakai komputer saat ini karena hampir seluruh software yang beredar di pasaran tidak mengharuskan si pemakai menentukan di alamat mana datanya akan disimpan (semua sudah otomatis dilakukan oleh si software). Jadi, yang kita pelajari adalah bagaimana kira-kira si software tersebut melakukan teknik pengalamatannya, sehingga data yang sudah kita berikan dapat disimpan di alamat memori tertentu dan dapat diambil kembali dengan tepat.

Ada 3 teknik dasar untuk pengalamatan, yakni 1. Pemetaan langsung (direct mapping) yang terdiri dari dua cara yakni Pengalamatan Mutlak (absolute addressing) dan Pengalamatan relatif (relative addressing), 2. Pencarian Tabel (directory look-up), dan 3. Kalkulasi (calculating).

TEKNIK PEMETAAN LANGSUNG

1. PENGALAMATAN MUTLAK

Pandang, kita memiliki data teman-teman sekelas kita yang akan kita masukkan ke dalam memori (misal hard disk), data tersebut berjumlah 50 orang yang masing-masing terdiri atas atribut-atribut : NIM, NAMA, dan ALAMAT_RUMAH.

Jika data tersebut kita masukkan dengan organisasi file sequential, maka jika kita mencari data NIM = ‘10105787’ yang namanya ‘ALI’ dan beralamat di ‘Jl. Margonda No. 100, Depok’, maka pencarian akan dilakukan mulai dari record pertama (data pertama yang dimasukkan), dan seterusnya menuju ke record terakhir sampai ketemu data yang dicari tersebut.

Lain halnya jika data tersebut dimasukkan dengan organisasi file relative, maka data tersebut akan didapat secara langsung dari record yang dituju. Tentu, untuk langsung mendapatkan record yang dituju ada ‘sesuatu’ yang disebut dengan kunci atribut (key field). Kunci atribut itulah yang dikelola sedemikian rupa sehingga ‘kita’ bisa tahu dimana record tersebut disimpan.

Untuk teknik pengalamatan ‘alamat mutlak’ ini, kita tidak terlalu mempermasalahkan kunci atribut karena kita diminta langsung menuliskan di mana alamat record yang akan kita masukkan. Jika kita menggunakan hard disk atau magnetic drum, ada dua cara dalam menentukan alamat memorinya, yaitu (1) cylinder addressing dan (2) sector addressing. Jika kita menggunakan cylinder addressing, maka kita harus menetapkan nomor-nomor dari silinder (cylinder), permukaan (surface), dan record, sedangkan bila kita menggunakan sector addressing, maka kita harus menetapkan nomor-nomor dari sektor (sector), lintasan (track), dan permukaan (surface). Teknik ini mudah dalam pemetaan (pemberian) alamat memorinya. Sulitnya pada pengambilan (retrieve) data kembali, jika data yang kita masukkan banyak, kita bisa lupa di mana alamat record tertentu, misalkan apakah kita ingat nomor record dari data NIM = ‘10105787’ yang namanya ‘ALI’ dan beralamat di ‘Jl. Margonda No. 100, Depok’ ?, apakah kita harus menghafal selamanya alamat-alamat tersebut ?. Pelajari keuntungan dan kerugian lainnya.

Teknik ini dapat dijuluki dengan device dependent (tergantung pada peralatan rekamnya), artinya, kita tidak dapat begitu saja meng-copy data berkas ini ke komputer lainnya, karena mungkin saja di komputer lainnya itu menggunakan alat rekam yang berbeda spesifikasinya.

Teknik ini juga dapat dijuluki dengan address space dependent (tergantung pada alamat-alamat yang masih kosong), artinya, kita tidak dapat begitu saja meng-copy data berkas ini ke komputer lainnya, karena mungkin saja di komputer lainnya itu alamat-alamat yang dibutuhkan sudah tidak tersedia lagi.

2. PENGALAMATAN RELATIF

Teknik ini menjadikan atribut kunci sebagai alamat memorinya, jadi, data dari NIM dijadikan bertipe numeric(integer) dan dijadikan alamat dari record yang bersangkutan. Cara ini memang sangat efektif untuk menemukan kembali record yang sudah disimpan, tetapi sangat boros penggunaan memorinya. Tentu alamat memori mulai dari 1 hingga alamat ke sekian juta tidak digunakan karena nilai dari NIM tidak ada yang kecil. Pelajari keuntungan dan kerugian lainnya.Teknik ini termasuk dalam katagori address space dependent.

TEKNIK PENCARIAN TABEL

Teknik ini dilakukan dengan cara, mengambil seluruh kunci atribut dan alamat memori yang ada dan dimasukkan ke dalam tabel tersendiri. Jadi tabel itu (misal disebut dengan tabel INDEX) hanya berisi kunci atribut (misalkan NIM) yang telah disorting (diurut) dan alamat memorinya.

Jadi, sewaktu dilakukan pencarian data, tabel yang pertama dibaca adalah tabel INDEX itu, setelah ditemukan atribut kuncinya, maka data alamat yang ada di sana digunakan untuk meraih alamat record dari data (berkas/ file/ tabel) yang sebenarnya. Pencarian yang dilakukan di tabel INDEX akan lebih cepat dilakukan dengan teknik pencarian melalui binary search (dibagi dua-dua, ada di mata kuliah Struktur dan Organisasi Data 2 kelak) ketimbang dilakukan secara sequential.

Nilai key field (kunci atribut) bersifat address space independent (tidak terpengaruh terhadap perubahan organisasi file-nya), yang berubah hanyalah alamat yang ada di INDEX-nya.

TEKNIK KALKULASI ALAMAT

Kalau pada teknik pencarian tabel kita harus menyediakan ruang memori untuk menyimpan tabel INDEX-nya, maka pada teknik ini tidak diperlukan hal itu. Yang dilakukan di sini adalah membuat hitungan sedemikian rupa sehingga dengan memasukkan kunci atribut record-nya, alamatnya sudah dapat diketahui. Tinggal masalahnya, bagaimana membuat hitungan dari kunci atribut itu sehingga hasilnya bisa efisien (dalam penggunaan memori) dan tidak berbenturan nilainya (menggunakan alamat yang sama).

Misal, untuk data si ALI di atas yang memiliki NIM = ‘10105787’, di mana akan kita letakkan ?. Bila yang kita lakukan adalah perhitungan : INT(VAL(NIM)/1000000) maka haslinya adalah 10, dengan demikian data si ALI akan disimpan di alamat 10. Tapi, apakah alamat 10 itu tidak akan digunakan oleh data lain dengan perhitungan yang sama ?, ternyata tidak. Untuk data si BADU yang NPMnya ’10105656’ juga di alamat tersebut, dan ternyata masih banyak juga yang ’rebutan’ untuk menempati alamat tersebut jika dilakukan dengan perhitungan seperti di atas.

Perhitungan (kalkulasi) terhadap nilai kunci atribut untuk mendapatkan nilai suatu alamat disebut dengan fungsi hash. Bisa juga fungsi hash digabungkan dengan teknik pencarian seperti tabel di atas, tetapi akan menjadi lebih lama pengerjaannya dibanding hanya dengan satu jenis saja (fungsi hash saja atau pencarian tabel saja).

Fungsi hash dikatakan baik bila memiliki kalkulasi yang sederhana dan memiliki kelas ekivalen (synonim) yang kecil, atau sederhananya, memiliki kalkulasi yang mudah tetapi memiliki benturan alamat yang sedikit.

Ada beberapa cara untuk mengatasi benturan (collision) penggunaan alamat seperti di atas, antara lain : scatter diagram techniques, randomizing techniques, key to address transformation methods, direct addressing techniques, hash tables methods, dan hashing. Di sini, kita hanya membahas mengenai hashing. Beberapa fungsi hash yang umum digunakan adalah : division remainder, mid square, dan folding.

DIVISION REMAINDER

Idenya adalah, membagi nilai key field dengan nilai tertentu, dan sisa pembagian tersebut dijadikan alamat relatifnya. Nilai tertentu itu terserah kita, ada yang membagi dengan bilangan prima, namun ada juga yang tidak.Yang jelas, tujuannya adalah agar alamat yang akan digunakan bisa berbeda sekecil mungkin (menghemat memori) dan menghindari benturan yang bakal terjadi.

Ada perhitungan faktor muat (load factor) yaitu, jika kita memiliki sejumlah record yang akan ditempatkan ke dalam memori, maka setidaknya kita harus menyediakan memori yang kapasitasnya melebihi dari jumlah record tersebut. Misalkan, kita memiliki 4000 record, maka sebaiknya kita memiliki memory space sebanyak 5000 alamat. Faktor muat dihitung dengan cara membagi jumlah record dalam file dengan jumlah maksimum record dalam file (alamat yang tersedia). Semakin besar nilai faktor muat maka semakin baik teknik ini digunakan. Faktor muat untuk contoh di atas adalah 4000/5000 = 0,8.

MID SQUARE

Teknik ini dilakukan dengan cara melakukan kuadratisasi nilai key field dan diambil nilai tengahnya sebanyak jumlah digit yang diinginkan. Misalkan, nilai key-nya = 123456790, setelah dikuadratkan hasilnya = 15241578997104100 dan diambil 4 digit di tengahnya, yaitu 8997. Jadi, alamat memori untuk data tersebut di 8997.

HASING BY FOLDING

Teknik ini dilakukan dengan cara ’melipat’ nilai dari kunci atribut sebanyak digit yang dibutuhkan (dari kanan), kemudian dijumlahkan. Nilai terbesar dari jumlah tersebut dibuang (jika melebihi digit yang dibutuhkan). Misalkan untuk nilai key 123456790, maka empat angka di belakang setelah dilipat menjadi 0976, angka tersebut ditambahkan dengan empat angka kedua (dari kanan) yaitu 2345 dan angka 1 paling kiri :

0976
2345
1
——– +

4321

Maka, alamat dari data tersebut adalah di 4321.

Berbagai teknik dalam penentuan penempatan data di memori (sekunder) komputer terus berkembang. Tentu saja karena data yang direkam biasanya selalu bersifat dinamis (bisa bertambah, berkurang, di-copy, di-sorting) dan sebagainya. Kedinamisan tersebut tentu saja bisa berpengaruh terhadap alamat-alamat yang sudah ditetapkan sebelumnya yang bersifat fixed size space atau memiliki ukuran alamat yang tetap (satu misalnya, jika kita meng-copy data tersebut yang semula di hard disk ke dalam disket, apakah alamat-alamat yang tersedia di disket sama dengan di hard disk ?, tentu tidak).

Teknik hash baru yang dikembangkan antara lain dynamic hashing, extendible hashing, dan virtual hashing. Tujuannya adalah agar alamat-alamat yang sudah ada tidak berubah meskipun data baru ditambahkan dengan cara membagi-bagi memori menjadi bagian-bagian tertentu yang disebut dengan blok atau bucket, bila sebuah record akan dimasukkan ke dalam bucket yang sudah penuh, maka bucket baru disediakan kembali.
Dynamic hashing memakai struktur indeks binary tree untuk menyimpan track dari bucket dan pointer untuk menuju ke record yang diinginkan. Extendible hashing menggunakan direction untuk menyimpan track dari bucket dan pointer untuk menuju ke record yang diinginkan. Sedangkan virtual hashing lebih luas lagi, termasuk di dalamnya dynamic hashing dan extendible hashing dan berbagai teknik indeks lainnya (yang tidak dibahas di sini).

PENDEKATAN MASALAH BENTURAN (COLLISION)

Hampir semua teknik akan mengalami benturan dalam penggunaan alamat memorinya. Ada beberapa teknik untuk menyelesaikannya, yaitu linear probing dan separate overflow.

LINEAR PROBING

Metode ini dilakukan dengan cara : apabila hasil perhitungan key baru ternyata sama dengan hasil perhitungan key sebelumnya, maka dengan menambahkan hasil perhitungan tersebut dengan satu (per satu) (secara linear) sampai ke alamat memori yang masih kosong, ia akan menempati alamat tersebut.

Misal, hasil perhitungan adalah 300 sedangkan di alamat 300 sudah ada yang menempati, maka data baru akan menempati alamat 301, bila alamat tersebut juga sudah ada yang menempati, maka ia akan menempati alamat 302, dan seterusnya bertambah satu-satu hingga ke alamat yang masih kosong (belum ditempati). Hal semacam ini disebut dengan open addressing.

Begitu juga ketika data tersebut dipanggil kembali, maka jika tidak ketemu di home address-nya (hasil perhitungan awalnya), maka akan ditambahkan dengan satu per satu hingga di alamat tertentu yang recordnya memiliki nilai key sama dengan nilai key yang dicari.

DOUBLE HASHING

Dari namanya dapat diketahui bahwa double hashing adalah menjalankan fungsi hash yang kedua terhadap hasil fungsi hash yang pertama jika masih terjadi collision. Penempatan data dapat dilakukan di primary area atau home address-nya (hasil perhitungan sebenarnya, nilai interval yang mungkin dapat dijangkau dengan perhitungannya), atau di separate overflow area (area yang disediakan untuk menampung data yang berbenturan/ di luar area yang masuk dalam interval nilai perhitungannya).

Double hashing lebih baik dari linear probing pada faktor muat tinggi (lebih dari 0,8), dan sama baik pada faktor muat 0,5. Double hashing memiliki synonim (hasil perhitungan yang sama/ terjadi collision) berpencar sedangkan linear probing mengelompok pada faktor muat kurang dari 0,5.

SYNONIM CHAINING

Synonim chaining adalah suatu rangkaian pointer yang menghubungkan (link) antara satu alamat dengan alamat lain yang berada di separate overflow area.Hal ini dilakukan untuk mempercepat akses di area tersebut. Jadi, jika hasil perhitungan ternyata datanya bukan yang data dicari, maka akan di-link data yang berada di separate overflow area mulai dari awal alamatnya hingga ketemu data yang dicarinya.

BUCKET ADDRESSING

Cara lain untuk menghindari benturan adalah pembuatan blok-blok memori. Misalkan, setiap 10 record akan kita tempatkan di dalam satu blok (bucket). Jika blok tersebut sudah penuh, maka dibuka kembali blok-blok lain. Perhitungan penempatan record ke dalam blok dapat dilakukan dengan teknik yang mirip dengan teknik-teknik sebelumnya. Begitu juga dengan pengambilan data kembali (retrieve) dilakukan dengan teknik-teknik yang sama dengan sebelumnya.

Istilah prime memory (memori yang ditempati oleh record yang sesuai dengan hasil perhitungannya) dan separate overflow (memori yang menampung record yang hasil perhitungannya berbenturan sehingga tidak bisa ditempatkan di memori sebenarnya) dipakai juga di sini. Istilahnya menjadi : primary bucket dan overflow bucket.

FILE ORGANIZATION : INDEX SEQUENTIAL

Selain organisasi berkas sequential dan relative yang telah dibahas sebelumnya, berikut akan dibahas mengenai organisasi berkas index sequential. Contoh sederhana dari organisasi ini adalah susunan data yang ada di sebuah buku kamus. Kita bisa mengakses buku kamus tersebut secara sequential (berurutan), maupun melalui index (daftar isi) nya. Jadi, file organization index sequential adalah file yang disusun sedemikian rupa sehingga dapat diakses secara sequential maupun secara direct (langsung), atau kombinasi keduanya, direct dan sequential.

File-File

· Menyediakan kemampuan untuk mengolah data secara fleksibel

· Pengaturan data dalam file cenderung tidak terstruktur

· Merupakan struktur organisasi yang menggunakan tempat penyimpanan data yang bervariasi baik ukuran maupun strukturny

File Sekuensial

· Terdiri dari kumpulan record fixed dan terurut berdasarkan ketentuan tertentu

· Penyimpanan data tidak fleksibel

· Update dalam file cukup sulit

· Struktur file sederhana

File Sekuensial Berindeks

· Struktur organisasi yang mengombinasikan indeks dengan sekuensial file

· Keunggulan : pencarian data dan update file berdasarkan 1 atribut tertentu jauh lebih baik daripada sekuensial file

File Berindeks Majemuk

· File indeks dengan banyak key

· Memungkinkan pencarian data dengan menggunakan lebih dari 1 atribut

· Cukup fleksibel

· Proses update kompleks

· Pengambilan record lebih mudah

Hash File

· Memungkinkan pencapaian record secara cepat berdasarkan rumus tertentu

· Format record tetap

Multiring File

· Terdidri dari kumpulan record yang memiliki interkoneksi antar record

· Mempercepat pencarian

· Boros tempat karena membutuhkan pointer.

Faisal Ahda Damanik

Minggu, 05 Februari 2012

ORGANISASI FILE

Implementasi Organisasi Berkas Indeks Sequential

Blok Indeks Dan Data

Prime dan Overflow Data Area

Adapun jenis akses yang diperbolehkan, yaitu:

· Akses Sequential

· Akses Direct

Sedangkan jenis prosesnya adalah:

Gambar 1. Silsilah Keluarga