sistem sistem basis basis data data – – ti ti ukdw ukdw
Indexing
Materi Minggu ke-10
Teknik Informatika Universitas Kristen Duta Wacana Yogyakarta
04/07/13
budi susanto
1
sistem sistem basis basis data data – – ti ti ukdw ukdw
Tujuan ●
Memahami Tujuan Index pada Database
●
Memahami model dasar Index
●
Memahami algoritma dasar B+Tree
04/07/13
budi susanto
2
sistem sistem basis basis data data – – ti ti ukdw ukdw
Konsep Dasar ●
●
Indexing digunakan untuk mempercepat akses terhadap data yang diperlukan. Search Key ●
●
Atribut yang digunakan untuk mencari record dalam file
Index File ●
Terdiri dari record-record dengan bentuk: search-key
●
pointer
Index file biasanya berukuran lebih kecil daripada file data.
04/07/13
budi susanto
3
sistem sistem basis basis data data – – ti ti ukdw ukdw
Matrix Evaluasi Index ●
Access Type
●
Access Time
●
Insertion Time
●
Deletion Time
●
Space Overhead
04/07/13
budi susanto
4
sistem sistem basis basis data data – – ti ti ukdw ukdw
Tipe Index ●
Ordered Index ●
●
Search key disimpan dalam suatu urutan tertentu
Hash Index ●
04/07/13
Search key disebar dengan menggunakan fungsi hash.
budi susanto
5
sistem sistem basis basis data data – – ti ti ukdw ukdw
Ordered Index
04/07/13
budi susanto
6
sistem sistem basis basis data data – – ti ti ukdw ukdw
Ordered Index ●
●
Pada Ordered Index, entri index disimpan secara terurut berdasar nilai search key Primary index: ●
●
●
●
Index dimana urutan search key menyatakan urutan data dalam sequential file. Disebut juga dengan clustering index Biasanya Primary Key
Secondary index : ●
●
Index dimana urutan seach key berbeda dengan urutan data dalam sequential file. Disebut juga non-clustering index
●
Index-Sequential file: file sequential terurut dengan primary index.
●
Ada dua tipe Ordered Index : Dense dan Sparse
04/07/13
budi susanto
7
sistem sistem basis basis data data – – ti ti ukdw ukdw
Contoh Clustering Index
04/07/13
budi susanto
8
sistem sistem basis basis data data – – ti ti ukdw ukdw
Dense Index ●
●
Sebuah index item muncul untuk setiap nilai search key dalam file. Index item berisi nilai search key dan pointer ke record data sesungguhnya.
04/07/13
budi susanto
9
sistem sistem basis basis data data – – ti ti ukdw ukdw
Dense Secondary Index
04/07/13
budi susanto
10
sistem sistem basis basis data data – – ti ti ukdw ukdw
Sparse Index ●
Item index dibuat hanya untuk beberapa record saja.
●
Untuk menemukan record dengan nilai search key K ●
●
●
Temukan item index dengan nilai search key terbesar < K. Cari data yang ditemukan mulai dari record seperti yang ditunjuk oleh item index.
Sparse Index hanya dapat digunakan jika atribut kunci yang digunakan adalah dalam keadaan terurut (clustering index).
04/07/13
budi susanto
11
sistem sistem basis basis data data – – ti ti ukdw ukdw
Sparse Index
04/07/13
budi susanto
12
sistem sistem basis basis data data – – ti ti ukdw ukdw
Dense vs Sparse ●
●
●
Dense index secara umum lebih cepat Sparse index membutuhkan space yang lebih kecil dan memiliki biaya perawatan yang lebih rendah untuk penambahan dan penghapusan. (why?) Kompromi yang baik: ●
Memiliki sparse index dengan satu entry per blok, dengan nilai search key terkecil dalam blok. – –
–
04/07/13
Biaya terbesar adalah meletakkan sebuah blok ke memori utama. Dijamin memiliki blok yang betul, kecuali record berada pada overflow blok (dapat beberapa blok). Ukuran index masih dapat tetap kecil.
budi susanto
13
sistem sistem basis basis data data – – ti ti ukdw ukdw
Latihan Dense Index ●
Buatlah Struktur Dense Index untuk data berikut, search key adlaah NAMA: NIM 22071234 22073456 22086312 22083920 22095312 22098982 22099482
04/07/13
NAMA Abu Nawas Aladin Iron Man Superman Batman Spiderman Arjuna budi susanto
14
sistem sistem basis basis data data – – ti ti ukdw ukdw
Multilevel Index ●
●
●
Walaupun dengan sparse index, ukuran index masih akan tumbuh terlalu besar. Untuk 100,000 record, 10 / blok, dengan satu index item per blok, maka butuh 10,000 index item! Jika index terlalu besar untuk disimpan dalam memori utama, pengaksesan/pencarian menjadi terlalu mahal. Untuk mengurangi jumlah pengaksesan disk terhadap index item, simpan primary index dalam disk sebagai sebuah sequential file dan bangun sebuah sparse index terhadapnya. ● ●
●
outer index – sebuah sparse index dari primary index inner index – file primary index
Bahkan jika outer index terlalu besar untuk diletakkan dalam memori utama, dapat dibentuk level index lain.
04/07/13
budi susanto
15
sistem sistem basis basis data data – – ti ti ukdw ukdw
Multilevel Index
04/07/13
budi susanto
16
sistem sistem basis basis data data – – ti ti ukdw ukdw
Latihan Multilevel Index ●
Buatlah Struktur Multilevel Index untuk data berikut (1 blok maks. 3 record), dimana NIM adalah PK: NIM 22071234 22073456 22086312 22083920 22095312 22098982 22099482
04/07/13
NAMA Abu Nawas Aladin Iron Man Superman Batman Spiderman Arjuna budi susanto
17
sistem sistem basis basis data data – – ti ti ukdw ukdw
Update Index: Insert ●
●
Temukan posisi record yang tepat untuk penyisipan. Dense Index ●
●
●
Tambahkan nilai search key pada index dan tabel jika belum ada Jika telah ada search key pada index, tambahkan data baru hanya pada tabel.
Sparse Index ●
04/07/13
tidak ada perubahan kecuali blok baru terbentuk budi susanto
18
sistem sistem basis basis data data – – ti ti ukdw ukdw
Update Index: Delete Dense Index ●
●
●
Temukan record yang akan dihapus. Jika record yang dihapus merupakan satusatunya yang ditunjuk pada item index, maka hapus keduanya Selain itu, jika index item merujuk pada search-key record yang dihapus lebih dari satu, maka hapus record datanya saja. ●
04/07/13
Selain itu, jika record yang dihapus merupakan record awal yang ditunjuk oleh index item, maka update item item ke record selanjutnya. budi susanto
19
sistem sistem basis basis data data – – ti ti ukdw ukdw
Update Index: Delete Sparse Index ●
●
●
Temukan record yang akan dihapus. Jika index tidak berisi search-key yang dihapus, maka index tidak perlu diupdate. Selain itu, jika record yang terhapus adalah satu-satunya record yang dirujuk oleh item index, maka item index di update untuk merujuk ke record search-key berikutnya. Jika search-key sudah ada pada index, maka item index hasil update akan dihapus. ●
Selain itu, jika item index untuk search-key merujuk ke record yang dihapus, maka sistem akan mengupdate penunjuk ke record selanjutnya yang memiliki search-key yang sama.
04/07/13
budi susanto
20
sistem sistem basis basis data data – – ti ti ukdw ukdw
Secondary Index ●
●
Seringkali, diinginkan mencari semua record berdasar nilai dari suatu field tertentu (yang bukan search key yang sudah dibentuk dalam primary index). Kita dapat memiliki sebuah secondary index dengan suatu index item untuk setiap nilai search-key value; index item menunjuk ke sebuah tempat yang berisi pointer ke record sesungguhnya berdasar nilai search-key tertentu.
04/07/13
budi susanto
21
sistem sistem basis basis data data – – ti ti ukdw ukdw
Secondary Index
04/07/13
budi susanto
22
sistem sistem basis basis data data – – ti ti ukdw ukdw
B+ Tree Index
04/07/13
budi susanto
23
sistem sistem basis basis data data – – ti ti ukdw ukdw
B+ Tree Index ●
●
●
●
●
Kerugian utama dari organisasi index-sequential file adalah unjuk kerja akan menurun seiring dengan bertumbuhnya file. Struktur file B+ -tree, menjaga efisiensi organisasinya walaupun sering terjadi insert dan delete. Kerugiannya, B+Tree membutuhkan biaya penambahan dan penghapusan tambahan dan juga ruang penyimpanan tambahan. Sebuah index B + -tree adalah balanced tree, dimana dalam setiap jalur dari root ke sebuah daun memiliki panjang yang sama. Setiap node bukan daun dalam tere harus memiliki anak antara n/2 sampai n, dimana n adalah tetap untuk pohon tertentu.
04/07/13
budi susanto
24
sistem sistem basis basis data data – – ti ti ukdw ukdw
Struktur Node B+ Tree ●
Struktur Node
●
Ki adalah nilai search key
●
●
Pi adalah pointer ke anak (node bukan daun) atau pointer ke record atau kelompok data (node daun) Search key dalam sebuah node diurutkan ●
04/07/13
K1 < K2 < K3 < ... < Kn budi susanto
25
sistem sistem basis basis data data – – ti ti ukdw ukdw
Node Daun B+ Tree ●
●
●
For i = 1, 2, . . ., n–1, pointer Pi baik menunjuk ke file record dengan nilai search-key Ki, atau ke sekelompok pointer ke file record, setiap index item memiliki nilai search-key K i. JIKA Li, Lj adalah node daun DAN i < j, nilai search-key Li < nilai search-key Lj Pn menunjuk ke node daun berikut dalam urutan search-key
04/07/13
budi susanto
26
sistem sistem basis basis data data – – ti ti ukdw ukdw
Contoh Node Daun
04/07/13
budi susanto
27
sistem sistem basis basis data data – – ti ti ukdw ukdw
Node Bukan Daun B+ Tree ●
●
Node bukan daun membentuk sebuah multilevel sparse index untuk node daun. Untuk node bukan daun dengan jumlah m pointer: ●
●
04/07/13
Semua search-key dalam subtree dimana nilai yang ditunjuk P1 < K1. For 2 ≤ i ≤ n – 1, semua search-keys dalam subtree dimana Pi memiliki nilai >= Ki–1 dan <= Km–1.
budi susanto
28
sistem sistem basis basis data data – – ti ti ukdw ukdw
Contoh B+ Tree (n=4)
04/07/13
budi susanto
29
sistem sistem basis basis data data – – ti ti ukdw ukdw
Contoh B+ Tree (n=5) ●
Node daun harus memiliki antara nilai 2 dan 4 ●
●
Node bukan daun selain root harus memiliki antara 3 – 5 anak ●
●
([(n–1)/2] dan n –1).
([(n/2)] dan n ).
Root harus memiliki setidaknya 2 anak.
04/07/13
budi susanto
30
sistem sistem basis basis data data – – ti ti ukdw ukdw
Query B+Tree Index ●
Temukan semua record dengan nilai search-key k. ● ●
●
●
●
●
Mulai dari node root Tentukan node dengan nilai search key terkecil > k. Jika ditemukan nilainya, misal Kj. Maka ikuti Pi ke node anak Selain itu jika k > Km–1, dimana terdapat m pointer dalam node. Maka ikuti Pm ke node anak. Jika node yang dicapai dari pointer di atas, adalah bukan node daun, ulangi prosedur di atas terhadap node bukan daun, dan ikuti pointer yang dihasilkan. Akhirnya mencapai node daun. Jika untuk beberapa i, kunci Ki = k ikuti pointer Pi ke record yang dituju. Selain itu tidak ada record dengan nilai k.
04/07/13
budi susanto
31
sistem sistem basis basis data data – – ti ti ukdw ukdw
Contoh Query B+ Tree Root 13
2*
3*
5*
7*
14*
17
19* 20*
16*
24
30
22*
24*
27* 29*
33*
34*
38*
39*
Root 13
2*
04/07/13
3*
5*
7*
14* 16*
17
24
19* 20* 22*
budi susanto
30
24* 27* 29*
33* 34* 38* 39*
32
sistem sistem basis basis data data – – ti ti ukdw ukdw
Insert B+-Tree Index ●
Temukan node daun L yang tepat.
●
Letakkan data ke L. ●
●
Jika L memiliki space cukup, done! Selain itu, harus split L (menjadi L dan node baru L2) – – –
Sebar ulang entri, copy up middle key. Insert index entry yang menunjuk ke L2 ke induk dari L. Hal ini dapat terjadi secara rekursif ●
● ●
04/07/13
Untuk split node index, sebar ulang redistribute entri, tapi push up middle key. (berbeda dengan leaf splits.) Splits “grow” tree; root split menambah tinggi tree. Tree growth: buat wider atau one level taller at top.
budi susanto
33
sistem sistem basis basis data data – – ti ti ukdw ukdw
Contoh Insert 8* ke B+-Tree Index ●
Temukan daun, dengan cara seperti pencarian.
●
Tangani overflow dengan splitting. Root 13
2*
3*
5*
04/07/13
7*
14*
16*
17
19* 20*
24
22*
budi susanto
30
24*
27* 29*
33*
34*
38*
39*
34
sistem sistem basis basis data data – – ti ti ukdw ukdw
Contoh Insert 8* ke B+-Tree Index ●
Tinjaulah berapa tempat minimum yang dijamin baik dalam leaf maupun index node. Entry to be inserted in parent node. (Note that 5 is s copied up and continues to appear in the leaf.)
5
2*
3*
5*
17
5
04/07/13
13
24
7*
8*
Entry to be inserted in parent node. (Note that 17 is pushed up and only appears once in the index. Contrast this with a leaf split.)
30
budi susanto
35
sistem sistem basis basis data data – – ti ti ukdw ukdw
Sebelum dan sesudah insert Root
13
3*
2*
5*
7*
14*
17
19* 20*
16*
24
22*
30
24*
27* 29*
33*
34*
38*
39*
Root 17
5
2*
3*
04/07/13
24
13
5*
7*
8*
14* 16*
19* 20* 22*
budi susanto
30
24* 27* 29*
33* 34* 38* 39*
36
sistem sistem basis basis data data – – ti ti ukdw ukdw
Delete B+-Tree Index ●
●
Mulai dari root, temukan daun L dimana entry yang dihapus berada. Buang entri tersebut. ●
●
Jika L adalah sedikitnya separo penuh, done! Jika L memiliki hanya d-1 entri, –
– ●
04/07/13
Cobalah untuk re-distribute, meminjam dari sibling (nyatakan parent node sama dengan L). Jika re-distribution gagal, merge L dan sibling.
Jika merge terjadi, entri (yang menunjuk ke L) harus dihapus dari induk L. budi susanto
37
sistem sistem basis basis data data – – ti ti ukdw ukdw
Contoh Delete 19* dan 20* ●
Deleting 19* is easy.
●
Deleting 20* is done with re-distribution. Root 17
5
2*
3*
04/07/13
24
13
5*
7*
8*
14* 16*
19* 20* 22*
budi susanto
30
24* 27* 29*
33* 34* 38* 39*
38
sistem sistem basis basis data data – – ti ti ukdw ukdw
Setelah Delete 19* dan 20* Root 17
5
2*
3*
04/07/13
27
13
5*
7*
8*
14* 16*
22* 24*
budi susanto
30
27* 29*
33* 34* 38* 39*
39
sistem sistem basis basis data data – – ti ti ukdw ukdw
Latihan B+ Tree Index ●
Buatlah Struktur B+ Tree Index untuk data berikut (n=3), dimana NIM adalah PK: NIM
NAMA
22071234
Abu Nawas
22073456
Aladin
22086312
Iron Man
22083920
Superman
22095312
Batman
22098982
Spiderman
22099482
Arjuna
04/07/13
budi susanto
40
sistem sistem basis basis data data – – ti ti ukdw ukdw
B-Tree Index ●
●
●
●
●
B-tree index mirip dengan B+ -tree index. Perbedaannya adalah B-tree membuang nilai search key yang redundan. Dalam B+ -tree, beberapa nilai search key muncul 2 kali. B-tree memungkinkan nilai search key muncul hanya sekali. Sehingga kita dapat menyimpan index dengan space lebih kecil
04/07/13
budi susanto
41
sistem sistem basis basis data data – – ti ti ukdw ukdw
B Tree ●
Keuntungan: ● ●
●
Mengurangi penyimpanan redundan. Beberapa pencarian lebih cepat (kunci mungkin berada di node bukan daun).
Kerugian : ●
●
04/07/13
Node daun dan bukan daun memiliki ukuran berbeda (struktur penyimpanan rumit) Penghapusan mungkin terjadi dalam node bukan daun (lebih rumit) budi susanto
42
sistem sistem basis basis data data – – ti ti ukdw ukdw
B Tree
04/07/13
budi susanto
43
sistem sistem basis basis data data – – ti ti ukdw ukdw
Definisi Index dengan SQL ●
Pembuatan index create index
on ()
●
Contoh : create index
●
●
b-index on branch(branch-name)
Gunakan create unique index untuk menyatakan kondisi bahwa search key adalah candidate key. Untuk membuang index drop index
04/07/13
budi susanto
44
sistem sistem basis basis data data – – ti ti ukdw ukdw
Multiple Key ●
Diasumsikan kita punya index kombinasi search-key (branch-name, balance).
●
Dengan klausa WHERE ●
●
●
●
Index dengan kombinasi search-key akan mengambil hanya record yang sesuai dengan kedua kondisi tersebut. Menggunakan index terpisah lebih efisien— kita mungkin mengambil beberapa record yang sesuai dengan satu kondisi saja. Dapat juga menangani ●
●
where branch-name = “Perryridge” and balance = 1000
where branch-name = “Perryridge” and balance < 1000
Namun tidak dapat secara efisien untuk ●
where branch-name < “Perryridge” and balance = 1000
04/07/13
budi susanto
45
sistem sistem basis basis data data – – ti ti ukdw ukdw
Bitmap Index ●
●
Bitmap index adalah tipe index khusus yang dirancang untuk efisiensi query berdasar beberapa kunci. Record dalam suatu relasi diasumsikan diberi nomor berurutan, misal mulai dari 0. ●
Diberikan sejumlah n, akan memudahkan untuk mengambil record ke n. –
04/07/13
Lebih mudah jika record berukuran tetap.
budi susanto
46
sistem sistem basis basis data data – – ti ti ukdw ukdw
Bitmap Index ●
●
●
●
Dapat diterapkan pada atribut yang secara relatif memiliki perbedaan nilai yang sedikit. Contoh. Jenis kelamin, negara, propinsi, … Contoh. Level-pendapatan (pendapatan dibagi ke dalam sejumlah kecil level, seperti 0-9999, 10000-19999, 20000-50000, 50000- tak terhingga) Sebuah bitmap adalah array bit.
04/07/13
budi susanto
47
sistem sistem basis basis data data – – ti ti ukdw ukdw
Contoh Bitmap Index
●
Male dengan level pendapatan L1 ●
●
10010 AND 10100 = 10000
Di Oracle create bitmap index namaIndex on nmTable(fieldname);
04/07/13
budi susanto
48
sistem sistem basis basis data data – – ti ti ukdw ukdw
Selesai!
04/07/13
budi susanto
49