Complexité du temps de requête
Je suis assez nouveau à des bases de données, donc pardonnez-moi si c'est une question stupide.
Dans des bases de données modernes, si j'utilise un index pour accéder à une ligne, je crois que ça va être O(1) de la complexité. Mais si je fais une requête pour sélectionner une autre colonne, qu'il sera O(1) O(n)? La base de données ont pour itérer sur toutes les lignes, ou faut-il établir une liste pour chaque colonne?
source d'informationauteur Zifre | 2009-04-07
Vous devez vous connecter pour publier un commentaire.
En fait, je pense que l'accès basé sur un indice de O(log(n)), parce que vous aurez toujours être à la recherche vers le bas par l'intermédiaire d'un B-Arbre-esque de l'organisation pour obtenir de votre dossier.
Pour répondre à votre question littérale, oui si il n'y a pas d'index sur une colonne, le moteur de base de données devra examiner toutes les lignes.
Dans les cas intéressant de sélectionner plusieurs colonnes, à la fois avec et sans index, la situation devient plus complexe: Si l'Optimiseur de Requête choisit d'utiliser l'index, puis il va d'abord sélectionner des lignes en fonction de l'index, puis appliquer un filtre avec les contraintes restantes. Ainsi, la réduction de la deuxième opération de filtrage de O(nombre de lignes) à O(nombre de lignes sélectionnées par indice). Le rapport entre ces deux nombre est appelé sélectivité et une statistique importante lors du choix de l'indice à utiliser.
Indices sont par colonne, donc si vous utilisez une clause where sur les nations unies-colonne indexée, il va faire une sorte de tablescan qui est O(n).
Je ne connais pas la réponse, mais gardez à l'esprit que le big-O notation ne vous donne qu'une indication de la performance pour l'ensemble de données de tailles qui sont arbitrairement grand.
Par exemple, le goulot d'étranglement pour les performances de base de données est généralement disque cherche. Par conséquent, la performance est grandement accrue si le travail d'un jeu de données peut être stocké en mémoire. Big-O notation ne vous dirai rien à propos de ces optimisations, parce qu'ils ne sont pertinentes que pour les finis les jeux de données.
B-arbres ne produisent pas de O(logN), c'est la complexité d'un arbre binaire.
Un B-Arbre est organisée de manière telle qu'il a un bloc entier par nœud, donc, une fois qu'un nœud est trouvé une seule opération d'e/S peut lire la totalité d'un îlot.
Avec le nombre d'éléments par nœud = facteur de blocage (#dossiers/bloquer){bfr}, un B-Arbre de recherche optimisé donnera O(log bfr÷2 +1 N) opérations d'e/S au lieu de O(N) opérations d'e/S la recherche d'un enregistrement par clé.
Vous avez des indices. Les index en cluster sont physiquement triés sur le disque, vous ne pouvez avoir qu'un par table. Les index non-cluster sont logiquement triés et vous pouvez avoir beaucoup de ceux (attention à ne pas en abuser non plus, il risque de ralentir les actions d'écriture).
Si il n'y a pas d'index sur la colonne puis je crois que c'est la bonne vieille ligne par ligne méthode.
Il existe différents types d'index, les différents plans d'exécution et les différentes implémentations de différentes bases de données. La plupart du code des relations de la base de données est à la recherche d'optimisation et algorithmes. Il n'y a pas une seule réponse à votre question. Vous pouvez utiliser un outil pour visualiser le plan d'exécution lorsque vous voulez savoir comment faire une requête va être exécuté.