. Yaitu berkas yang telah di susun sesuai dengan keinginan user yang dapat di akses secara sequential, direct (langsung) dan kombinasi keduanya (direct dan 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.
Contoh umum dimana struktur pohon sering ditemukan adalah pada penyusunan silsilah keluarga, hirarki suatu organisasi, daftar isi suatu buku dan lain sebagainya.
Contoh :
https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhS5H_bhYAlF0bhHPD6j4XpCiYKkJ2rMPBZfNGVtiL7HM_E8yxnIgwhekQRwJT0Dy4kFKWGyZa8KYNQ2iHGlQvM9ajB3VkyuD1GoKzKyPGoB_f4YJmu1np94Pc92WNhWE3GqP6qQ1rrQkrr/s320/untitledss.bmp
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
Lihat gambar berikut ini :
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.
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 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.
Lihat gambar
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.
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 :
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
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 :
Dengan ovfl-ptr adalah :
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
Materi yang di tambahkan untuk melengkapi materi pada bab 5 yang bersumber dari
www.google.com
Organisasi Berkas ialah suatu teknik atau cara untuk menyatakan dan menyimpan record-record dalam sebuah berkas / file
Ada 4 teknik dasar organisasi file, yaitu :
Sequential
Relative
Indexed Sequential
Multi – Key
Secara umum keempat teknik dasar tersebut berbeda dalam cara pengaksesannya, yaitu :
Direct Access
Adalah suatu cara pengaksesan record yang langsung, tanpa mengakses seluruh record yang ada.
Contoh : Magnetic Disk
Sequential Acces
Adalah suatu cara pengaksesan record, yang didahului pengaksesan record-record di depannya.
Contoh : Magnetic Tape
Faktor-faktor yang mempengaruhi dalam proses pemilihan organisasi file :
Karakteristik dari media 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
Model Operasi File
Menurut penggunaannya ada 2 cara :
Batch;
Suatu proses yang dilakukan secara group atau kelompok.
Interactive;
Suatu proses yang dilakukan secara satu persatu, yaitu record demi record
Menurut operasi file ada 4 cara :
Creation;
Membuat struktur file lebih dahulu, menentukan banyak record baru, kemudian record-record dimuat ke dalam file tersebut.
Membuat file dengan cara merekam record demi record.
Update;
Untuk menjaga agar file tetap up to date.
Insert / Add, Modification, Deletion.
Retrieval;
Pengaksesan sebuah file dengan tujuan untuk mendapatkan informasi.
Inquiry, Volume data rendah, model proses interactive.
Report Generation, Volume data tinggi, model proses batch
Maintenance;
Perubahan yang dibuat terhadap file dengan tujuan memperbaiki penampilan program dalam mengakses file tersebut.
Restructuring, Perubahan struktur file.
Misalnya : Panjang field diubah, penambahan field baru, panjang record dirubah.
Reorganization, Perubahan organisasi file dari organisasi yang satu, menjadi organisasi file yang lain.
Misalnya : Dari organisasi file sequential menjadi indeks sequential, Dari direct menjadi sequential
ORGANISASI BERKAS
SEQUENTIAL
Sequential merupakan cara yang paling dasar untuk mengorganisasikan kumpulan record-record dalam sebuah berkas.
Keuntungan
Kemampuan untuk mengakses record berikutnya secara tepat.
Keterbatasan
Tidak dapat mengakses langsung pada record yang diinginkan
Pembuatan Berkas Sequential
Meliputi penulisan record-record dalam serangkaian yang diinginkan pada media penyimpanan.
Tugas-tugasnya :
Pengumpulan data
Perubahan data dalam bentuk bahasa yang dapat dibaca oleh mesin
Pengeditan data
Pemeriksaan transaksi yang ditolak
Penyortiran edit data
Retrieval Terhadap Berkas Sequential
Record pada berkas sequential di retrieve secara berurutan.
Retrieve dari sebuah berkas dapat dibagi 2 tergantung pada jumlah data yang dihasilkan, yaitu :
Report Generation
Inquiry,
Update Terhadap Berkas Sequential
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
Hit Ratio
Banyaknya record yang harus diakses untuk mendapatkan informasi yang diinginkan dibagi dengan banyaknya record dalam berkas tersebut .
Semakin rendah hit ratio, semakin tidak baik bila menggunakan organisasi sequential.
Semakin tinggi hit ratio, semakin baik bila menggunakan organisasi sequential.
File Activity Ratio
Banyaknya record pada master file yang di-update dibagi dengan banyaknya record pada master file.
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
ORGANISASI BERKAS RELATIVE
Pengertian Berkas Relatif
Suatu cara yang efektif dalam mengorganisasi sekumpulan record yang membutuhkan akses sebuah record dengan cepat.
Hubungan ini dinyatakan sebagai R, yang merupakan fungsi pemetaan :
R(NILAI KEY) ADDRESS
dari nilai key ke address dalam penyimpanan sekunder.
Proses Berkas Relatif
Pada waktu sebuah record ditulis kedalam berkas relatif, fungsi pemetaan R digunakan untuk menerjemahkan NILAI KEY DARI RECORD menjadi ADDRESS, dimana record tersebut disimpan.
Berkas relatif harus disimpan dalam media DASD, seperti magnetic disk atau drum.
(SASD, seperti magnetic tape atau pada DASD, seperti magnetic disk)
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; tampa mempengaruhi record lain dalam berkas yang sama.
Ada 3 teknik dasar yang digunakan untuk menyatakan fungsi pemetaan R, dimana
R(NILAI KEY) ADDRESS,
yaitu :
Teknik Pemetaan Langsung (Direct Mapping)
Teknik Pencarian Tabel (Directory Look Up)
Teknik Kalkulasi Alamat
Teknik Pemetaan Langsung (Direct Mapping)
Teknik ini merupakan teknik yang sederhana untuk menerjemahkan nilai record key menjadi address. Ada 2 cara dalam pemetaan langsung, yaitu :
Absolute Addressing (Pengalamatan Mutlak)
Relative Addressing (Pengalamatan Relatif)
Absolute Addressing (Pengalamatan Mutlak)
R(NILAI KEY) ADDRESS
NILAI KEY = ALAMAT MUTLAK
Nilai key yang diberikan oleh pemakai program sama dengan ADDRESS SEBENARNYA dari record tersebut pada penyimpanan sekunder.
KEUNTUNGAN KELEMAHAN
Fungsi pemetaan R sangat sederhana Pemakai harus mengetahui dengan pasti record-record yang disimpan secara fisik.
Tidak membutuhkan waktu lama dalam menentukan lokasi record pada penyimpanan sekunder. Merupakan device dependent.
Perbaikan atau pengubahan device, dimana berkas berada akan mengubah nilai key.
䦋㌌㏒㧀좈琰茞ᓀ㵂Ü Merupakan address space dependent.
Reorganisasi berkas relatif akan menyebabkan nilai key berubah.
Relative Addressing (Pengalamatan Relatif)
R(NILAI KEY) ADDRESS
NILAI KEY = ALAMAT RELATIF
KEUNTUNGAN KELEMAHAN
Fungsi pemetaan R sangat sederhana. bukan device dependent
Nilai key dari sebuah record dapat ditentukan lokasi recordnya dalam sebuah penyimpanan sekunder tanpa memerlukan waktu proses yang berarti. Merupakan address space dependent
Terjadinya pemborosan ruangan
Teknik Pencarian Tabel (Directory Look Up)
Dasar pemikiran pendekatan pencarian tabel adalah sebuah tabel atau direktori dari nilai key dan address.
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.
Teknik Kalkulasi Alamat
Teknik Kalkulasi Alamat
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.
Teknik-teknik yang terdapat pada kalkulasi alamat :
Scatter storage techniques
Randomizing techniques
Key-to-address transformation methods
Direct addressing techniques
Hash table methods
Hashing
Posts
