File/berkas adalah sekumpulan informasi yang
saling berkaitan dan didefenisikan oleh pembuatnya. Umumnya berkas adalah
sekumpulan bit, byte, record di mana artinya didefenisikan oleh pembuat dan
pemakainya. File data dapat berbentuk numeric, alfabeth ataupun alfanumeric.
File dapat berbentuk bebas seperti file teks atau terstruktur. Suatu file
mempunyai nama dan diacu berdasarkan nama tersebut. Juga mempunyai komponen
lain seperti tipe, waktu pembuatan, nama dan nomor account dari pembuatnya,
besar ukuran file. Kita dapat menulis informasi, mengubah informasi, menambah
dan menghapus informasi dalam file.
Sistem
berkas adalah
suatu sistem untuk mengetahui bagaimana cara menyimpan data dari file tertentu
dan organisasi file yang digunakan. Sistem berkas
menyediakan pendukung yang memungkinkan programmer mengakses file tanpa
menyangkut perincian karakteristik penyimpanan dan peralatan pewaktu. Sistem
berkas mengubah pernyataan akses file menjadi instruksi/output level rendah.
Atau dengan kata lain Sistem berkas adalah cara untuk mengambil informasi dari
suatu file.
Pengertian
Organisasi berkas adalah Suatu teknik/cara yang digunakan untuk
menyatakan/menggambarkan dan menyimpan record-record dalam sebuah berkas.
Ada 4 teknik dasar organisasi berkas, yaitu: (1).
Sequential File (2). Relative File (3). Index Sequential File (4). Multi-Key
File
Salah satu
kegiatan dalam materi system berkas adalah bagaimana mengorganisir sebuah
record yang ada dalam berkas. 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 . Organisasi berkas ini mempunyai semua keunggulan dari sequential
file. Tetapi kemampuan aksesnya jauh lebih baik
1.1.Rumusan
Masalah
Adapun rumusan
masalah dalam makalah iniyaitu sebagai berikut:
1. Pengertian
organisasi berkas indexed sequential?
2. Contoh
dari indexed sequential?
3. Implementasi
organisasi berkas indexs sequential?
4. Keuntungan
dan kerugian penggunaan magnetic disk?
1.2.Maksud dan
Tujuan
Secara umum
tujuan penyusunan makalah ini bertujuan untuk :
1. Sebagai
salah satu syarat untuk memenuhi tugas mata kuliah Sistem Berkas
2. Agar
dapat memahami menegenai tentang Organisasi Berkas Indexed
Sequential
BAB II
PEMBAHASAN
2.1. Pengertian Organisasi
Berkas Indexed Sequential
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.
Penyimpanan ataupun penulisan character demi character yang ada didalam
external memory, harus diatur sedemikian rupa sehingga komputer bisa dengan
mudah menemukan kembali data-data yang tersimpan didalamnya. Aturan inilah yang
kemudian dikenal sebagai organisasi file. Dalam hal ini, dikenal ada beberapa
metoda, yaitu: Sequential File, Random File dan Index Sequential File.
2.1.1. Sequential
File
Sequential file merupakan suatu cara ataupun suatu metode
penyimpanan dan pembacaan data yang dilakukan secara berurutan. Dalam hal ini,
data yang ada akan disimpan sesuai dengan urutan masuknya. Data pertama dengan
nomor berapapun, akan disimpan ditempat pertama, demikian pula dengan data
berikutnya yang juga akan disimpan ditempat berikutnya. Dalam melakukan
pembacaan data, juga akan dilakukan secara berurutan, artinya, pembacaan akan
dimulai dari data paling awal dan dilanjutkan dengan data berikutnya sehingga
data yang dimaksud bisa diketemukan.
2.1.2. Random
File
Random file merupakan suatu cara ataupun suatu metode
penyimpanan dan pembacaan data yang dilakukan secara random atau langsung.
Dengan demikian, random file juga disebut sebagai Direct Access File (Bisa
dibaca secara langsung). Dalam hal ini, tempat penyimpanan data sudah diatur
sedemikian rupa, sehingga setiap data akan tersimpan didalam tempat-tempat yang
telah ditentukan sesuai dengan nomor data yang dimiliki-nya.
2.1.3. Index
Sequential File
Index Sequential File merupakan perpaduan terbaik dari
teknik sequential dan random file. 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 record key ini dipanggil,
maka seluruh data juga akan ikut terpanggil. Untuk penyimpanan dan pembacaan
data secara sequential, dapat dilihat rekaman lagu yang tersimpan pada kaset.
Untuk mendengarkan lagu kelima, kita harus melalui lagu kesatu, dua, tiga dan
empat terlebih dahulu. Pembacaan seperti inilah yang disebut sebagai sequential
atau berurutan. Apabila lagu-lagu yang ada kemudian disimpan didalam
compack-disk, maka untuk mendengar kan lagu yang ke-lima bisa langsung
dilakukan (dibaca secara random). Disamping itu, dengan compack-disk juga bisa
dilakukan pembacaan secara berurutan atau sequential. Compack-disk menyimpan
lagu secara random. Untuk penyimpanan data dengan menggunakan teknik index
sequential ini, kita bisa mengibaratkan dengan 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. Pulung yang memiliki abjad terkecil, akan menempati posisi pertama dan
Rino pada posisi terakhir. Gambar yang ada menunjukkan bagaimana record data
nilai disimpan didalam media disk ataupun disket dengan menggunakan teknik
index sequential. Index data akan dibaca pertama kali oleh computer dan
dikarenakan didalam index data juga terdapat address maka data yang dicari bisa
segera diketemukan. Sesuai dengan sifat media yang dimilikinya, maka pada
sebuah pita magnetic tape, hanya bisa menyimpan data secara sequential. Dengan
demikian, cara pembacaan yang dilakukan juga hanya secara sequential, yaitu
berurutan satu persatu sampai nomor record yang dikehendaki diketemukan. Dengan
menggunakan Direct Access Methode (metode pembacaan/penulisan secara langsung),
maka, record yang tersimpan didalam sebuah disket, Hard-disk, CD ROM ataupun
Laser-Disk dapat di-access secara langsung dengan tanpa harus membaca seluruh
data yang dimilikinya. Access dengan menggunakan methoda Index-sequential juga
dapat dilakukan oleh media ini. Dengan melakukan access pertama kali pada
key-field yang ada, maka akan diketemukan record yang dituju. 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.
2.2.Contoh dari
indexed sequential
2.2.1. 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 :
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.
2.2.2. 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
Adapun jenis akses yang diperbolehkan, yaitu :
Ø Akses Sekuensial
Ø Akses Direct
Sedangkan jenis prosesnya adalah :
Ø Batch
Ø Interactive
Struktur Berkas Indeks sekuensial
Ø Indeks ® Binary Search Tree
Data ® Sekuensial
Pada gambar
tersebut memperlihatkan struktur berkas indeks sequential dengan sebuah indeks
berikut pointer yang menuju ke berkas data sequential. Pada contoh gambar
tersebut, indeksnya disusun berdasarkan binary search tree. 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.
2.3.Implementasi
organisasi berkas indexed 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.
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.3.1. Blok
Indeks Dan Data (Dinamik)
Pada pendekatan
ini berkas indeks dan berkas data diorganisasikan dalam blok. Berkas indeks
mempunyai struktur tree, sedangkan 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.
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 sequential
dilayani dengan mengakses blok data dalam urutan sequential. Sebagai catatan
blok data merupakan consecutive secara logik dan bukan consecutive secara
fisik. Dalam hal ini, blok data harus dihubungkan secara bersama dalam urutan
secara logik, seperti terlihat pada gambar.
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 di bawah ini :
Entry pada blok harus diletakkan berdasarkan urutan
sequential 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 di bawah ini :
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 pada 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.
2.3.2. Prime
dan Overflow Data Area
Pendekatan lain
untuk mengimplementasikan berkas indeks sequential adalah 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.
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 :
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
Jika sebuah
permintaan untuk mengakses record tertentu, misal kita akan mengakses dengan
nilai key BAT, pertama akan dicari pada master indeks. 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 sequential sampai BAT
ditemukan.
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).
Permintaan :
INSERT
APE
INSERT
AIREDALE
Akan mudah
dilayani. Hanya track data 1 dari cylinder 1 yang akan digunakan dan hasilnya
ditunjukkan pada gambar di bawah ini :
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 ditunjukkan oleh entry prime data area.
Hasilnya ditunjukkan pada gambar di bawah ini :
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 di bawah ini :
Permintaan :
INSERT
ANT
Hasilnya ditunjukkan pada gambar di bawah ini :
Deklarasi Berkas Indeks Sequential dalam bahasa COBOL :
2.4.Keuntungan
Dan Kerugian Penggunaan Magnetic Disk
- · 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.
