B-Arbre vs Table de Hachage

Dans MySQL, un type d'index est un b-arbre, et accéder à un élément dans un b-arbre est en échelle logarithmique amorti temps O(log(n)).

D'autre part, l'accès à un élément dans une table de hachage est dans O(1).

Pourquoi une table de hachage pas utilisé au lieu d'un b-arbre afin d'accéder aux données à l'intérieur d'une base de données?

  • Les tables de hachage ne prennent pas en charge les requêtes d'intervalle, et ne peut pas augmenter ou de réduire en douceur pendant le fonctionnement.
  • Pourquoi ne pas hachage pour les colonnes qui n'ont pas besoin de la gamme des requêtes?
InformationsquelleAutor JohnJohnGa | 2011-09-05
  1. 87

    Vous pouvez uniquement accéder aux éléments par leur clé primaire dans une table de hachage.
    C'est plus rapide qu'avec un algorithme d'arbre (O(1) au lieu de log(n)), mais vous ne pouvez pas sélectionner des plages (tout entre x et y).
    Arbre algorithmes prennent en charge cette Log(n) alors que les index de hachage peut entraîner un full table scan O(n).
    Également les frais généraux constants de hash index est généralement plus gros (qui n'est pas facteur de thêta la notation, mais il existe encore).
    Aussi arbre algorithmes sont généralement plus faciles à maintenir, développer avec les données, échelle, etc.

    De hachage indices de travailler avec des pré-définis de hachage tailles, donc vous retrouver avec des "seaux", où les objets sont stockés dans. Ces objets sont en boucle sur nouveau pour vraiment trouver la bonne à l'intérieur de cette partition.

    Donc, si vous avez de petites tailles que vous avez beaucoup de frais généraux pour les petits éléments, grandes tailles davantage à la numérisation.

    D'aujourd'hui, les tables de hachage algorithmes généralement mis à l'échelle, mais de mise à l'échelle peut être inefficace.

    Il y a en effet évolutive algorithmes de hachage. Ne me demandez pas comment cela fonctionne - son un mystère pour moi aussi. Autant que je sache, ils ont évolué à partir évolutive de la réplication où re-hachage n'est pas facile.

    Son appelé RUSH - Rréplication Under Scalable Hde clignoter, et ces algorithmes sont donc appelés RUSH algorithmes.

    Cependant il peut y avoir un point où votre index dépasse tolérable taille par rapport à votre hash tailles et de votre index doit être re-construit. Ce n'est généralement pas un problème, mais pour l'énorme-énorme-énorme bases de données, cela peut prendre des jours.

    L'échange pour d'arbres algorithmes est de petite taille et ils sont adaptés pour presque tous les cas d'utilisation et sont donc par défaut.

    Toutefois, si vous avez un très précises de cas d'utilisation, et vous savez exactement ce qui, et seulement ce qui est nécessaire, vous pouvez profiter de hachage index.

    • Pouvez-vous expliquer plus sur la reconstruction d'un index? Ça veut dire que pour x jours, tandis que la reconstruction d'index, la table est totalement indisponible pour une utilisation au cours de cette période?
    • cela dépend du système de base de données en cours d'utilisation. la question ne couvrait que le théorique aspecsts. je ne sais pas vraiment sur les détails de mise en œuvre de la base de données commune des systèmes. mais généralement, cela ne devrait pas être le cas parce que la deuxième indice peut être construit, tandis que le premier est encore utilisé
    • "Vous ne pouvez accéder à des éléments par leur clé primaire" - tu veux dire par la valeur de la colonne de l'index droit, si c'est une clé primaire ou un autre type d'indice?
    InformationsquelleAutor The Surrican
  2. 57

    En fait, il semble que MySQL utilise à la fois le type d'index à une table de hachage ou d'un b-arbre suivant lien.

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

    • Que c'est injuste. La meilleure réponse a le score le plus bas.
    • C'est exactement ce que je cherchais. Je pris soin de comment elle affecte mes questions plutôt que d'une analyse technique.
    • Yep! Cette réponse m'a aidé le plus.
    • merci beaucoup, été long, mais cette réponse m'aide aussi beaucoup.
    InformationsquelleAutor lmiguelvargasf
  3. 13

    La complexité du temps de tables de hachage est constant que pour suffisamment de taille moyenne tables de hachage (il doit y avoir assez de seaux pour contenir les données). De la taille d'une table de base de données n'est pas connue à l'avance, de sorte que le tableau doit être rabâchage maintenant et puis pour obtenir des performances optimales d'une table de hachage. La redéfinition de est également coûteux.

    • Peut reshashing être effectué pendant que la db est en ligne? Ou avons-nous besoin de verrouiller la table à ressasser tout?
    • Pacerier, MySQL ont pas de support pour le hachage des indices. Il est théoriquement possible de ressasser les index pendant que la base de données est toujours en ligne (gardez à l'aide de l'ancien indice, créer un nouvel index, de passer à la nouvelle quand c'est fait) mais je ne sais pas ce que MySQL feraient s'ils en œuvre de hachage indicies.
    • MySQL supporte hash index droit? : dev.mysql.com/doc/refman/5.5/en/index-btree-hash.html
    • Vous semblent correctes. Qui a des nouvelles de moi! Je dois essayer de garder en place avec le développement de l' 🙂 Alors vous êtes beaucoup mieux pour répondre à votre question que je suis, mais comme je l'ai dit: c'est théoriquement possible.
    • Ok, merci pour les conseils =)
    • Btw, pourquoi dites-vous que "un arbre peut être facilement transférées sur le disque, mais une table de hachage ne peut pas"? Ne pouvait pas une table de hachage être stockées dans le disque depuis une simple clé de recherche suffirait?
    • Vous êtes de droite. Ma réponse est en fait mal. Si j'ai répondu à cette question aujourd'hui, je dirais quelque chose comme dans cette réponse pour MongoDB, où je motiver pourquoi un b-arbre a effectivement O(1) recherche dans la pratique.

    InformationsquelleAutor Emil Vikström
  4. 5

    Je pense que Hashmaps n'évoluent pas aussi bien, et peut être coûteux lors de l'ensemble de la carte doit être rabâchage.

    InformationsquelleAutor Jonathan Weatherhead