Las tablas hash parecen ser preferibles en términos de acceso al disco. ¿Cuál es la verdadera razón por la que los índices generalmente se implementan con un árbol? Lo siento si es infantil, pero no encontré la respuesta correcta en SO.¿Por qué los índices DB usan árboles balanceados, no hashtables?
Tamaño, btrees comienzan pequeño y perfectamente formado y crecen muy bien a enormes tamaños. Los valores hash tienen un tamaño fijo que puede ser demasiado grande (10.000 cubos para 1000 entradas) o demasiado pequeño (10.000 cubos para 1,000,000,000 de entradas) para la cantidad de datos que tiene.
Untrue. Hay algoritmos hash extensibles. – EJP
@EJP Pero en la práctica es cierto, en promedio, que hay espacio desperdiciado, incluso para algoritmos de hashing extensibles. Un dict python consume un 50% más de cubetas que las requeridas (factor de carga del 75%). ¿Y pueden imaginarse las grabaciones de disco necesarias para implementar la parte "extensible" de tablas hash extensibles? De repente, llegas al límite y tu base de datos tiene que copiar y volver a generar toda la tabla. Y cualquier tabla para apuntar a PK en esa tabla, etc. Así que un único INSERT podría (inesperadamente) poner su DB fuera de línea durante un tiempo doloroso. Eso hace que la parte "extensible" sea poco práctica. – hobs
La memoria es definitivamente un factor cuando se usan hashtables. Pero, ¿qué pasa con el aumento de rendimiento que se obtendrá si se usa hashtable? Una operación de inserción en hashtable tiene complejidad de tiempo constante. Mientras que el árbol equilibrado debe reajustarse después de cada operación de inserción. – sajid
Una de las acciones más comunes con los datos es ordenarlos o buscar datos en un rango: un árbol contendrá los datos en orden mientras que una tabla hash solo es útil para buscar una fila y no tiene idea de qué La siguiente fila es
tablas Así de hash no son buenos para este caso común, gracias a este answer
SELECT * FROM MyTable WHERE Val BETWEEN 10000 AND 12000
o
SELECT * FROM MyTable ORDER BY x
Es obvio que hay casos en los que las tablas hash son mejores, pero la mejor manera de tratar los principales casos primero.
Hasing es bueno cuando los datos no está aumentando, más techically cuando N/n es constante .. donde N = No de elementos y n = ranuras de hash ..
Si este no es el imposible de hashing caso dar un buen aumento de rendimiento.
En la base de datos, lo más probable es que los datos aumenten a un ritmo significativo, por lo que usar hash no es una buena idea.
clasificación y sí está allí también ...
Esto no es cierto. Hay algoritmos hash extensibles, con buen rendimiento. – EJP
"En la base de datos con toda probabilidad los datos estaría aumentando un ritmo significativo lo que el uso de hash no es una buena idea."
Eso es una exageración exagerada del problema. Sí, los espacios hash deben tener un tamaño fijo (soluciones modulo a hashing extensible) y sí, su tamaño debe ser administrado, y sí, alguien debe hacer ese trabajo.
Dicho esto, el rendimiento aumenta si explotas la ubicación física basada en hash en todo su potencial, son enormes.
Las bases de datos normalmente usan árboles B + (un tipo específico de árbol), ya que tienen mejores propiedades de acceso a disco - cada nodo puede tener el tamaño de un bloque de sistema de archivos. Hacer tan pocas lecturas de disco como sea posible tiene un mayor impacto en la velocidad, ya que se gasta relativamente poco tiempo en perseguir punteros en un árbol o hashing.
Las tablas hash proporcionar ningún beneficio para este caso:
SELECT * FROM MyTable WHERE Val BETWEEN 10000 AND 12000
Uno sólo tiene que mirar a MySQL's hash index implementation asociado con MEMORY motor de almacenamiento para ver sus desventajas:
= pero no con operadores de comparación como <Y tenga en cuenta que lo anterior se aplica a los índices de hash implementados en la memoria, sin la consideración adicional de asuntos de acceso a disco asociados con los índices implementados en el disco. Los factores de acceso al disco según lo observado por @silentbicycle lo inclinarían aún más en favor del índice de árbol equilibrado.
Porque también necesitan una propiedad secuencial. – EJP