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.
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.
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
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.
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 dibawah ini :
Pada gambar tsb memperlihatkan struktur berkas indeks sequential dengan sebuah indeks berikut pointer yang menuju ke berkas data sequential.
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 Sequensial
Ada 2 pendekatan dasar untuk mengimplementasikan konsep dari organisasi berkas indeks sekuensial :
• Blok Indeks dan Data (Dinamik)
• Prime dan Overflow Data Area (Statik)
Kedua pendekatan tersebut mengunakan 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 sekuensial dengan ruang bebas yang didistribusikan antar populasi record.
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
Prime dan Overflow Data Area
Pendekatan lain untuk mengimplementasikan berkas indek sekuensial adalah berdasarkan struktur indek dimana struktur indek ini lebih ditekankan pada karakteristik fisik dari penyimpanan, dibandingkan dengan distribusi secara logik dari nilai key.
Indeksnya ada beberapa tingkat, misalnya tingkat cylinder index dan tingkat track index. Berkas datanya secara umum diimplementasikan sebagai 2 berkas, yaitu prime area dan overflow area.
Misal 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 index.
“Entry pada indeks ini adalah dalam bentuk :”
nilai key tertinggi, pointer
Tingkat kedua dari indeks dinamakan cylinder index.
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 index. Karena BAT ada didepan LYNX, maka pointer dari LYNX akan menunjuk ke cylinder index. Karena BAT ada didepan ELEPHANT, maka pointer dari ELEPHANT akan menunjuk ke track 0 dari cylinder 1. Karena BAT ada dibelakang BABOON dan didepan COW, maka pointer dari BABOON akan menunjuk ke track 2, yang mencari secara sekuensial, sampai BAT ditemukan.
Permintaan untuk mengakses data secara sekuensial 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
Sedangkan dalam perintah berikut 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 ditunjukan oleh entry prime data area.
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.
Tidak ada komentar:
Posting Komentar