Comment l'échelle de la requête de la base de données avec la taille de la base de données?

Question

J'étais récemment sur l'OEIS (encyclopédie en ligne des séquences entières) récemment, essayant de rechercher une séquence particulière que j'avais.

Maintenant, cette base de données est assez grande. Le site Web stipule que si l'édition 2006 (! 5 ans) était imprimée, elle occuperait 750 volumes de texte.

Je suis sûr que c'est le même type de problème que Google doit également gérer. Mais, ils ont également un système distribué où ils profitent de l'équilibrage de la charge.

Négliger l'équilibrage de la charge cependant, combien de temps faut-il pour faire une requête par rapport à la taille de la base de données?

Ou en d'autres termes, quelle est la complexité temporelle d'une requête en ce qui concerne la taille de la base de données?

EDIT: Pour rendre les choses plus spécifiques, supposons que la requête d'entrée consiste simplement à rechercher une chaîne de nombres tels que:

1, 4, 9, 16, 25, 36, 49

Answer 1

Cela dépend fortement de la requête, de la structure de la base de données, des affirmations, etc. Mais en général, la plupart des bases de données trouveront un moyen d'utiliser un index, et cet index sera soit une sorte de structure d'arbre (voir http://en.wikipedia.org/wiki/B-Tree pour une option) auquel cas le temps d'accès est proportionnel au journal (n), sinon un hachage, auquel cas le temps d'accès est proportionnel à o (1) en moyenne (voir http://en.wikipedia.org/wiki/hash_function#hash_tables pour une explication de leur fonctionnement).

La réponse est donc généralement O (1) ou O (log (n)) selon le type de structure de données utilisé.

Cela peut vous amener à vous demander pourquoi nous n'utilisons pas toujours les fonctions de hachage. Il y a plusieurs raisons. Les fonctions de hachage rendent difficile la récupération de plages de valeurs. Si la fonction de hachage ne distribue pas bien les données, il est possible d'accès à l'heure de devenir O (n). Les hachages ont besoin de redimensionnement de temps en temps, ce qui est potentiellement très cher. Et le journal (n) se développe suffisamment lentement pour que vous puissiez le traiter comme étant raisonnablement proche de constante dans tous les ensembles de données pratiques. (De 1000 à 1 pétaoctet, il varie d'un facteur de 5.) Et souvent les données activement demandées montrent une sorte de localité, que les arbres font un meilleur travail de maintien en RAM. En conséquence, les arbres sont un peu plus courants dans la pratique. (Bien que les hachages ne soient en aucun cas rares.)

Answer 2

Cela dépend d'un certain nombre de facteurs, notamment la mise en œuvre du moteur de la base de données, la stratégie d'indexation, les spécificités de la requête, le matériel disponible, la configuration de la base de données, etc.

Il n'y a aucun moyen de répondre à une telle question générale.

Answer 3

Une base de données correctement conçue et implémentée avec des téraoctets de données peut en fait surpasser une petite base de données mal conçue (particulière sans indexation et qui utilise des requêtes non sarcables et des choses comme des sous-questionnaires corrélées). C'est pourquoi quiconque s'attend à avoir de grandes quantités de données doit embaucher un expert en conception de données pour les grandes bases de données afin de faire la conception initiale pas plus tard lorsque la base de données est grande. Vous devrez peut-être également investir dans le type d'équipement dont vous avez besoin pour gérer la taille également.