Selasa, 03 November 2009

ORGANISASI BERKAS INDEKS SEQUENTIAL

ORGANISASI BERKAS INDEKS SEQUENTIAL

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

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

KEUNTUNGAN

Merupakan organisasi file yang sederhana. Jarak setiap aplikasi yang tersimpan sangat jelas. Metode penyimpanan didalam memory sangat sederhana, sehingga efisien untuk menyimpan record yang besar. Sangat murah untuk digunakan, sebab medianya cukup menggunakan magnetic tape.

KERUGIAN

Seandainya diperlukan perubahan data, maka seluruh record yang tersimpan didalam master file, harus semuanya diproses. Data yang tersimpan harus sudah urut (sorted). Posisi data yang tersimpan sangat susah untuk up-to-date, sebab master file hanya bisa berubah saat proses selesai dilakukan. Tidak bisa dilkukan pembacaan secara langsung.

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

Dikarenakan data yang tersimpan menggunakan teknik yang sedemikian rupa (yaitu random), maka data yang dibutuhkan bisa langsung ditemukan tanpa harus membaca data-data sebelumnya. Walaupun demikian, seandainya diperlukan untuk dibaca secara berurutan, juga dimungkinkan.

KEUNTUNGAN

Sangat sesuai untuk kebutuhan File Transaksi, sebab transaksi harus diproses saat kejadian berlangsung. Data yang tersimpan tidak harus urut (sorted). Untuk pemrosesan lebih efisien, sebab ada beberapa file yang memerlukan perubahan saat proses berlangsung. Lebih cepat dalam hal pemanggilan data. Beberapa data yang tersimpan didalam file, bisa diperbaiki dalam waktu bersamaan.

KERUGIAN

Memerlukan adanya back-ap data. Sebab transaksi yang diperbaiki setiap saat bisa menghilangkan jejak data asal. Data yang tersimpan mempunyai potensi lebih cepat rusak. Kapasitas media penyimpanan memory menjadi besar. Memerlukan hardware dan software yang lebih kompleks apabila dibanding sequential file.

C. 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 membayangkan penyimpanan dan pembacaan data secara sequential, kita bisa melihat 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

KEUNTUNGAN

Sangat cocok untuk digunakan menyimpan batch data ataupun individual data. Dibanding sequential file, pemanggilan data menjadi lebih cepat

KERUGIAN

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.

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 :

Handoko


Andi Reni

Anton Yana Mardi Riri

Tedi Susi Roni Dewi Dodi Irma Rudi Nurul

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.


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)


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

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.

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

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.

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

Maka seluruh pencarian langsung memerlukan pengaksesan empat blok indeks dan sebuah blok data.

KEY

KEY

BABOON

AARDVARK

·

BAT

ALLIGATOR

·

BEAR

KEY

AARDVARK

·

INDEX BLOCK 1.1

DATA BLOCK 2

BABOON

·

FOX

·

KEY

LLAMA

·

KEY

BOBCAT

INDEX BLOCK 2.1

BABOON

·

CALF

BOBCAT

·

CAT

COW

·

INDEX BLOCK 1.A

DATA BLOCK 2.A

TO data block 3

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.

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