complexité d'une recherche ?

[Ekinoks]

Salut !

Si je me trompe pas, une base de donnée utilise des arbre de recherche équilibré et donc une recherche classique du type select * from table where id = 12 est de complexité ln(nombre_d_element_dans_table) ?

Maintenant si on dit que "id" est un INDEX, es que cela reviens à avoir un tableau et insérer dans la "Neme" case du tableau les elements qui on "id" = N ? avec donc un temps de recherche constant ?

Merci pour vos réponses.

[fsmrel]

Si je me trompe pas, une base de donnée utilise des arbre de recherche équilibré et donc une recherche classique du type select * from table where id = 12 est de complexité ln(nombre_d_element_dans_table)

Les bases de données n’utilisent pas d’arbres, par contre, les SGBD c’est généralement le cas, si on a défini des index organisés en arbres. Par exemple, avec DB2 for z/OS, les index sont organisés en arbres B+. Je ne sais pas ce que vous entendez par "complexité". En tout état de cause, si l’attribut Id est indexé et que le facteur de filtrage est optimal (l’attribut id étant par exemple clé primaire ou équivalent de la table concernée), si l'index n'est pas désorganisé, le nombre de lectures de pages du fichier sur lequel repose l’index est égal à la hauteur de l’arbre (nombre de niveaux d’index) + 1 (pour la page de données). Par exemple, telle table contenant 400 000 000 de lignes, pour laquelle on a 4 niveaux d’index, à 10 millisecondes la lecture, votre requête coûtera 50 millisecondes, à la louche.

Toujours avec DB2, si la clé (Id) mesure 4 octets, Le 1er niveau d’index comportera 1 page, le 2e niveau 10 pages, le 3e niveau 2 900 pages et le 4e niveau 1 100 000 pages.

[Ekinoks]

merci pour ta réponse fsmrel ! =)

He... je ne voie pas bien ce que c'est le niveaux d'index mais cela veux dire que le temps d'exécution de la requête de dépend que du niveau de l'index et non pas du nombre d'élément ?

[fsmrel]

He... je ne voie pas bien ce que c'est le niveaux d'index mais cela veux dire que le temps d'exécution de la requête de dépend que du niveau de l'index et non pas du nombre d'élément ?

Je ne vais pas m'embarquer dans un cours sur les arbres B (on doit trouver ça un peu partout), mais l'objet d'un index est l'accès aux pages de données en effectuant un minimum d'entrées/sorties. Clairement, s'il en faut en compter 5 dans l'exemple ci-dessus, sans index, c'est une autre chanson. Dans ce cas-là, si les pages sont de 4K, pour une ligne de données de 200 octets en moyenne et un taux de compression de 40%, le SGBD devra balayer au pire 14 000 000 de pages pour traiter le Select initial. Les lectures se feront par rafales disons de 64 pages : à 4 millisecondes par page, cela fait 14 000 000 / 4 millisecondes, ce qui laisse le temps de faire un tour au troquet du coin et de revenir dans un triste état... avant de lancer la requête suivante.