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 sequentialSebuah 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.
Indeks disusun berdasarkan binary search tree dan digunakan untuk melayani sebuah permintaan untuk mengakses sebuah record tertentu
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 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.
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.
Tidak ada komentar:
Posting Komentar