DBMS - Pengindeksan
Kita tahu bahwa data disimpan dalam bentuk catatan. Setiap rekaman memiliki bidang kunci, yang membantunya dikenali secara unik.
Pengindeksan adalah teknik struktur data untuk mengambil catatan dari file database secara efisien berdasarkan beberapa atribut yang telah dilakukan pengindeksan. Pengindeksan dalam sistem database serupa dengan yang kita lihat di buku.
Pengindeksan didefinisikan berdasarkan atribut pengindeksannya. Pengindeksan dapat dari jenis berikut -
Primary Index- Indeks primer didefinisikan pada file data yang dipesan. File data diurutkan pada akey field. Bidang kunci umumnya adalah kunci utama dari relasi.
Secondary Index - Indeks sekunder dapat dihasilkan dari bidang yang merupakan kunci kandidat dan memiliki nilai unik di setiap rekaman, atau non-kunci dengan nilai duplikat.
Clustering Index- Indeks clustering didefinisikan pada file data yang dipesan. File data diurutkan pada bidang non-kunci.
Pengindeksan Berurutan terdiri dari dua jenis -
- Indeks Padat
- Indeks Renggang
Indeks Padat
Dalam indeks padat, ada catatan indeks untuk setiap nilai kunci pencarian dalam database. Ini membuat pencarian menjadi lebih cepat tetapi membutuhkan lebih banyak ruang untuk menyimpan catatan indeks itu sendiri. Catatan indeks berisi nilai kunci pencarian dan penunjuk ke catatan aktual di disk.
Indeks Renggang
Dalam indeks renggang, catatan indeks tidak dibuat untuk setiap kunci pencarian. Catatan indeks di sini berisi kunci pencarian dan penunjuk aktual ke data di disk. Untuk mencari catatan, pertama-tama kita lanjutkan dengan catatan indeks dan sampai di lokasi data yang sebenarnya. Jika data yang kita cari tidak ada di tempat yang langsung kita jangkau dengan mengikuti indeks, maka sistem memulai pencarian berurutan hingga data yang diinginkan ditemukan.
Indeks Bertingkat
Catatan indeks terdiri dari nilai kunci pencarian dan penunjuk data. Indeks bertingkat disimpan di disk bersama dengan file database yang sebenarnya. Seiring bertambahnya ukuran database, begitu pula ukuran indeks. Ada kebutuhan yang sangat besar untuk menyimpan catatan indeks di memori utama untuk mempercepat operasi pencarian. Jika indeks satu tingkat digunakan, maka indeks ukuran besar tidak dapat disimpan dalam memori yang mengarah ke beberapa akses disk.
Indeks Multi-level membantu memecah indeks menjadi beberapa indeks yang lebih kecil untuk membuat level terluar menjadi sangat kecil sehingga dapat disimpan dalam satu blok disk, yang dapat dengan mudah ditampung di mana saja di memori utama.
B + Pohon
Pohon AB + adalah pohon pencarian biner seimbang yang mengikuti format indeks multi-level. Simpul daun dari pohon B + menunjukkan penunjuk data aktual. Pohon B + memastikan bahwa semua simpul daun tetap pada ketinggian yang sama, sehingga seimbang. Selain itu, simpul daun dihubungkan menggunakan daftar tautan; Oleh karena itu, pohon B + dapat mendukung akses acak serta akses berurutan.
Struktur Pohon B +
Setiap simpul daun memiliki jarak yang sama dari simpul akar. Pohon AB + adalah urutannyan dimana nditetapkan untuk setiap pohon B + .
Internal nodes -
- Node internal (non-daun) berisi setidaknya ⌈n / 2⌉ pointer, kecuali node root.
- Paling banyak, simpul internal dapat berisi n petunjuk.
Leaf nodes -
- Node daun berisi setidaknya ⌈n / 2⌉ pointer record dan nilai kunci ⌈n / 2⌉.
- Paling banyak, simpul daun bisa berisi n record pointers dan n nilai kunci.
- Setiap simpul daun berisi satu penunjuk blok P untuk menunjuk ke simpul daun berikutnya dan membentuk daftar tertaut.
B + Penyisipan Pohon
Pohon B + diisi dari bawah dan setiap entri dilakukan di simpul daun.
- Jika simpul daun meluap -
Pisahkan node menjadi dua bagian.
Partisi di i = ⌊(m+1)/2⌋.
Pertama i entri disimpan dalam satu node.
Sisa entri (i + 1 dan seterusnya) dipindahkan ke node baru.
ith kunci diduplikasi di induk daun.
Jika simpul non-daun meluap -
Pisahkan node menjadi dua bagian.
Partisi node di i = ⌈(m+1)/2⌉.
Entri hingga i disimpan dalam satu node.
Sisa entri dipindahkan ke node baru.
B + Penghapusan Pohon
Entri B + tree dihapus di node daun.
Entri target dicari dan dihapus.
Jika itu adalah simpul internal, hapus dan ganti dengan entri dari posisi kiri.
Setelah penghapusan, underflow diuji,
Jika terjadi underflow, distribusikan entri dari node kiri ke sana.
Jika distribusi tidak memungkinkan dari kiri, maka
Distribusikan dari node langsung ke sana.
Jika distribusi tidak memungkinkan dari kiri atau dari kanan, maka
Gabungkan node dengan kiri dan kanan ke sana.