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