B-Tree vs table de hachage

Dans MySQL, un type d'index est un b-tree et l'accès à un élément d'un b-tree est en temps amorti logarithmique O(log(n)).

D'un autre côté, l'accès à un élément dans une table de hachage se fait O(1).

Pourquoi une table de hachage n'est-elle pas utilisée à la place d'un b-tree pour accéder aux données d'une base de données?

Vous ne pouvez accéder aux éléments que par leur clé primaire dans une table de hachage. C'est plus rapide qu'avec un algorithme d'arborescence ( O(1)au lieu delog(n) ), mais vous ne pouvez pas sélectionner de plages ( tout entre xety ). Les algorithmes d'arborescence prennent en charge cela Log(n)alors que les index de hachage peuvent entraîner une analyse complète de la table O(n). De plus, la surcharge constante des index de hachage est généralement plus importante ( ce qui n'est pas un facteur en notation thêta, mais elle existe toujours ). De plus, les algorithmes d'arbre sont généralement plus faciles à maintenir, à se développer avec les données, à l'échelle, etc.

Les index de hachage fonctionnent avec des tailles de hachage prédéfinies, vous vous retrouvez donc avec des «compartiments» dans lesquels les objets sont stockés. Ces objets sont à nouveau bouclés pour trouver vraiment le bon dans cette partition.

Donc, si vous avez de petites tailles, vous avez beaucoup de frais généraux pour les petits éléments, les grandes tailles entraînent une numérisation plus poussée.

Les algorithmes actuels des tables de hachage sont généralement mis à l'échelle, mais la mise à l'échelle peut être inefficace.

Il existe en effet des algorithmes de hachage évolutifs. Ne me demandez pas comment cela fonctionne - c'est un mystère pour moi aussi. AFAIK ils ont évolué à partir de la réplication évolutive où le re-hachage n'est pas facile.

Il s'appelle RUSH - R eplication U nder S calable H ashing , et ces algorithmes sont donc appelés algorithmes RUSH.

Cependant, il peut y avoir un point où votre index dépasse une taille tolérable par rapport à vos tailles de hachage et votre index entier doit être recréé. Ce n'est généralement pas un problème, mais pour des bases de données énormes, énormes, cela peut prendre des jours.

Le compromis pour les algorithmes d'arbre est petit et ils conviennent à presque tous les cas d'utilisation et sont donc par défaut.

Cependant, si vous avez un cas d'utilisation très précis et que vous savez exactement de quoi et seulement ce qui sera nécessaire, vous pouvez profiter des index de hachage.

En fait, il semble que MySQL utilise les deux types d'index soit une table de hachage ou un b-tree selon le lien suivant .

La différence entre l'utilisation d'un b-tree et d'une table de hachage est que le premier vous permet d'utiliser des comparaisons de colonnes dans les expressions qui utilisent les opérateurs =,>,> =, <, <= ou BETWEEN, tandis que le second n'est utilisé que pour comparaisons d'égalité qui utilisent les opérateurs = ou <=>.

La complexité temporelle des tables de hachage n'est constante que pour des tables de hachage de taille suffisante (il doit y avoir suffisamment de compartiments pour contenir les données). La taille d'une table de base de données n'étant pas connue à l'avance, la table doit être remaniée de temps en temps pour obtenir des performances optimales d'une table de hachage. Le ressassement est également coûteux.

Je pense que les Hashmaps ne sont pas également mis à l'échelle et peuvent être coûteux lorsque la carte entière doit être remaniée.

Pick DB / OS était basé sur le hachage et fonctionnait bien. Avec plus de mémoire ces jours-ci pour prendre en charge des tables de hachage clairsemées efficaces et un hachage redondant pour prendre en charge des requêtes à plage modeste, je dirais que le hachage peut encore avoir sa place (certains préféreraient avoir d'autres formes de correspondance de similitude sans plage, telles que les caractères génériques et les expressions rationnelles) ). Nous recommandons également la copie pour garder les chaînes de collision contiguës lorsque les hiérarchies de mémoire présentent de grandes différences de vitesse.