Welcome

widget

8 Mei 2009

Index Sequential Search


Index adalah struktur data yang mengatur record data pada disk untuk mengoptimalkan beberapa jenis operasi pengambilan (retrieval) tertentu. Index memungkinkan kita untuk secara efektif mengambil semua record yang memenuhi syarat pencarian pada field search key dari index. Memungkinkan untuk membuat index tambahan pada kumpulan record data tertentu, masing – masing dengan search key yang berbeda, untuk mempercepat operasi pencarian yang tidak didukung secara efisien oleh organisasi file yang digunakan untuk menyimpan record data.

Struktur Data Index
Untuk mengatur entry data, dapat digunakan :
1. Tree – Based Indexing
Record dapat diatur dengan menggunakan struktur data seperti Tree. Entry data disusun dalam urutan yang tersortir oleh nilai search key, dan struktur data pencarian hierarki dilakukan yang mengarahkan pencarian ke halaman entry data yang benar.
2. Hash – Based Indexing
Record dapat diatur dengan menggunakan teknik yang disebut hashing untuk secara cepat menemukan record yang memiliki nilai search key tertentu.

Tree – Based Indexing
Berdasarkan organisasi tree, terdapat 2 struktur data index :
1. Indexed Sequential Access Method (ISAM) Tree
Merupakan struktur index statis yang efektif ketika file tidak sering diperbarui, tetapi tree tersebut tidak sesuai untuk file yang bertambah dan berkurang banyak.
2. B+ Tree
Merupakan struktur index yang paling banyak digunakan karena dapat mengatur perubahan dengan baik dan mendukung query persamaan dan rentang.

Dibawah ini adalah penjelasan dari 2 butih diatas, adalah sebagai berilut:
1. ISAM Tree
Entry data pada ISAM index berada dalam halaman leaf dari tree dan halaman overflow tambahan disambungkan ke beberapa halaman leaf. Masing – masing tree node merupakan satu halaman disk, dan semua data terletak dalam halaman leaf. Saat file dibuat, semua halaman leaf dialokasikan secara berurutan dan disortir dalam nilai search key. Halaman non – leaf kemudian dialokasikan.

Gambar 1. Struktur ISAM Index

Jika Dalam ISAM Tree terdapat beberapa sisipan pada file secara berurutan, sehingga lebih banyak entry yang disisipkan ke dalam leaf daripada yang akan dimasukkan pada halaman tunggal, maka halaman tambahan diperlukan karena struktur index statis. Halaman tambahan tersebut dialokasikan dari area overflow.

Gambar 2. Struktur ISAM Tree

Seluruh operasi dasar dari penyisipan, penghapusan, dan pencarian adalah langsung. Untuk pencarian equality selection, dimulai dari root node dan menentukan subtree mana yang dicari dengan membandingkan nilai dalam field search dari record tersebut dengan nilai key dalam node. Pada query rentang, titik permulaan dalam level data (atau leaf) ditentukan dengan cara yang sama, dan kemudian halaman data diambil secara berurut. Untuk insert penyisipan dan penghapusan, halaman yang sesuai ditentukan seperti untuk pencarian, dan record disisipkan atau dihapus dengan menambah halaman overflow, jika diperlukan.

Contoh ISAM Tree

Gambar 3a. Contoh ISAM Tree

Gambar 3b. Contoh ISAM Tree dengan overflow.

2 komentar: