Discussion :

[Napalm51]

Bonjour, j'espère que c'est bien le bon endroit pour poster cette demande

Problème : J'ai une sorte de base de données sous forme de fichiers (très nombreux) comportant chacun un grand nombre de ligne. Mon but est de trouver, avec une ligne donnée, le fichier de ma base dans lequel une ligne équivalente est présente. Bien entendu, peu importe la ligne en entrée, pour le moment tous les fichiers de la base sont parsés jusqu'à trouver (ou non) cette fameuse ligne. Résultat, quand je dois trouver 100 lignes il parcours 100 fois ma base de fichiers, ce qui fait non seulement des accès disques à répétition, mais également une perte de temps assez importante, et une utilisation CPU énorme.

Question : Quel serait la meilleur façon de représenter cette base de donnée, afin de minimiser le temps de recherche et les ressources nécessaires, sachant qu'il est impossible à partir de la ligne recherchée de savoir si elle à plus de chance d'être dans tel ou tel fichier de la base.

Merci d'avance à ceux qui répondrons.

[Jean-Marc.Bourguet]

Tel que tu poses le probleme, je vois trois approches:
- rechercher simultanement tes 100 lignes dans chaque fichier. C'est l'approche la plus simple mais elle suppose que tu peux rassembler les requetes.
- batir une sorte d'index qui te permet de choisir les fichiers ou chercher.
- changer complement de structure.

Tu ne donnes pas assez d'information pour t'aider dans les deux dernieres approches.

[Napalm51]

D'abord merci de ta réponse. Ensuite, je vais préciser, un script va lire les logs de mon serveur qui fait du filtrage HTTP. Dans ces logs, il retrouve l'URL de tous les sites visités, il découpe alors cette chaine afin d'en extraire uniquement le domaine, du style "google.com" ou "developpez.net". Je dois alors définir dans quelle catégorie de site se trouve ce domaine. J'ai donc un nombre important de fichiers contenant des domaines, comme pirate.txt contenant un grand nombre de domaines de sites pirate, etc ...

Maintenant pour savoir si "google.com" appartient à la catégorie "moteur de recherche" ou "pirate" il faut parcourir les deux fichiers texte et vérifier si le domaine est bien dedans. Cette opération est actuellement longue car il va fouiller tous les fichiers jusqu'à trouver le bon. Je cherche à optimiser cette recherche, et ceci peu passer par un changement total de la structure de donnée. C'est pourquoi je demande votre aide.

Il ne me semble pas possible de "pré-catégoriser" le domaine, si ce n'est pour les sites fréquents comme google ou pages jaunes. Mais j'espère me tromper

[edfed]

que penses tu d'un systeme de fichier genre reiser fs?
ce systeme est bien performant.
une base de donnée, c'est un systeme de fichiers.

ou alors, crée une liste d'index alphabetiques/groupes.
les index, c'est des pointeurs, un pointeur, c'est une addresse memoire, ou un offset dans un fichier.

cette structure est tres simple à creer et la recherche d'un mot est tres rapide.
il suffit juste de connaitre la premiere lettre du mot recherché et le groupe à explorer, par contre, ça bouffe de la memoire, mais c'est tout de meme plus rapide qu'une recherche de mots dans un fichier sans savoir où il est...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
ceci est du pseudo asm, mais c'est facile à comprendre
 
 
group? c'est un id du groupe dans lequel est rangé l'url
size, c'est la taille de la structure en octets.
la base est composée de plusieurs structures:
 
groupxxx c'est le nom du groupe, une structure où sont
classés les pointeurs des url de cette structure.
 
meta pour le classement alphabetique des url
 
A, B, C ... pour classer les pointeurs de chaines pour chaque url
et finalement, la chaine de carateres en question.
 
groupcuisine:
size dd ?
dd bonnesrecettes.com
dd j'aimelagalette.fr
dd spaghettis.org
dd ...
 
groupmoteurderecherche:
size dd ?
dd google.com
dd blackle.com
dd ...
 
meta:
size dd ?
dd A
dd B
dd C
dd D
dd..
dd Z
 
A:
size dd ?
dd alapage.fr,group?
dd allomairie.fr,group?
dd ..
 
alapage.fr:
db 'alapage.fr'0
allomairie.fr:
db 'allomairie.fr'0
 
B:
size dd ?
dd bellesdusud.org,group?
dd bonnesrecettes.com,group?
dd blackle.com
dd ...
 
bellesdusud.org:
db 'bellesdusud.org',0
bonnesrecettes.com:
db 'bonnesrecettes.com',0
blackle.com:
db 'blackle.com',0
...
G:
size dd ?
dd google.com
dd google.fr
dd grossefaimdeloupjevaisallermanger.fr
dd ...

voila pour une structure de donnée bien rapide.
les algorithmes pour l'utiliser en decoulent...

voire comment faire une implementation en language de haut niveau... quoi qu'il en soit, le resultat, c'est des octets.

[Napalm51]

Merci pour ces infos, je vais me pencher plus en profondeur sur cette structure.