Apa perbedaan antara pengindeksan btree dan rtree?

36

Saya perhatikan di MySQLWorkbench bahwa Anda dapat memilih cara menyimpan indeks Anda sebelum meneruskan desain Anda. Jenis penyimpanannya adalah:

  1. BTREE
  2. RTREE
  3. HASH

Meneliti ini, saya menemukan beberapa informasi yang cukup banyak di kepala saya, jadi saya mencari informasi praktis tentang apa perbedaan antara ini dan / atau mengapa Anda harus memilih satu di antara yang lain.

Juga, saya belum pernah memilih jenis penyimpanan sebelumnya, jadi saya berasumsi MySQL memilih jenis penyimpanan default (BTREE?)


sumber

Jawaban:

51

BTree

BTree (sebenarnya B * Tree) adalah peta nilai kunci yang diurutkan secara efisien. Berarti:

  • diberikan kunci, indeks BTree dapat dengan cepat menemukan catatan,
  • sebuah BTree dapat dipindai secara berurutan.
  • juga mudah untuk mengambil semua kunci (dan catatan) dalam suatu rentang.

mis. "semua acara antara jam 9 pagi dan jam 5 sore", "nama belakang dimulai dengan 'R'"

RTree

RTree adalah spatial indexyang artinya dapat dengan cepat mengidentifikasi closenilai dalam 2 atau lebih dimensi. Ini digunakan dalam basis data geografis untuk kueri seperti:

semua titik dalam jarak X meter dari (x, y)

Hash

Hash adalah peta nilai kunci yang tidak berurutan. Ini bahkan lebih efisien daripada BTree: O(1)bukan O(log n).

Tetapi tidak memiliki konsep pesanan sehingga tidak dapat digunakan untuk operasi sortir atau untuk mengambil rentang.

Sebagai catatan, awalnya, MySQL hanya mengizinkan indeks Hash di atas MEMORYmeja; tapi saya tidak yakin apakah itu telah berubah selama bertahun-tahun.

Javier
sumber
Apakah MySQL mendukung Rtrees?
Pacerier
2
ya, mereka disebut SPATIAL INDEX ( dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html )
Javier
Keren, terima kasih =) Apakah ada struktur lain selain 3 ini, atau struktur yang direncanakan dalam waktu dekat?
Pacerier
Tabel memori juga mendukung indeks btree
Amareswar
@ Amareswar, benar. Mungkin jawaban saya dapat dibaca dua arah, tetapi yang saya maksudkan adalah bahwa indeks HASH hanya diperbolehkan pada tabel MEMORY, bukan pada tabel 'normal'.
Javier