Pengindeksan basis data singkatnya dengan B+tree dan Hash sebagai perbandingan

Orang sering mengatakan bahwa pengindeksan adalah teknik masuk untuk memproses kueri secara efisien jika basis data Anda cukup besar. Postingan ini untuk meringkas apa itu indeks basis data dan meninjau kembali hash dan B+Tree.

Indeks adalah struktur data yang mengatur catatan untuk mengoptimalkan jenis operasi pengambilan tertentu. Kami dapat membuat indeks pada bidang tabel kemudian mengambil semua catatan yang memenuhi kondisi pencarian di search-key bidang. Tanpa indeks, kueri kami akhirnya akan memindai secara linier seluruh konten tabel untuk mengambil hanya satu atau beberapa catatan.

Dalam posting ini, saya ingin merangkum kinerja dan kasus penggunaan dua teknik pengindeksan umum:Indeks hash dan B+pohon

Indeks hash

Teknik ini banyak digunakan untuk membuat indeks di memori utama karena pengambilannya cepat oleh alam. Ini memiliki kompleksitas operasi O(1) rata-rata dan kompleksitas penyimpanan O(n).
Di banyak buku, orang menggunakan istilah bucket untuk menunjukkan unit penyimpanan yang menyimpan satu atau lebih catatan
Ada dua hal yang perlu didiskusikan dalam hal hashing:

• Fungsi hash:memetakan kunci penelusuran (sebagai inputnya) ke bilangan bulat yang mewakili kunci tersebut dalam keranjang.
• Skema hashing:cara menangani tabrakan kunci setelah hashing.

Beberapa orang bertanya:mengapa tabrakan? Apakah fungsi hash yang sempurna pernah ada? Faktanya, katakanlah kunci Anda adalah kumpulan tak terbatas, tidak mungkin untuk memetakannya ke dalam kumpulan bilangan bulat 32-bit tanpa tabrakan. Harus ada trade-off antara komputasi dan tingkat tabrakan.

Ada beberapa skema hashing yang layak disebutkan:linear probing, chained hashing, dan hashing yang dapat diperpanjang. Cari/masukkan/hapus algoritma bervariasi menurut skema hashing, misalnya, hashing berantai menangani tabrakan kunci dengan menempatkan elemen memiliki nilai hash yang sama dalam ember yang sama.

Kelebihan

• Indeks hash cocok untuk pencarian kesetaraan atau kunci utama. Kueri dapat memanfaatkan indeks hash untuk mendapatkan biaya pencarian O(1) yang diamortisasi. Contoh:SELECT name, id FROM student WHERE id = '1315';

Kontra

Tabel hash memiliki beberapa batasan:

• Kueri rentang tidak efisien. Tabel hash didasarkan pada distribusi seragam. Dengan kata lain, Anda tidak memiliki kendali di mana entri indeks akan ditempatkan.
• Skalabilitas rendah:kinerja operasi pencarian dapat menurun ketika ada banyak tabrakan dan perlu mengubah ukuran tabel hash kemudian mengulangi entri indeks yang ada.

B+Pohon

Ini adalah struktur data pohon self-balancing yang menyimpan data dalam urutan terurut dan memungkinkan pencarian cepat dalam setiap node, biasanya menggunakan pencarian biner.
B+Tree adalah implementasi indeks standar di hampir semua sistem basis data relasional.

B+Tree pada dasarnya adalah pohon pencarian M-way yang memiliki struktur sebagai berikut:

• keseimbangan sempurna:simpul daun selalu memiliki tinggi yang sama.
• setiap node dalam selain root setidaknya setengah penuh (M/2 1 <=jumlah kunci <=M 1).
• setiap simpul dalam dengan kunci k memiliki k+1 turunan bukan nol.

Setiap simpul pohon memiliki larik pasangan nilai kunci yang diurutkan. Pasangan kunci-nilai dibangun dari (nilai kunci pencarian, pointer) untuk root dan node dalam. Nilai simpul daun dapat berupa 2 kemungkinan:

• catatan sebenarnya
• penunjuk ke catatan sebenarnya

Cari nilai v

• Mulai dengan simpul akar
• Meskipun simpul bukan simpul daun, kami melakukan:
  • Temukan Ki terkecil di mana Ki>=v
  • Jika Ki ==v:setel simpul saat ini ke simpul yang ditunjuk oleh Pi+1
  • Jika tidak, setel node saat ini ke node yang ditunjuk oleh Pi

Kunci duplikat

Secara umum, kunci pencarian dapat digandakan, untuk mengatasi ini, sebagian besar implementasi basis data muncul dengan kunci pencarian gabungan. Misalnya, kita ingin membuat indeks pada student_name maka kunci pencarian gabungan kami harus (nama_siswa, Ap) di mana Ap adalah kunci utama tabel.

Kelebihan

Ada dua fitur utama yang ditawarkan B+tree:

• Meminimalkan operasi I/O
  • Penurunan tinggi:B+Pohon memiliki faktor percabangan yang cukup besar (nilai antara 50 dan 2000 sering digunakan) yang membuat pohon gemuk dan pendek. Gambar di bawah mengilustrasikan B+Tree dengan tinggi 2. Seperti yang kita lihat node tersebar, dibutuhkan lebih sedikit node untuk melintasi ke daun. Biaya mencari satu nilai adalah tinggi pohon + 1 untuk akses acak ke tabel.
• Skalabilitas:
  • Anda memiliki performa yang dapat diprediksi untuk semua kasus, khususnya O(log(n)). Untuk database, biasanya lebih penting daripada memiliki performa kasus terbaik atau rata-rata yang lebih baik.
  • Pohon selalu tetap seimbang dengan implementasinya. A B+Tree dengan n kunci selalu memiliki kedalaman O(log(n)). Dengan demikian, kinerja tidak akan menurun jika database bertambah besar. Pohon empat tingkat dengan faktor percabangan 500 dapat menyimpan hingga 256 TB asalkan halaman berukuran 4 KB.

• B+Tree paling cocok untuk kueri rentang, misalnya "SELECT * FROM student WHERE age > 20 AND age < 22"

Kesimpulan

Meskipun indeks hash berkinerja lebih baik dalam hal kueri pencocokan tepat, B+Tree bisa dibilang merupakan struktur indeks yang paling banyak digunakan di RDBMS berkat kinerjanya yang konsisten secara keseluruhan dan skalabilitas tinggi.

Baru-baru ini, pohon gabungan terstruktur-log (LSM-tree) telah menarik minat yang signifikan sebagai pesaing B+-tree, karena struktur datanya dapat memungkinkan efisiensi penggunaan ruang penyimpanan yang lebih baik. Saya akan menyelidikinya lebih lanjut dan membuat postingan tentangnya dalam waktu dekat.