Tabla B-Tree vs Hash

102

En MySQL, un tipo de índice es un árbol b, y el acceso a un elemento en un árbol b está en tiempo logarítmico amortizado O(log(n)).

Por otro lado, acceder a un elemento en una tabla hash está en O(1).

¿Por qué no se usa una tabla hash en lugar de un árbol b para acceder a los datos dentro de una base de datos?

JohnJohnGa
fuente
9
Hash tablas para no admitir consultas de rango y no pueden crecer o reducirse sin problemas durante la operación.
hmakholm dejó a Monica el
3
@HenningMakholm ¿Por qué no utilizar hash para las columnas que no necesitan consultas de rango?
Pacerier

Respuestas:

114

Solo puede acceder a los elementos por su clave principal en una tabla hash. Esto es más rápido que con un algoritmo de árbol (en O(1)lugar delog(n) ), pero no puede seleccionar rangos ( todo entre xyy ). Los algoritmos de árbol admiten esto Log(n)mientras que los índices hash pueden dar como resultado un escaneo completo de la tabla O(n). Además, la sobrecarga constante de los índices hash suele ser mayor (lo que no es un factor en la notación theta, pero aún existe ). Además, los algoritmos de árbol suelen ser más fáciles de mantener, crecer con datos, escalar, etc.

Los índices hash funcionan con tamaños hash predefinidos, por lo que terminas con algunos "cubos" donde se almacenan los objetos. Estos objetos se repiten de nuevo para encontrar realmente el correcto dentro de esta partición.

Entonces, si tiene tamaños pequeños, tiene mucha sobrecarga para elementos pequeños, los tamaños grandes dan como resultado un mayor escaneo.

Los algoritmos de tablas hash de hoy en día generalmente escalan, pero el escalado puede ser ineficiente.

De hecho, existen algoritmos de hash escalables. No me preguntes cómo funciona, también es un misterio para mí. AFAIK, evolucionaron a partir de una replicación escalable donde volver a aplicar hash no es fácil.

Su llamado Rush - R eplication U nder S calable H incineración, y esos algoritmos son así llamados algoritmos Rush.

Sin embargo, puede haber un punto en el que su índice supere un tamaño tolerable en comparación con sus tamaños de hash y su índice completo deba reconstruirse. Por lo general, esto no es un problema, pero para bases de datos enormes, esto puede llevar días.

La compensación por los algoritmos de árbol es pequeña y son adecuados para casi todos los casos de uso y, por lo tanto, son predeterminados.

Sin embargo, si tiene un caso de uso muy preciso y sabe exactamente qué y solo qué se va a necesitar, puede aprovechar los índices hash.

El surrican
fuente
¿Puede explicar más sobre la reconstrucción del índice? ¿Significa que durante x días mientras el índice se reconstruye, la tabla no estará disponible para su uso durante ese período?
Pacerier
eso depende del sistema de base de datos en uso. la pregunta solo cubría los aspectos teóricos. Realmente no conozco los detalles de implementación de los sistemas de bases de datos comunes. pero, por lo general, este no debería ser el caso porque el segundo índice se puede construir mientras el primero todavía se está usando
The Surrican
"Solo puede acceder a los elementos por su clave principal", ¿quiere decir por el valor de la columna que tiene el índice correcto, ya sea una clave principal u otro tipo de índice?
Mark Fisher
90

En realidad, parece que MySQL usa ambos tipos de índices, ya sea una tabla hash o un árbol b de acuerdo con el siguiente enlace .

La diferencia entre usar un árbol b y una tabla hash es que el primero le permite usar comparaciones de columnas en expresiones que usan los operadores =,>,> =, <, <= o BETWEEN, mientras que el segundo se usa solo para comparaciones de igualdad que utilizan los operadores = o <=>.

lmiguelvargasf
fuente
9
Eso no es justo. La mejor respuesta tiene la puntuación más baja.
Андрей Беньковский
6
Esto es exactamente lo que estaba buscando. Me preocupé más por cómo afecta a mis consultas que por un análisis técnico.
Ben Dehghan
¡Sí! Esta respuesta me ayudó más.
Ron Ross
muchas gracias, ha pasado mucho tiempo pero esta respuesta me ayudó mucho también.
Reham Fahmy
14

La complejidad temporal de las tablas hash es constante solo para tablas hash de tamaño suficiente (es necesario que haya suficientes depósitos para contener los datos). El tamaño de una tabla de la base de datos no se conoce de antemano, por lo que la tabla debe repetirse de vez en cuando para obtener un rendimiento óptimo de una tabla hash. El refrito también es caro.

Emil Vikström
fuente
2
¿Se puede realizar el cambio de hash mientras db está en línea? ¿O tenemos que cerrar la mesa para repetir todo?
Pacerier
1
Pacerier, MySQL no tiene soporte para índices hash. En teoría, es posible repetir el índice mientras la base de datos todavía está en línea (seguir usando el índice anterior, crear un índice nuevo, cambiar al nuevo cuando esté hecho) pero no sé qué haría MySQL si implementaran indicios hash.
Emil Vikström
3
MySQL admite índices hash, ¿verdad? : Dev.mysql.com/doc/refman/5.5/en/index-btree-hash.html
Pacerier
Pareces tener razón. ¡Eso fue una novedad para mí! Debo tratar de mantenerme al día con el desarrollo :-) Entonces, estás mucho mejor respondiendo tu pregunta que yo, pero como dije: es teóricamente posible.
Emil Vikström
Por cierto, ¿por qué dice que "un árbol b puede paginarse fácilmente en el disco pero una tabla hash no"? ¿No podría almacenarse una tabla hash en el disco, ya que una simple búsqueda de claves sería suficiente?
Pacerier
6

Creo que los Hashmaps no se escalan tan bien y pueden ser costosos cuando es necesario modificar todo el mapa.

Jonathan Weatherhead
fuente
0

Pick DB / OS se basó en hash y funcionó bien. Con más memoria en estos días para admitir tablas hash dispersas eficientes y hash redundante para admitir consultas de rango modesto, diría que el hash aún puede tener su lugar (algunos preferirían tener otras formas de coincidencia de similitudes sin rango, como comodines y expresiones regulares) ). También recomendamos copiar para mantener las cadenas de colisión contiguas cuando las jerarquías de memoria tienen grandes diferencias de velocidad.

RONALD LOUI
fuente