it's better to be a pirate than to join the navy. (Steven Paul Jobs)


BAB 5

ORGANISASI BERKAS INDEKS SEQUENTIAL


Pengertian Berkas Indeks Sequential

Salah satu cara yang paling efektif untuk mengorganisasi kumpulan record-record yang membutuhkan akses record secara sequential maupun akses record secara individu berdasarkan nilai key adalah organisasi berkas indeks sequential.

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

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

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

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

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.

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

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.

Permintaan :

INSERT CAT

INSERT BEAR

INSERT BOBCAT

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

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

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 :

cylinder 1track 0 : no change

track 1 : AARDVARK,,,,,,,AIREDALE,,,,,,,,,ALBATROSS,,,,,,,,,ALLIGATOR,,,,,,,APE,,,,,,,,,,

track 2 : no change

track 3 : no change

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 :

SELECT filename ASSIGN TO implementor-name[,implementor-name2]

AREA

RESERVE integer

AREA

ORGANIZATION IS INDEXED

SEQUENTIAL

ACCESS MODE IS       RANDOM

DYNAMIC

RECORD KEY IS dataname-1

[  FILE STATUS IS dat

n

n1

n2

nk

BAB 5 Revisi Argun

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: