60.4. Implémentation

Les lignes de feuille individuelles et les lignes intermédiaires doivent tenir dans une unique page d'index (8 Ko par défaut). Cependant, lorsque des données de taille variable sont indexées, les longues valeurs ne sont uniquement supportées que par les arbres suffixés, dans lesquels chaque niveau de l'arbre contient un préfixe qui est suffisamment petit pour tenir dans une page. La classe d'opérateur doit uniquement définir longValuesOK à TRUE si elle supporte ce cas de figure. Dans le cas contraire, le cœur de SP-GiST rejètera l'indexation d'une valeur plus large qu'une page.

De la même manière, il est de la responsabilité de l'opérateur de classe de s'assurer que la taille des lignes intermédiaires soit plus petite qu'une page ; cela limite le nombre de nœuds enfants qui peuvent être utilisés dans une ligne intermédiaire, ainsi que la taille maximum d'un préfixe.

Une autre limite est que lorsqu'un nœud de ligne intermédiaire pointe vers un ensemble de lignes de feuille, ces lignes doivent toutes être dans la même page d'index (il s'agit d'une décision d'architecture pour réduire le temps de recherche et utiliser moins de mémoire dans les liens qui lient de telles lignes ensemble). Si l'ensemble de lignes de feuille grandit plus qu'une page, un découpage est réalisé et un nœud intermédiaire est inséré. Pour que ce mécanisme résolve le problème, le nouveau nœud intermédiaire doit diviser l'ensemble de valeurs de feuilles en plus d'un groupe de nœuds. Si la fonction picksplit de la classe d'opérateur n'y parvient pas, le cœur de SP-GiST met en œuvre des mesures extraordinaires telles que décrites dans Section 60.4.3, « Lignes intermédiaires « All-the-same » ».

Certains algorithmes d'arbres utilisent un ensemble de nœuds figé pour chaque ligne intermédiaire ; par exemple, l'arbre quad-tree impose exactement quatre nœuds correspondant aux quatre coins autour du centroïde de la ligne intermédiaire. Dans ce cas, le code travaille généralement avec les nœuds au moyen de leur identifiant, et le besoin de label de nœud ne se fait pas ressentir. Pour supprimer les labels de nœud (et ainsi gagner de l'espace), la fonction picksplit peut retourner NULL pour le tableau nodeLabels. Cela aura pour effet d'obtenir une valeur NULL pour nodeLabels lors des appels aux fonctions choose et inner_consistent. En principe, les labels de nœuds peuvent être utilisés par certaines lignes intermédiaires, et ignorés pour les autres de même index.

Lorsqu'une ligne intermédaire sans label est concerné, la fonction choose ne peut pas retourner spgAddNode car l'ensemble des nœuds est supposé être fixé dans de tels cas. De même, il n'y a aucune raison de générer un nœud sans label dans les actions spgSplitTuple à partir du moment où une action spgAddNode est attendue.

Le cœur de SP-GiST peut surcharger les résultats de la fonction picksplit de l'opérateur de classe lorsque picksplit ne réussit pas à diviser la valeur de la feuille fournie en au moins un nœud. Dans ce cas, la nouvelle ligne intermédiaire est créée avec de multiples nœuds qui ont tous le même label (si un label est défini) qui est celui attribué au nœud utilisé par picksplit et les valeurs des feuilles sont divisées aléatoirement entre les nœuds équivalents. Le drapeau allTheSame est activé sur la ligne intermédiaire pour signifier aux fonctions choose et inner_consistent que la ligne n'a pas l'ensemble de nœud attendu.

Lorsque le cas d'une ligne allTheSame est rencontré, le résultat de la fonction choose sous la forme spgMatchNode est interprété de manière à ce que la nouvelle valeur puisse être assignée à chacun des nœuds équivalents ; le code du cœur de SP-GiST ignorera la valeur nodeN fournie et descendra dans l'un des nœuds enfants au hasard (pour conserver l'équilibre de l'arbre). Il s'agirait d'une erreur si la fonction choose retournait spgAddNode car tous les nœuds ne seraient pas équivalent ; l'action spgSplitTuple doit être utilisée si la valeur à insérer ne correspond pas aux nœuds existants.

Lorsque le cas d'une ligne allTheSame est rencontré, la fonction inner_consistent peut tout autant retourner tous les nœuds ou aucun des nœuds ciblés pour continuer la recherche indexée car ils sont tous équivalents. Cela peut éventuellement nécessiter du code spécifique, suivant le support réalisé par la fonction inner_consistent concernant la signification des nœuds.