A voir également:
- Utilisation d'Arbres binaires de recherches ?
- Notice d'utilisation - Guide
- Utilisation chromecast - Guide
- Impossible d'utiliser ce numéro de téléphone pour la validation - Forum Gmail
- Consultez le code source de cette page. copiez la ligne qui indique aux moteurs de recherche de ne pas référencer la page. ✓ - Forum Référencement
- Une restriction de compte utilisateur vous empeche de vous connecter ✓ - Forum Réseau
2 réponses
up.
Marco la baraque
Messages postés
996
Date d'inscription
vendredi 9 mai 2008
Statut
Contributeur
Dernière intervention
5 novembre 2009
328
11 déc. 2008 à 11:33
11 déc. 2008 à 11:33
Bonjour Griffin,
L'indexation des SGBD ne fonctionne pas exactement comme ça. On peut la considérer comme une implémentation d'arborescence mais ce n'est pas un arbre binaire.
Imagine une table contenant 1000 entrées. Pour que l'indexation soit possible, il faut qu'il existe une fonction de tri sur la colonne que tu souhaites indexer (tri naturel pour les int par exemple, tri alphabétique pour les varchar...).
L'indexation se fait de la manière suivante :
- le sgbd crée une première page contenant 10 valeurs (par exemple). Ici on va considérer qu'on utilise un index sur des int non signés : 0, 100, 200, .., 900
- le sgbd, pour chaque intervalle situé entre deux valeurs va créer une autre page (de façon récursive), par exemple la page 0 va pointer vers une page contenant 10, 20,... 90 ; et la page 30 va elle-même pointer vers une page contenant 31, 32, ... 39
Note bien qu'il n'est pas obligatoire de posséder absolument toutes les valeurs, comme dans mon exemple. Ce qu'il faut comprendre, c'est que le sgbd va simplement trier ta colonne, et stocker une liste de couples (valeur/adresse) dans plein de pages (dont la longueur est fonction de la taille de la pagination).
Ensuite, en ce qui concerne la recherche, ça se fait en complexité O(n log (n)), par dichotomie.
Exemple: tu recherches la valeur 43. Le sgbd va regarder dans la première page et va sélectionner la valeur médiane (ici 500). 43 est inférieur, donc on recherche dans la sous-partie (0, 500). Finalement, on se rend compte, à force de récurrence, que 43 se trouve dans la page pointée par 0 (car appartenant à (0,100)), donc on se déplace dans cette page et on continue le processus.
J'espère avoir été assez clair.
Cordialement,
L'indexation des SGBD ne fonctionne pas exactement comme ça. On peut la considérer comme une implémentation d'arborescence mais ce n'est pas un arbre binaire.
Imagine une table contenant 1000 entrées. Pour que l'indexation soit possible, il faut qu'il existe une fonction de tri sur la colonne que tu souhaites indexer (tri naturel pour les int par exemple, tri alphabétique pour les varchar...).
L'indexation se fait de la manière suivante :
- le sgbd crée une première page contenant 10 valeurs (par exemple). Ici on va considérer qu'on utilise un index sur des int non signés : 0, 100, 200, .., 900
- le sgbd, pour chaque intervalle situé entre deux valeurs va créer une autre page (de façon récursive), par exemple la page 0 va pointer vers une page contenant 10, 20,... 90 ; et la page 30 va elle-même pointer vers une page contenant 31, 32, ... 39
Note bien qu'il n'est pas obligatoire de posséder absolument toutes les valeurs, comme dans mon exemple. Ce qu'il faut comprendre, c'est que le sgbd va simplement trier ta colonne, et stocker une liste de couples (valeur/adresse) dans plein de pages (dont la longueur est fonction de la taille de la pagination).
Ensuite, en ce qui concerne la recherche, ça se fait en complexité O(n log (n)), par dichotomie.
Exemple: tu recherches la valeur 43. Le sgbd va regarder dans la première page et va sélectionner la valeur médiane (ici 500). 43 est inférieur, donc on recherche dans la sous-partie (0, 500). Finalement, on se rend compte, à force de récurrence, que 43 se trouve dans la page pointée par 0 (car appartenant à (0,100)), donc on se déplace dans cette page et on continue le processus.
J'espère avoir été assez clair.
Cordialement,
Griffin
>
Marco la baraque
Messages postés
996
Date d'inscription
vendredi 9 mai 2008
Statut
Contributeur
Dernière intervention
5 novembre 2009
11 déc. 2008 à 20:56
11 déc. 2008 à 20:56
Merci d'avoir répondu.
Si je comprends bien ton exemple, c'est à peu près la même idée qu'un arbre binaire sauf qu'on a 10 branche au lieu de 2 ? Cela me parait donc être plus efficace seulement à condition savoir rapidement dans quel branche aller.
Je pense que je ne vais me contenter de deux branches, au moins c'est clair : on compare le noeud avec l'élément recherché et on sait tout de suite où aller.
Néanmoins tu ne m'as pas dis s'il faut faire cette implémentation arborescent pour chaque attribut ? (ce qui me parait toutefois logique)
Si je comprends bien ton exemple, c'est à peu près la même idée qu'un arbre binaire sauf qu'on a 10 branche au lieu de 2 ? Cela me parait donc être plus efficace seulement à condition savoir rapidement dans quel branche aller.
Je pense que je ne vais me contenter de deux branches, au moins c'est clair : on compare le noeud avec l'élément recherché et on sait tout de suite où aller.
Néanmoins tu ne m'as pas dis s'il faut faire cette implémentation arborescent pour chaque attribut ? (ce qui me parait toutefois logique)
Marco la baraque
Messages postés
996
Date d'inscription
vendredi 9 mai 2008
Statut
Contributeur
Dernière intervention
5 novembre 2009
328
>
Griffin
11 déc. 2008 à 23:19
11 déc. 2008 à 23:19
Bonsoir,
Oui, ici mon arbre n'est pas binaire. Cependant, plus ta page sera de taille importante, plus ce sera efficace (c'est pour ça qu'avec des arbres binaires ce n'est pas le top). Après, il ne faut pas non plus que ta page soit trop grande (sinon le système de pagination ne sert à rien).
Ce qui est important, c'est d'éviter de charger toutes les données en mémoire (parce que si tu as 50 milliards d'entrées dans ta base c'est difficile : ça se fragmente, ça swappe à tout va... bref, ça rame), mais essayer d'en charger assez pour éviter de faire des accès disque à tout va (ce que tu vas faire si tu utilises un arbre binaire).
Et oui, il faut créer ce système de pagination pour chaque index. Il faudra aussi penser à mettre à jour tes pages lors de l'insertion de données (pas forcément à chaque fois, mais ton arborescence peut devenir déséquilibrée si tu ne le fais pas). Ici, avec un arbre binaire de recherche tu peux faire ça à chaque fois assez facilement avec les algorithmes de réorganisation que tu as du voir en cours.
Bien cordialement,
Oui, ici mon arbre n'est pas binaire. Cependant, plus ta page sera de taille importante, plus ce sera efficace (c'est pour ça qu'avec des arbres binaires ce n'est pas le top). Après, il ne faut pas non plus que ta page soit trop grande (sinon le système de pagination ne sert à rien).
Ce qui est important, c'est d'éviter de charger toutes les données en mémoire (parce que si tu as 50 milliards d'entrées dans ta base c'est difficile : ça se fragmente, ça swappe à tout va... bref, ça rame), mais essayer d'en charger assez pour éviter de faire des accès disque à tout va (ce que tu vas faire si tu utilises un arbre binaire).
Et oui, il faut créer ce système de pagination pour chaque index. Il faudra aussi penser à mettre à jour tes pages lors de l'insertion de données (pas forcément à chaque fois, mais ton arborescence peut devenir déséquilibrée si tu ne le fais pas). Ici, avec un arbre binaire de recherche tu peux faire ça à chaque fois assez facilement avec les algorithmes de réorganisation que tu as du voir en cours.
Bien cordialement,
Griffin
>
Marco la baraque
Messages postés
996
Date d'inscription
vendredi 9 mai 2008
Statut
Contributeur
Dernière intervention
5 novembre 2009
11 déc. 2008 à 23:49
11 déc. 2008 à 23:49
Merci bien, pour ces renseignements.
Quant à l'utilisation d'ABR, je ne suis qu'en première année d'école d'ingénieur en informatique et on n'a pas encore en théorie vu ces algorithmes. Cependant j'ai déjà bordé plusieurs fois les ABR et les fonctions de rééquilibrage en classe préparatoire (langage CaML).
Quant à l'utilisation d'ABR, je ne suis qu'en première année d'école d'ingénieur en informatique et on n'a pas encore en théorie vu ces algorithmes. Cependant j'ai déjà bordé plusieurs fois les ABR et les fonctions de rééquilibrage en classe préparatoire (langage CaML).
