Tabla B-Tree vs Hash

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?

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.

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 <=>.

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.

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

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.