[IDEE] Mots clés + recherche 3 lettres

AdministrateurNiveau 50 · OscariséRéférenceur Légendaire

Membre depuis: 2002
Messages: 17438

Plus

Membre n°: 1
Inscription: 22 Feb 2002
Localisation: La Défense
Âge: 49 ans
Sujets lancés: 3040
Ancienneté: 100 %
Participation: 100 %
Temps en ligne: 104 Jours, 13 Heures, 5 Minutes, 37 Secondes en ligne

23-01-2004 22:26

Message écrit par Zakath, le 23-01-2004 à 22:15

Effectivement...

Mais je suppose que les données sont sous forme arborescente, donc avec une base de donnée bien indexée, la recherche se fait en un temps logarithmique, non ?

Donc, doubler la taille de la base reviendrait à augmenter de ln2 le temps de recherche, donc l'usage CPU.

Erreur, mais où ?

Alors là tu me poses une colle... je ne sais pas comment est implémentée une table MyISAM physiquement sur le disque.... de toute façon, la représentation optimale est loin d'être évidente parce que même si la table est ultra simple: "1 ID bidon, 1 wordID, 1 postID" par entrée, c'est évidemment l'ID bidon qui sert de clé primaire... et cette clé primaire est vraiment bidon (c'est un compteur auto-incrémenté au même titre que les numéros de posts du forum) et par conséquent il n'y a aucune logique dans les associations... (enfin je veux dire pour localiser rapidement les entrées à prendre)

Pour être optimal, il faudrait que soit les WordID qui soient physiquement classés par ordre numérique, et que la recherche se cantone donc à trouver les bornes inférieures et supérieures de ces WordID (là effectivement c'est en temps log(n)), mais ça suppose aussi que la table soit retriée à chaque modification (et là je crois pas que serait efficace lol)...

Donc en l'état, comme l'indexage est constamment mis à jour, je pense que le CPU est obligé de parcourir intégralement l'index à chaque requête... y'a que la partie "Cache" de mySQL qui peut accélérer le traitement, ainsi que le chargement de toute la base en mémoire (c'est pas pour rien que j'ai mis 1Go de RAM dans le serveur....) pour éviter tout accès disque et donc minimiser le temps de lecture...

Bref... bonne question !

Edité par soul^keeper le 23-01-2004 à 22:42 Raison de l'édition: Oops coquille

| IP: Logguée

BBenmarsGuruNiveau 31 · Guest starRéférenceur Appliqué

Membre depuis: 2002
Messages: 11324

Plus

Membre n°: 870
Inscription: 03 Apr 2002
Âge: 55 ans
Sujets lancés: 780
Ancienneté: 100 %
Participation: 95 %
Temps en ligne: 57 Jours, 6 Heures, 9 Minutes, 0 Seconde en ligne

23-01-2004 22:33

Si je comprends bien, un HD de 1 Go suffirait pour leserveur ...

A moins que ... quelle est la place occupée par les PM ?

__________________
Tout le monde est un génie. Mais si vous jugez un poisson sur ses capacités à grimper à un arbre, il passera sa vie à croire qu'il est stupide.
A. Einstein

| IP: Logguée

AdministrateurNiveau 50 · OscariséRéférenceur Légendaire

Membre depuis: 2002
Messages: 17438

Plus

Membre n°: 1
Inscription: 22 Feb 2002
Localisation: La Défense
Âge: 49 ans
Sujets lancés: 3040
Ancienneté: 100 %
Participation: 100 %
Temps en ligne: 104 Jours, 13 Heures, 5 Minutes, 37 Secondes en ligne

23-01-2004 22:38

Message écrit par Benmars, le 23-01-2004 à 22:33

Si je comprends bien, un HD de 1 Go suffirait pour leserveur ...

Hehe non... 1Go suffirait pour la base de données du forum

... C'est la seule déduction que tu peux faire.... si tu ajoutes Windows, les softs, les backups etc... idéalement il faudrait 1To

Message écrit par Benmars, le 23-01-2004 à 22:33

A moins que ... quelle est la place occupée par les PM ?

Trop.... beaucoup trop

| IP: Logguée

ZZakathGuruNiveau 29 · CascadeurRéférenceur Aguerri

Membre depuis: 2002
Messages: 9866

Plus

Membre n°: 7213
Inscription: 15 Dec 2002
Localisation: Copenhague
Sujets lancés: 426
Ancienneté: 97 %
Participation: 92 %
Temps en ligne: 103 Jours, 6 Heures, 15 Minutes, 39 Secondes en ligne

23-01-2004 22:38

That's it... La base de données ne retrie pas tout à chaque nouvelle insertion.

Cela dit, le cours d'info théorique affirme (à vrai dire, ce serait plutôt le Cormen et Rivest qui affirme

) qu'avec un arbre de type rouge-noir, qui est une sous-classe des arbres de recherche , on peut insérer un élément en un temps ln n (à moins que ce ne soit un n ln(n) ?) tout en préservant un relatif équilibre... Donc pas besoin *a priori* de tout retrier à chaque insertion.

