index - mysql btree vs hash
Tabla B-Tree vs Hash (4)
Creo que los Hashmaps no se escalan también, y pueden ser costosos cuando se debe volver a generar el mapa completo.
En MySQL, un tipo de índice es un b-tree, y el acceso a un elemento en un b-tree 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 utiliza una tabla hash en lugar de b-tree para acceder a los datos dentro de una base de datos?
En realidad, parece que MySQL usa ambos tipos de índices, ya sea una tabla hash o un b-tree, de acuerdo con el siguiente link .
La diferencia entre usar un b-tree 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 último se usa solo para comparaciones de igualdad que usan los operadores = o <=>.
La complejidad temporal de las tablas hash es constante solo para las tablas hash de tamaño suficiente (debe haber suficientes cubos para contener los datos). El tamaño de una tabla de base de datos no se conoce de antemano, por lo que la tabla debe actualizarse de vez en cuando para obtener un rendimiento óptimo de una tabla hash. El reacondicionamiento también es costoso.
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 ( O(1) lugar de log(n) ), pero no puede seleccionar rangos ( todo entre y ). Los algoritmos de árbol soportan esto en Log(n) donde como un índice de hash puede resultar en un escaneo completo de tabla O(n) . Además, la sobrecarga constante de los índices hash suele ser más grande (lo cual no es un factor en la notación theta, pero todavía 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 de hash predefinidos, por lo que terminas con algunos "depósitos" en los que se almacenan los objetos. Estos objetos se vuelven a enlazar 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 escaneo adicional.
Los algoritmos de las tablas hash de hoy en día suelen escalar, pero escalar puede ser ineficiente.
De hecho, hay algoritmos de hashing escalables. No me preguntes cómo funciona eso, es un misterio para mí también. AFAIK evolucionaron a partir de la replicación escalable donde no es fácil volver a mezclar.
Se llama RUSH - R eplication U nder S Hilable H , y esos algoritmos se denominan algoritmos RUSH.
Sin embargo, puede haber un punto en el que su índice exceda un tamaño tolerable en comparación con sus tamaños de hash y todo su índice debe reconstruirse. Por lo general, esto no es un problema, pero para bases de datos enormes, enormes, esto puede llevar días.
Los algoritmos de compensación de árbol son pequeños 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 qué va a necesitar, puede aprovechar los índices de hash.