B-Árbol vs Tabla Hash
En MySQL, un tipo de índice es un árbol b, y access 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 utiliza una tabla hash en lugar de un árbol b para acceder a los datos dentro de una base de datos?
4 answers
Solo se puede acceder a los elementos por su clave primaria en una tabla hash.
Esto es más rápido que con un algoritmo de árbol(O(1) en lugar de log(n)), pero no puede seleccionar rangos ( todo lo que está entre x y y).
Los algoritmos de árbol soportan esto en Log(n) mientras que los índices hash pueden resultar en un escaneo completo de la tabla O(n).
También la sobrecarga constante de los índices hash suele ser mayor ( que no es un factor en la notación theta, pero todavía existe).
También los algoritmos de árbol son generalmente más fácil de mantener, crecer con datos, escalar, etc.
Los índices Hash funcionan con tamaños hash predefinidos, por lo que termina con algunos "cubos" donde se almacenan los objetos. Estos objetos se repiten para encontrar realmente el correcto dentro de esta partición.
Así que si tiene tamaños pequeños, tiene una gran cantidad de sobrecarga para elementos pequeños, los tamaños grandes dan como resultado un escaneo adicional.
Los algoritmos actuales de las tablas hash generalmente escalan, pero el escalado puede ser ineficiente.
Existen algoritmos de hash escalables. No me preguntes cómo funciona - es un misterio para mí también. AFAIK evolucionaron de la replicación escalable donde el re-hash no es fácil.
Su llamado RUSH - Replication Ucon Scalable Hparpadeando, y los algoritmos son así llamado punta de los algoritmos.
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 su totalidad el índice necesita ser reconstruido. Por lo general, esto no es un problema, pero para bases de datos enormes-enormes-enormes, esto puede tomar 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é va a ser necesario, puede aprovechar los índices de hash.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-09-03 05:59:35
En realidad, parece que MySQL utiliza 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 la primera le permite usar comparaciones de columnas en expresiones que usan el =, >, >=, solo para comparaciones de igualdad que usan los operadores = o.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-11-11 08:21:14
La complejidad temporal de los hashtables es constante solo para los hashtables de tamaño suficiente (es necesario que haya 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 ser revisada de vez en cuando para obtener un rendimiento óptimo de una tabla hash. El refrito también es caro.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-03-06 02:39:35
Creo que los Hashmaps no escalan tan bien, y pueden ser costosos cuando todo el mapa necesita ser rehasheado.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-09-05 09:48:53