¿Cuál es la diferencia entre btree e rtree indexing?

36

He notado en MySQLWorkbench que puedes elegir cómo almacenar tus índices antes de avanzar la ingeniería de tu diseño. Los tipos de almacenamiento son:

  1. BTREE
  2. RTREE
  3. PICADILLO

Investigando esto, encontré información que estaba muy por encima de mi cabeza, así que estoy buscando información práctica sobre cuál es la diferencia entre estos y / o por qué debería elegir uno sobre otro.

Además, nunca he elegido un tipo de almacenamiento antes, así que supongo que MySQL está eligiendo un tipo de almacenamiento predeterminado (¿BTREE?)


fuente

Respuestas:

51

BTree

BTree (de hecho B * Tree) es un mapa ordenado clave-valor eficiente. Sentido:

  • dada la clave, un índice BTree puede encontrar rápidamente un registro,
  • Se puede escanear un BTree en orden.
  • También es fácil obtener todas las claves (y registros) dentro de un rango.

por ejemplo, "todos los eventos entre las 9am y las 5pm", "apellidos que comienzan con 'R'"

RTree

RTree es lo spatial indexque significa que puede identificar rápidamente closevalores en 2 o más dimensiones. Se utiliza en bases de datos geográficas para consultas como:

todos los puntos dentro de X metros de (x, y)

Picadillo

Hash es un mapa clave-valor desordenado. Es incluso más eficiente que un BTree: en O(1)lugar de O(log n).

Pero no tiene ningún concepto de orden, por lo que no se puede usar para operaciones de clasificación o para buscar rangos.

Como nota al margen, originalmente, MySQL solo permitía índices Hash en las MEMORYtablas; pero no estoy seguro si eso ha cambiado con los años.

Javier
fuente
¿MySQL es compatible con Rtrees?
Pacerier
2
sí, se llaman ÍNDICE ESPACIAL ( dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html )
Javier
Genial, gracias =) ¿Hay otras estructuras además de estas 3, o estructuras planificadas en el futuro cercano?
Pacerier
Las tablas de memoria también son compatibles con los índices btree
Amareswar
@Amareswar, cierto. Tal vez mi respuesta se pueda leer en ambos sentidos, pero lo que quise decir es que los índices HASH solo se permitían en las tablas de MEMORIA, no en las tablas 'normales'.
Javier