Tabel B-Tree vs Hash

Di MySQL, tipe indeks adalah b-tree, dan akses elemen di b-tree dalam waktu logaritmik diamortisasi O(log(n)).

Di sisi lain, mengakses elemen dalam tabel hash ada di O(1).

Mengapa tabel hash tidak digunakan sebagai pengganti b-tree untuk mengakses data di dalam database?

Anda hanya dapat mengakses elemen dengan kunci utamanya di hashtable. Ini lebih cepat daripada dengan algoritma pohon ( O(1)bukanlog(n) ), tetapi Anda tidak dapat memilih rentang ( semua di antara xdany ). Algoritme pohon mendukung ini di mana Log(n)indeks hash dapat menghasilkan pemindaian tabel penuh O(n). Juga overhead konstan indeks hash biasanya lebih besar ( yang bukan merupakan faktor dalam notasi teta, tetapi masih ada ). Juga algoritma pohon biasanya lebih mudah untuk dipelihara, dikembangkan dengan data, skala, dll.

Indeks hash bekerja dengan ukuran hash yang telah ditentukan sebelumnya, jadi Anda akan mendapatkan beberapa "keranjang" tempat objek disimpan. Objek ini diulangi lagi untuk benar-benar menemukan yang benar di dalam partisi ini.

Jadi, jika Anda memiliki ukuran kecil, Anda memiliki banyak overhead untuk elemen kecil, ukuran besar menghasilkan pemindaian lebih lanjut.

Algoritme tabel hash saat ini biasanya menskalakan, tetapi penskalaan bisa jadi tidak efisien.

Memang ada algoritme hashing yang dapat diskalakan. Jangan tanya saya bagaimana cara kerjanya - ini juga merupakan misteri bagi saya. AFAIK mereka berevolusi dari replikasi terukur di mana hashing ulang tidak mudah.

Yang disebut RUSH - R eplication U nder S calable H ashing, dan algoritma yang demikian disebut algoritma RUSH.

Namun mungkin ada titik di mana indeks Anda melebihi ukuran yang dapat ditoleransi dibandingkan dengan ukuran hash Anda dan seluruh indeks Anda perlu dibuat ulang. Biasanya ini bukan masalah, tetapi untuk database yang sangat-sangat-sangat-sangat besar, ini bisa memakan waktu berhari-hari.

Pengorbanan untuk algoritme pohon kecil dan cocok untuk hampir semua kasus penggunaan dan karenanya menjadi default.

Namun jika Anda memiliki kasus penggunaan yang sangat tepat dan Anda tahu persis apa dan hanya apa yang akan dibutuhkan, Anda dapat memanfaatkan indeks hashing.

Sebenarnya, MySQL tampaknya menggunakan kedua jenis indeks tersebut, baik tabel hash maupun b-tree sesuai dengan tautan berikut .

Perbedaan antara menggunakan b-tree dan tabel hash adalah tabel pertama memungkinkan Anda menggunakan perbandingan kolom dalam ekspresi yang menggunakan operator =,>,> =, <, <=, atau BETWEEN, sedangkan tabel hash hanya digunakan untuk perbandingan kesetaraan yang menggunakan operator = atau <=>.

Kompleksitas waktu hashtable konstan hanya untuk hashtable berukuran cukup (perlu ada cukup bucket untuk menyimpan data). Ukuran tabel database tidak diketahui sebelumnya sehingga tabel harus di-rehash sesekali untuk mendapatkan kinerja yang optimal dari hashtable. Pengulangan juga mahal.

Saya pikir Hashmaps juga tidak berskala, dan bisa mahal ketika seluruh peta perlu di-rehash.

Pilih DB / OS didasarkan pada hashing dan bekerja dengan baik. Dengan lebih banyak memori akhir-akhir ini untuk mendukung tabel hash renggang yang efisien, dan hashing yang berlebihan untuk mendukung kueri rentang sederhana, menurut saya hashing mungkin belum ada tempatnya (beberapa lebih suka memiliki bentuk lain dari pencocokan kemiripan non-rentang, seperti wildcard dan regexps ). Kami juga merekomendasikan penyalinan untuk menjaga collision chain tetap berdekatan saat hierarki memori memiliki perbedaan kecepatan yang besar.