Inside an inverted index

[Spidetra]

Les moteurs de recherches n'utilisent pas un SGBD pour stocker et indexer les informations.

Ils utilisent une structure connu sous le nom de : Inverted Index.

Ce post essaye de décrire ce que je comprend de la structure d'un inverted index.

J'espère que les zones d'ombres pourront être complété par les experts du Hub

1. Les fichiers qui composent un inverted index

Un inverted index est composé de segments. Dans notre exemple nous avons un seul segment _0.

Un segment est composé de différents fichiers.

En particulier certains fichiers ont des extensions du type : .fnm, .tis, .frq, .prx

Nous verrons un peu plus bas à quoi correspondent ces fichiers.

Un des fichiers important de ce répertoire est le fichier segment.

Ce fichier liste tout les segments présents dans notre inverted index.

Dans notre exemple nous n'avons qu'un seul segment : _0

Le moteur de recherche va se baser sur ce fichier pour savoir quels sont les noms des fichiers d'index qu'il devrat manipuler.

Dans notre exemple, ce sont les fichiers _0.fnm, _O.tis, _O.frq, _0.prx qui vont nous intéresser.

Le fichier deletable contient des informations sur les documents qui ont été marqués pour suppression.

Les fichiers ayant des extensions .fN ( N étant un nombre entre 0 et 8 dans notre exemple ) contiennent des informations sur

les champs présents dans les documents indéxés.

Dans notre exemple nous verrons que les 9 champs présents sont :

anchor, content, dccreator, dctitle, host, site, tag, title, url

2. Le fichier .fnm : liste les noms des champs

Ce fichier contient la liste de tout les champs composant l'inverted index.

Vous pouvez voir que j'ai configuré mon crawler pour prendre en compte

les méta Dublin Core ( dc:title et dc:creator )

Pour chacun de ces champs des flags indiquent les propriétés du champs : I, T, S, V

I : Indexed => Le champ est indéxé

T : Tokenized => Le champ est tokenize ( Découpé en mot )

S : Strored => Le champ est stocké

V : Vector => ???

3. Le fichier .tis : Dictionnaire des termes

Ce fichier contient tout les termes de l'index.

Un terme est un tuple contenant : Nom du champ et valeur du champ.

Un terme de notre exemple :

dctitle: XMLParser parse XMLData using Namespace and XPath

Ce fichier contient aussi un document frequency.

Cette valeur correspond au nombre de document du segment qui contiennent ce terme.

4. Les fichiers .frq et .prx : fréquences et positions des termes

Ces deux fichiers listent les fréquences et les positions des termes dans

l'ensemble des documents composant le segment.

La structure d'un inverted index est un compromis entre deux chemin :

- maximum de performance

- minimum de ressources utilisées.