bTree vs HashTable

Question

Dans MySQL, un type d’index est BTree et l'accès à un élément d'un arbre est en temps amorti logarithmique.

L'accès à un élément dans une table de hachage se fait en O (1).

Pourquoi une table de hachage n'est pas utilisée pour accéder aux données de la base de données?

Answer 1

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)) vous ne pouvez pas sélectionner des plages (tout ce qui est entre x et y). arbre algorithmes prennent en charge ce en Log(n), comme un 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 le facteur theta notation, mais elle existe toujours). aussi arbre algorithmes sont généralement plus faciles à maintenir, développer avec les données, échelle, etc.

hash index travailler avec pré-définies de hachage de taille. donc, vous vous retrouvez 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.

aujourd'hui les tables de hachage algorithmes généralement mis à l'échelle. mais 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 de hachage n'est pas facile. son appelé RUSH - réplication ander évolutive de hachage, 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 construire. 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.

le compromis 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.

Answer 2

Parce qu’un arbre peut être facilement paginé sur le disque. De plus, 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, vous devez la modifier de temps en temps pour obtenir des performances optimales avec une table de hachage. La rechapage est également chère.

Answer 3

Je pense que les cartes de hachage ne s'adaptent pas aussi bien et peuvent coûter cher lorsque l'ensemble de la carte doit être réorganisé.