Ca doit simplement être le coût CPU à chaque nouveau post qui empêche ce genre d'implémentation, alors...

__________________
Allez jeter un œil à mon portfolio !

| IP: Logguée

AdministrateurNiveau 50 · OscariséRéférenceur Légendaire

Membre depuis: 2002
Messages: 17438

Plus

Membre n°: 1
Inscription: 22 Feb 2002
Localisation: La Défense
Âge: 49 ans
Sujets lancés: 3040
Ancienneté: 100 %
Participation: 100 %
Temps en ligne: 104 Jours, 13 Heures, 5 Minutes, 37 Secondes en ligne

23-01-2004 22:46

Non mais je te le confirme, y'a pas de tri. En plus, on peut forcer le tri qu'on veut sur une table donnée (par la ligne de commande j'entend)... donc il est évident que la recherche ne se fait pas selon un schéma de représentation imposé.
Anyway, je ne vois pas véritablement OÙ pourrait être inséré une entrée dans "l'arbre" (en supposant que c'est bien en arbre que c'est implémenté) étant donné qu'il n'y a je le répète aucune logique particulière dans les entrées... ce ne sont que des associations wordid/postid étiquetés par un searchid bidon.... Je ne vois pas dans ces conditions comment "optimiser" l'arbre pour accélerer une recherche... Je ne vois pas non plus ce que pourrait signifier un arbre "équilibré" dans ce cas là... tu as une idée toi?

| IP: Logguée

ZZakathGuruNiveau 29 · CascadeurRéférenceur Aguerri

Membre depuis: 2002
Messages: 9866

Plus

Membre n°: 7213
Inscription: 15 Dec 2002
Localisation: Copenhague
Sujets lancés: 426
Ancienneté: 97 %
Participation: 92 %
Temps en ligne: 103 Jours, 6 Heures, 15 Minutes, 39 Secondes en ligne

23-01-2004 22:54

En utilisant une indexation bidon, il est clair que ce n'est pas possible, mais si on construit l'arbre de l'index de la manière suivante :

Au départ, arbre vide
Puis ajout d'un élément : on regarde la première lettre. S'il existe une branche existante avec cette lettre, on se place dessus, sinon on la crée. Si le mot est terminé, on ajoute la référence du post à une liste chainée qui se trouve à la dernière feuille où on est arrivé. Sinon, on enlève la première lettre du mot et on recommence.

Donc les noeuds de ton arbre seront formés d'un couple (liste chainée des posts correspondant à ce mot, tableau des 26 branches suivantes). Insérer un élément te prend un temps logarithmique au pire (descente dans ton arbre). Rechercher un élément pareil.

Est-ce que ça te semble viable ? J'ai fait une erreur quelque part ?

__________________
Allez jeter un œil à mon portfolio !

| IP: Logguée

Ddom95MaitreNiveau 16 · Critique de comptoirRéférenceur Appliqué

Membre depuis: 2002
Messages: 4597

Plus

Membre n°: 2839
Inscription: 05 Jul 2002
Localisation: RP
Sujets lancés: 113
Ancienneté: 99 %
Participation: 79 %
Temps en ligne: 61 Jours, 10 Heures, 11 Minutes, 23 Secondes en ligne

23-01-2004 23:11

Désolée pour l'intervention à côté de la plaque !

__________________

| IP: Logguée

AdministrateurNiveau 50 · OscariséRéférenceur Légendaire

Membre depuis: 2002
Messages: 17438

Plus

Membre n°: 1
Inscription: 22 Feb 2002
Localisation: La Défense
Âge: 49 ans
Sujets lancés: 3040
Ancienneté: 100 %
Participation: 100 %
Temps en ligne: 104 Jours, 13 Heures, 5 Minutes, 37 Secondes en ligne

23-01-2004 23:14

Message écrit par Zakath, le 23-01-2004 à 22:54

Non seulement c'est viable, mais c'est même à mon avis la meilleure manière de faire. Simplement, ça serait idéal dans un monde où TU implémentes toi-même cette structure de données... Le problème ici c'est que c'est du mySQL, et que le SQL, par définition c'est ultra simple (pour rappel SQL = Simple Query Language). Une table SQL c'est toujours des colonnes et des lignes... Y'a pas de notion de structure à n-dimensions.. c'est TOUJOURS du 2 dimensions ! Donc je serais surpris qu'il y ait différentes manières d'implémenter la table sur disque, vu que TOUTES les tables ont exactement la même façon simple de contenir des données....

une table mySQL, ça ressemble à un tableau Excel, exemple:

Code

+-----------------+-----------------+-----------------+
|      ID         |      PRENOM     |       AGE       |
+-----------------+-----------------+-----------------+
|      0          |      ALBERT     |       18        |
+-----------------+-----------------+-----------------+
|      1          |     MAURICE     |       35        |
+-----------------+-----------------+-----------------+
|      2          |      ROBERT     |       24        |
+-----------------+-----------------+-----------------+

C'est donc difficile d'imaginer une telle table s'implémenter comme t'as dit... surtout que les mots sont représentés par des numéros, et que le numéro attribué n'a pas de relation directe avec l'ortographe du mot. On ne peut donc pas imaginer un arbre dont le parcours des branches représenterait chaque chiffre du WordID parcouru de gauche à droite...

Mais même avec des lettres, ça me semble atrocement complexe à mettre en oeuvre (pour une TABLE SQL hein...) : à moins d'avoir une table à nombre de colonnes variable (et infini!) où chaque colonne ne contiendrait qu'UNE lettre du mot, etc.... enfin je sais pas à vrai dire... il y a parfois des années lumières entre la représentation "visuelle" et la représentation "interne" d'une structure de données... c'est peut être possible...

En tout cas, je suis allé vérifier la table de l'index, en fait j'ai dit une bêtise... ce sont les RECHERCHES (j'en ai pas parlé) qui ont un searchid bidon (il est attribué à la volée, et est visible dans l'URL d'ailleurs)... mais l'INDEX n'a pas d'ID bidon comme je disais... en fait la structure est la suivante:

CREATE TABLE `searchindex` (
`wordid` int(10) unsigned NOT NULL default '0',
`postid` int(10) unsigned NOT NULL default '0',
`intitle` smallint(5) unsigned NOT NULL default '0',
UNIQUE KEY `wordid` (`wordid`,`postid`)
) TYPE=MyISAM;

Le tri peut donc se faire (se fait!) sur le WordID puisque c'est la clé primaire (et unique!) (et ça me parait plus logique quand même lol... c'est ce que je disais plus haut d'ailleurs)

On peut donc imaginer que le fichier physique de la table de l'index se "fragmente" et soit géré AUTOMATIQUEMENT de manière optimale par mySQL, indépendamment des nouvelles entrées et des modifications...

| IP: Logguée

KkwiskasExpertNiveau 13 · Collectionneur DVDRéférenceur Assidu

Membre depuis: 2002
Messages: 2040

Plus

Membre n°: 7341
Inscription: 20 Dec 2002
Localisation: Toulouse
Âge: 46 ans
Sujets lancés: 128
Ancienneté: 97 %
Participation: 64 %
Temps en ligne: 14 Jours, 18 Heures, 52 Minutes, 27 Secondes en ligne

23-01-2004 23:17

très intéressant à lire tout ça !

Kwiskas

__________________

Venez découvrir le site de mon projet musical Phaselag
Téléchargez mon 1er album
Donnez moi votre avis à phaselag@yahoo.com

| IP: Logguée

ZZakathGuruNiveau 29 · CascadeurRéférenceur Aguerri

Membre depuis: 2002
Messages: 9866

Plus

Membre n°: 7213
Inscription: 15 Dec 2002
Localisation: Copenhague
Sujets lancés: 426
Ancienneté: 97 %
Participation: 92 %
Temps en ligne: 103 Jours, 6 Heures, 15 Minutes, 39 Secondes en ligne

23-01-2004 23:19

Je ne connais pas du tout ni les bases de données en général, ni MySQL en particulier, mais la question qui me vient immédiatement à l'esprit est : pourquoi utiliser MySQL s'il n'est pas optimal ?

Tu me dis si je t'embête avec toutes mes questions !

__________________
Allez jeter un œil à mon portfolio !

| IP: Logguée

AdministrateurNiveau 50 · OscariséRéférenceur Légendaire

Membre depuis: 2002
Messages: 17438

Plus

Membre n°: 1
Inscription: 22 Feb 2002
Localisation: La Défense
Âge: 49 ans
Sujets lancés: 3040
Ancienneté: 100 %
Participation: 100 %
Temps en ligne: 104 Jours, 13 Heures, 5 Minutes, 37 Secondes en ligne

23-01-2004 23:29

Toutes les bases de données du marché (ORACLE, SYBASE, mySQL, Access etc...) reposent sur SQL ou ses dérivés (SQL, mySQL, SQL+, PL/SQL etc... sachant que grosso modo c'est du kif kif, si ce n'est qu'il y a plus ou moins de fonctions supplémentaires/exclusives d'un dérivé à l'autre, mais bon la base est la même)

Et toutes les bases de données fonctionnent sur le même principe: un ensemble de tables à 2 dimensions. Je ne connais aucune base de données qui permettent de rentrer des listes, des piles, des tableaux à n dimensions etc.... tout ça, c'est réservé au domaine de la programmation pure.... mais dès que tu utilises une base de données, c'est forcément des tables... et le langage SQL a été conçu spécialement pour les requêtes sur ces structures simples.

Il n'y a donc aucune autre alternative.... en tout cas moi je n'en connais pas (mais je ne suis pas DBA expert non plus...)

Après, d'un SGBD à l'autre, il se peut qu'il y ait des façons de représenter ces tables qui diffèrent (puisque là ce sont les programmeurs qui les implémentent comme ils veulent, y compris en ayant recours à toutes les structures de données qui existent, donc les arbres, les graphes, etc... !) C'est ce qui explique d'ailleurs les différences de performance d'un système à l'autre. mySQL est ce qui se fait de mieux actuellement pour les webmasters, car PHP intègre par défaut toutes les fonctions nécessaires pour piloter mySQL. Des modules optionnels sont néanmoins utilisables pour gérer du MSSQL, ORACLE etc.. mais c'est plus compliqué, et surtout : vBulletin, phpBB, InvasionBB, etc... (enfin bref: TOUS les forums du marché) sont développés pour être interfacés avec mySQL... il n'y a donc là encore aucune alternative.....

| IP: Logguée

ZZakathGuruNiveau 29 · CascadeurRéférenceur Aguerri

Membre depuis: 2002
Messages: 9866

Plus

Membre n°: 7213
Inscription: 15 Dec 2002
Localisation: Copenhague
Sujets lancés: 426
Ancienneté: 97 %
Participation: 92 %
Temps en ligne: 103 Jours, 6 Heures, 15 Minutes, 39 Secondes en ligne

23-01-2004 23:44

C'est une mission pour.............................................. la FSF !!!!

Je note sur mon calepin : développer base de données avec structure arborescente. C'est entre la réalisation de mon OS et celle d'un code auto-réplicateur autonome

__________________
Allez jeter un œil à mon portfolio !

| IP: Logguée

DDidouGuruNiveau 23 · PerchisteRéférenceur Aguerri

Membre depuis: 2002
Messages: 5746

Plus

Membre n°: 65
Inscription: 24 Feb 2002
Sujets lancés: 289
Ancienneté: 100 %
Participation: 83 %
Temps en ligne: 43 Jours, 1 Heure, 39 Minutes, 14 Secondes en ligne

23-01-2004 23:56

Message écrit par soul^keeper, le 23-01-2004 à 23:29

Et toutes les bases de données fonctionnent sur le même principe: un ensemble de tables à 2 dimensions. Je ne connais aucune base de données qui permettent de rentrer des listes, des piles, des tableaux à n dimensions etc.... tout ça, c'est réservé au domaine de la programmation pure.... mais dès que tu utilises une base de données, c'est forcément des tables... et le langage SQL a été conçu spécialement pour les requêtes sur ces structures simples.

Il n'y a donc aucune autre alternative.... en tout cas moi je n'en connais pas (mais je ne suis pas DBA expert non plus...)

La représentation sous forme de tables est issue du modèle relationnel "conceptualisé" par Edgar F. Codd en 1969 je crois, c'est pour cela que l'on parle de bases de données relationnelles.

Ce modèle est effectivement devenu ultra-dominant dans le monde de la base de données : on ne parle plus du tout du modèle hiérarchique et d'un autre modèle dont j'ai oublié le nom....

Une alternative possible mais qui reste aujourd'hui très théorique car très très peu répandu : les bases de données objet (qui sont donc basés non pas sur le modèle relationnel mais sur le modèle objet).

Voilà c'était juste une précision au passage dans ce thread ma foi fort intéressant

__________________
Que chacun s'efforce dans le milieu où il se trouve de témoigner à d'autres une véritable humanité. C'est de cela que dépend l'avenir du monde.

| IP: Logguée