Mengapa MySQL tidak memiliki indeks hash pada MyISAM atau InnoDB?

Saya memiliki aplikasi yang hanya akan memilih kesetaraan, dan saya pikir saya harus menggunakan indeks hash atas indeks btree. Banyak yang mencemaskan saya, indeks hash tidak didukung di MyISAM atau InnoDB. Ada apa dengan itu?

Banyak basis data yang tidak mendukung indeks berbasis hash sama sekali .

Agar tabel hash menjadi efisien, Anda perlu mengetahui jumlah baris yang mungkin ada jika tidak, tabel hash dasar akan terlalu besar (banyak entri kosong, ruang kosong dan berpotensi disk IO) atau terlalu kecil artinya tipuan sering digunakan (mungkin beberapa tingkat tipuan, atau bahkan lebih buruk jika implementasi hash adalah tingkat tunggal Anda akhirnya dapat melakukan pencarian linier atas sejumlah catatan) di mana hal-hal yang mungkin tidak lebih efisien daripada berbasis pohon tetap indeks.

Jadi untuk menjadi berguna secara umum (yaitu biasanya lebih baik daripada alternatif) indeks perlu sesekali dibangun kembali ketika data tumbuh (dan menyusut) yang dapat menambah overhead yang intermiten yang signifikan. Ini biasanya baik-baik saja dengan tabel berbasis memori karena pembangunan kembali mungkin akan cukup cepat (karena data akan selalu berada dalam RAM dan tidak mungkin besar dalam hal apapun), tetapi membangun kembali indeks besar pada disk adalah operasi yang sangat berat (dan mySQL IIRC tidak mendukung pembangunan kembali indeks langsung sehingga memegang kunci tabel selama operasi).

Oleh karena itu indeks hash digunakan dalam tabel memori karena di sana mereka umumnya berkinerja lebih baik, tetapi tabel berbasis disk tidak mendukung mereka karena mereka dapat merusak kinerja bukan bonus. Tidak ada yang menghentikan indeks hash yang tersedia untuk tabel berbasis disk tentu saja, tidak diragukan lagi beberapa database memang mendukung fitur tersebut, tetapi mungkin mereka tidak diimplementasikan dalam tabel ISAM / InnoDB karena pengelola tidak mempertimbangkan fitur yang layak ditambahkan (karena kode tambahan untuk ditulis dan dipelihara tidak sebanding dengan manfaatnya dalam beberapa keadaan yang membuat perbedaan signifikan). Mungkin jika Anda sangat tidak setuju Anda dapat berbicara dengan mereka dan membuat alasan yang baik untuk penerapan fitur ini.

Jika Anda mengindeks string besar maka menerapkan pseudo-hash index Anda sendiri (dengan menyimpan hash nilai serta nilai aktual, dan pengindeksan yang memiliki kolom) dapat bekerja, tetapi ini hanya pasti lebih efisien untuk string besar (di mana menghitung nilai hash dan mencari indeks pohon dengan nilai ini selalu cenderung lebih cepat daripada hanya mencari indeks pohon menggunakan nilai yang lebih besar untuk perbandingan, dan penyimpanan tambahan yang digunakan tidak akan menjadi signifikan) jadi lakukan beberapa analisis kinerja sebelum menerapkan ini dalam produksi.

Pada catatan terkait, Anda mungkin menemukan diskusi tentang tipe indeks dari dokumen PostgreSQL menarik. Ini tidak lagi hadir dalam versi terbaru dari dokumen (karena optimasi berikutnya, saya ambil), tetapi takeaway mungkin mirip untuk MySQL (dan alasan mengapa indeks hash hanya digunakan untuk heap tables):

http://www.postgresql.org/docs/8.1/static/indexes-types.html

Catatan: Pengujian menunjukkan indeks hash PostgreSQL berkinerja tidak lebih baik daripada indeks B-tree, dan ukuran indeks serta waktu pembuatan untuk indeks hash jauh lebih buruk. Selain itu, operasi indeks hash saat ini tidak dicatat dalam WAL, jadi indeks hash mungkin perlu dibangun kembali dengan REINDEX setelah terjadi kerusakan basis data. Untuk alasan ini, penggunaan indeks hash saat ini tidak disarankan. Demikian pula, indeks R-tree tampaknya tidak memiliki keunggulan kinerja dibandingkan dengan operasi setara indeks GiST. Seperti indeks hash, mereka bukan WAL-login dan mungkin perlu mengindeks ulang setelah database crash. Sementara masalah dengan indeks hash mungkin diperbaiki pada akhirnya, ada kemungkinan bahwa tipe indeks R-tree akan dihentikan pada rilis mendatang. Pengguna didorong untuk memigrasi aplikasi yang menggunakan indeks R-tree ke indeks GiST.

