Index dan Hashing Basis Data

Dalam mengorganisasikan file basis data, dikenal cara mengorganisasi file sebagai berikut:

• Heap (random order) files yaitu untuk akses file scan yang meliputi retrieval semua record yang ada.
• Sorted Files yaitu dikatakan terbaik jika records harus di-retieve dalam urutan tertentu, atau hanya suatu jangkauan (range) records tertentu yang diperlukan untuk di-retrieve.
• Indexes yaitu struktur data yang mengorganisasi records dengan menggunakan trees atau hashing.
• Seperti halnya sorted files, indexes mempercepat pelacakan terhadap subset dari records, berdasarkan nilai-nilai ("search key") fields tertentu.
• Proses updates dari records jauh lebih cepat dibandingkan dalam sorted files.

Indexes

• Sebuah index pada sebuah file akan mempercepat proses pemilihan pada search key fields dari index tersebut.
• Sembarang subset dari fields suatu relasi (tabel) dapat digunakan sebagai search key dari index pada relasi tersebut.
• Search key tidak sama dengan key (satu set minimal dari fields yang dapat secara unik mengidentifikasi sebuah record dalam suatu relasi).
• Sebuah index berisikan sekumpulan data entries, dan memberikan dukungan untuk proses retrieval yang efisien terhadap semua data entries k* untuk sebuah nilai k yang diberikan.
• Index pada satu set fields yang meliputi primary key disebut primary index; sedangkan indexes lainnya disebut secondary indexes.
• Dua buah data entries dikatakan terduplikasi jika keduanya mempunyai nilai yang sama untuk search key field yang diasosiasikan dengan suatu
• Primary key index dijamin tidak mengandung duplikasi data entries
• Secara umum, secondary index dapat mengandung duplikasi data entries
• Index pada satu set fields meliputi candidate key, yang juga dijamin tidak mengandung duplikasi data entries, disebut unique index.

 Alternatif:

1. Data record dengan nilai key k
2. <k, rid dari data record dengan nilai search key k>
3. <k, list rids dari data records dengan nilai search key k>

Pemilihan alternatif untuk data entries bergantung pada teknik "indexing" yang digunakan untuk memperoleh data entries berdasarkan nilai key k.

• Contoh teknik indezxing: B+ trees, hash-based structures
• Secara tipikal, index berisikan informasi tambahan (auxiliary information) yang mengarahkan pelacakan pada data entries yang diinginkan.

Alternatif 1:

• Dalam alternatif ini, struktur index adalah sebuah organisasi file dari data records (bukan berupa Heap file atau sorted file).
• Paling banyak hanya satu index untuk sekumpulan data records yang diberikan yang dapat menggunakan alternatif 1.
• jika tidak, data records akan terduplikasi, dan akan menimbulkan terjadinya redundansi storage dan inkonsistensi data.
• Jika data records berukuran sangat besar, maka jumlah "pages" yang berisikan data entries akan menjadi besar. Secara tipikal hal ini akan meyebabkan ukuran dari informasi tambahan dalam index menjadi besar.

Alternatif 2 dan 3:

• Secara tipikal, data entries jauh lebih kecil dibandingkan dengan data records. Sehingga, alternatif ini akan menjadi lebih baik untuk data records yang besar, khususnya jika search key berukuran kecil.
  
• Bagian struktur index yang digunakan untuk mengarahkan pelacakan (yang bergantung pada ukuran data entries) akan menjadi jauh lebih kecil dibandingkan dengan alternatif 1.
• Alternatif 3 lebih kompak (utilisasi ruang penyimpanan yang lebih baik) dari pada alternatif 2, tetapi dapat menimbulkan data entries dengan ukuran yang variabel, bergantung pada jumlah data records untuk sebuah nilai search key yang diberikan.

 

Klassifikasi Index

• Primary v.s. secondary adalah jika search key berupa primary key, maka disebut primary index, selebihnya disebut secondary indexes.
• Unique index: Search key berupa sebuah candidate key
• Clustered v.s. unclustered adalah jika urutan data records sama dengan, atau 'mendekati', urutan data entries, maka disebut clustered index.
• Alternatif 1 mengimplementasikan clustered index. Dalam praktek, clustered index juga mengimplikasikan Alternatif 1 (karena struktur sorted files jarang digunakan).
• Sebuah file dapat mempunyai clustered index paling banyak pada satu search key.
• Biaya untuk melakukan retrieving data records melalui index sangat bervariasi, bergantung pada apakah index-nya adalah clustered atau tidak 

Clusterd v.s. Unsclustered Index

Diasumsikan menggunakan data entries alternatif 2, dan data records diasumsikan disimpan dalam Heap file.

• Untuk membangun clustered index, pertama Heap file harus disorting (dengan menyediakan beberapa ruang kosong pada setiap page untuk keperluan penyisipan yang akan datang).
• Overflow pages mungkin diperlukan untuk penyisipan. Sehingga urutan data records menjadi 'mendekati ke', bukan sama dengan, urutan terurut (sorted order).

 

Hash-Based Indexes

• Bagus untuk "equality selections"
• Index berupa sekumpulan buckets. Bucket sama dengan primary page plus nol atau lebih oeverflow pages.
• Hashing function h: h(r)=bucket dimana record r berada. Untuk ini, h akan mencari search key fields dari r.
• Jika alternatif 1 digunakan, maka buckets berisikan data records; jika tidak,buckets berisikan pasangan-pasangan <key, rid> atau pasangan-pasangan <key, rid-list>