Discussion :

[camboui]

Un B+tree est un arbre n-aire dans lequel les données ne se trouvent que dans les noeuds terminaux, ces noeuds contiennent aussi les clés. Les noeuds intermédiares ne contiennent que les clés. Chaque élément (clé) d'un noeud intermédiaire possède deux pointeurs vers des noeuds inférieurs, ceux à gauche pour lesquels les clés sont < et ceux à droite pour lesquels les clés sont >=.
Cependant je constate que cette contrainte est violée quand une clé est dupliquée plus de N fois (N= ordre de l'arbre). Dans les docs, exemples et multiples simulations trouvés ça et là on ne traite que le cas où les clés sont toutes de valeurs différentes.
Ainsi supposons le cas extrême d'un arbre d'ordre N dans lequel on insère 3*N fois la même clé. On obtient 3 noeuds terminaux et un noeud parent racine dans lequel il devrait y avoir deux clés. Ces deux clés ne peuvent avoir que la seule valeur de clé introduite jusque là dans l'arbre. Comment donc respecter la contrainte dans ce cas ?
Merci.

[pseudocode]

Et en changeant la contrainte : "inférieur ou égal" pour le noeud gauche et "supérieur strict" pour le noeud droit ?

[camboui]

Essaie de dessiner un arbre d'ordre 3 par exemple avec 9 éléments qui ont tous la même clé. Il devrait y avoir donc 4 noeuds, 1 racine et 3 feuilles, 3 éléments dans chacune des feuilles et, me semble-t-il, 2 éléments dans la racine. Mais voilà, ces deux éléments ont la même valeur de clé. La feuille-noeud pointée entre ces deux valeurs ne respecte pas les relations d'ordre. Qu'elles soient strictes à gauche ou à droite ne change rien.

[Luc Orient]

Essaie de dessiner un arbre d'ordre 3 par exemple avec 9 éléments qui ont tous la même clé ...

Et si considère qu'il n'y a pas 9 éléments, mais un seul élément (puisqu'il y a une seule clé) avec 9 informations différentes ?

[camboui]

Tu sors du cahier des charges.

Pour faire une analogie en C++, pour ceux qui connaissent sa STL, il s'agit de faire comme un std::multi_set<> et non pas comme un std::set<>. C'est-à-dire que les clés multipes sont autorisées.

Ceci ne veut pas dire que ta proposition n'est pas bonne, ce n'est juste pas ce que je cherche à comprendre.
A moins que j'ai fait une erreur de compréhension et que le B-Tree ne supporte pas les clés multiples. Mais je ne le vois nulle part dans les explications du B-Tree.

[Luc Orient]

Il se trouve que je suis DBA, et, en principe, tout DBA sait qu'un index sur une table dans une Base de données est très souvent réalisé sous la forme d'un index équilibré ( "balanced tree" en anglais ).

Ce type de structure, sans être totalement analysé, est souvent présenté sommairement dans les cours d'administration portant sur un SGBD en particulier.

Bien entendu, un index sur une table peut être unique ou non-unique, et dans ce dernier cas on est bien face au cas que tu décris.

J'ai laissé mes supports de cours au bureau et je verrai demain si je trouve des informations complémentaires mais voilà déjà ce que je peux lire dans l'ouvrage suivant :
Relationnal Database Index Design and the Optimizers

Af far back as the sixties, the indexes of file and database systems were built as balanced trees.
Index rows are stored in leaf pages. Today, the typical index page size is 4 or 8 kb. The lenght of an index row is usually the sum of the length of the index columns plus about 10 bytes of control information. If a total length of an index row is 200 bytes, about 40 index rows will fit in an 8K leaf page if the index is unique. In a nonunique index, several pointers may follow each key value; in many DBMS these pointers are stored in pointer value sequence. This is enable the DBMS to quickly find a pointer to be deleted even if there are a million pointers chained to one key value. We mention this because for historical reasons, some DBAs are worried about the impact of the maximum chain length on delete performance.

[pseudocode]

. Mais voilà, ces deux éléments ont la même valeur de clé. La feuille-noeud pointée entre ces deux valeurs ne respecte pas les relations d'ordre.

Valeurs multiples => Clés potentiellement identiques => relation d'ordre non stricte.

Qu'elles soient strictes à gauche ou à droite ne change rien.

Effectivement, ca ne change rien au principe. Mais du fait que la relation est non stricte, choisir "inférieur ou égal" à gauche permet d'avoir une certaine cohérence pour le noeud racine.

Code :

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

1
2
3
4
5
 
        [1,1,infini]
    _____| | |_____
 __|__   __|__   __|__
[1,1,1] [1,1,1] [1,1,1]

[camboui]

J'ai laissé mes supports de cours au bureau et je verrai demain si je trouve des informations complémentaires mais voilà déjà ce que je peux lire dans l'ouvrage suivant :
Relationnal Database Index Design and the Optimizers

Merci.

Ce que tu dis tend à faire penser que le Btree ne supporte pas les doublons dans ses valeurs de clé. Mais je n'arrive pas à trouver explicitement la confirmation de cette contrainte dans les explicatons de l'algo.
Si c'est le cas, comment donc est stocké le chainage de pointeur sous chaque valeur (unique) de clé ?
Cette info est de longueur très variable et je ne vois pas trop comment la paginer (par block de 4 ou 8Kb d'après ton extrait). De plus, s'il y en a un million comme dans l'extrait et qu'on veut en supprimer un quelque part au milieu de la chaine...

[camboui]

Valeurs multiples => Clés potentiellement identiques => relation d'ordre non stricte.



Effectivement, ca ne change rien au principe. Mais du fait que la relation est non stricte, choisir "inférieur ou égal" à gauche permet d'avoir une certaine cohérence pour le noeud racine.

Code :

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

1
2
3
4
5
 
        [1,1,infini]
    _____| | |_____
 __|__   __|__   __|__
[1,1,1] [1,1,1] [1,1,1]

On ne peut pas avoir une relation d'ordre non stricte à gauche et à droite en même temps. Il faut bien qu'elle soit stricte d'un des deux cotés. Que tu choisisses l'un ou l'autre coté, la contrainte n'est pas respectée par au moins un des deux éléments de la racine.

[pseudocode]

On ne peut pas avoir une relation d'ordre non stricte à gauche et à droite en même temps. Il faut bien qu'elle soit stricte d'un des deux cotés. Que tu choisisses l'un ou l'autre coté, la contrainte n'est pas respectée par au moins un des deux éléments de la racine.

heu... oui. Il me semble qu'on dit la même chose : on ne peut pas avoir une relation d'ordre stricte avec des valeurs identiques. D'où le fait de choisir le critère "on descend dans le noeud de gauche si la valeur est inférieur OU EGALE à la clé".

[camboui]

...
"on descend dans le noeud de gauche si la valeur est inférieur OU EGALE à la clé".

Et quand descend-on à droite alors ? Il y a aussi des valeurs égales de clé à droite.

Je suis un peu perdu. Quelqu'un aurait-il un cours/tuto/illustration/animation exhaustif d'un B+tree dans le cas de clés multiples ? (en français si possible)

[pseudocode]

"on descend dans le noeud de gauche si la valeur est inférieure OU EGALE à la clé".

Et quand descend-on à droite alors ?

Il n'y a pas uniquement gauche et droite dans un noeud. Il peut y a voir plus de 2 enfants. L'algo général consiste à tester itérativement les différentes clés contenues dans le noeud.

Par exemple un noeud avec 4 clés (donc 4 enfants possibles)

Code :

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

1
2
3
4
     [a, b, c, d]
  ____|  |  |  |___
 |       |  |      |
[#1]  [#2]  [#3] [#4]

soit "x" la valeur a trouver, on fait successivement les tests suivants :

1. si (x<=a) on descend dans le noeud #1
2. si (x<=b) on descend dans le noeud #2
3. si (x<=c) on descend dans le noeud #3
4. si (x<=d) on descend dans le noeud #4

Ca fonctionne donnc aussi avec des clés identiques

[camboui]

OK merci.
Mais ce n'est pas tout à fait clair dans mon esprit.
J'ai trouvé du code en C++ ici http://idlebox.net/2007/stx-btree/ code qui permet des clés uniques comme multiples, avec ou sans donnée associée aux clés.