Sekali lagi, itu (versi usang) PostgreSQL-spesifik, tetapi harus mengisyaratkan bahwa tipe indeks "alami" tidak akan selalu menghasilkan kinerja yang optimal.

Ini sesuatu yang menarik:

Menurut buku Panduan Studi Sertifikasi MySQL 5.0 , Halaman 433, Bagian 29.5.1

Mesin MEMORY menggunakan HASH dengan algoritma pengindeksan default.

Untuk tertawa, saya mencoba membuat tabel InnoDB dan tabel MyISAM dengan kunci utama menggunakan HASH di MySQL 5.5.12

mysql> use test
Database changed
mysql> create table rolando (num int not null, primary key (num) using hash);
Query OK, 0 rows affected (0.11 sec)

mysql> show create table rolando\G
*************************** 1. row ***************************
       Table: rolando
Create Table: CREATE TABLE `rolando` (
  `num` int(11) NOT NULL,
  PRIMARY KEY (`num`) USING HASH
) ENGINE=InnoDB DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

mysql> create table rolando2 (num int not null, primary key (num) using hash) engine=MyISAM;
Query OK, 0 rows affected (0.05 sec)

mysql> show create table rolando2\G
*************************** 1. row ***************************
       Table: rolando2
Create Table: CREATE TABLE `rolando2` (
  `num` int(11) NOT NULL,
  PRIMARY KEY (`num`) USING HASH
) ENGINE=MyISAM DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

MySQL tidak mengeluh.

MEMPERBARUI

Kabar buruk !!! Saya menggunakan TAMPILKAN INDEKS DARI. Dikatakan indeks adalah BTREE.

The CREATE INDEX sintaks MySQL Halaman menyatakan bahwa hanya MEMORY dan mesin penyimpanan NDB dapat mengakomodasi INDEX Hash.

mysql> show indexes from rolando;
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table   | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| rolando |          0 | PRIMARY  |            1 | num         | A         |           0 |     NULL | NULL   |      | BTREE      |         |               |
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set (0.00 sec)

mysql> show indexes from rolando2;
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table    | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| rolando2 |          0 | PRIMARY  |            1 | num         | A         |           0 |     NULL | NULL   |      | BTREE      |         |               |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set (0.00 sec)

mysql> create table rolando3 (num int not null, primary key (num)) ENGINE=MEMORY;
Query OK, 0 rows affected (0.03 sec)

mysql> show create table rolando3\G
*************************** 1. row ***************************
       Table: rolando3
Create Table: CREATE TABLE `rolando3` (
  `num` int(11) NOT NULL,
  PRIMARY KEY (`num`)
) ENGINE=MEMORY DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

mysql> show indexes from rolando3;
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table    | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| rolando3 |          0 | PRIMARY  |            1 | num         | NULL      |           0 |     NULL | NULL   |      | HASH       |         |               |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set (0.00 sec)

Beberapa orang menyarankan mengikuti gagasan di Halaman 102-105 dari buku " MySQL Kinerja Tinggi: Optimasi, Cadangan, Replikasi, dan Lainnya " untuk meniru algoritma hash.

Page 105 menampilkan algoritme cepat-dan-kotor ini yang saya sukai:

SELECT CONV(RIGHT(MD5('whatever value you want'),16),16,10) AS HASH64;

Buat kolom untuk ini di tabel apa saja dan indeks nilai ini.

Cobalah !!!

BTree tidak lebih lambat dari Hash untuk pencarian baris tunggal. Karena BTree menyediakan rentang pertanyaan yang sangat efisien, mengapa repot dengan selain BTree.

MySQL melakukan pekerjaan caching blok BTree dengan sangat baik, sehingga kueri berbasis BTree jarang harus melakukan I / O, yang merupakan konsumen waktu terbesar dalam kueri apa pun.