Les index B-Tree de PostgreSQL sont des structures arborescentes multi-niveaux, où chaque niveau de l'arbre peut être utilisé comme une liste doublement chaînée de pages. Une seule métapage est stockée à une position fixe au début du premier segment de fichier de l'index. Toutes les autres pages sont soit des pages feuilles, soit des pages internes. Les pages feuilles sont les pages de plus bas niveau de l'arbre. Tous les autres niveaux consistent en des pages internes. Chaque page feuille contient des tuples qui pointent sur les enregistrements en table. Chaque page interne contient des tuples qui pointent vers le niveau inférieur suivant dans l'arbre. En général, 99% des pages sont des pages feuilles. Aussi bien les pages internes que les pages feuilles emploient le format standard de page décrit dans Section 70.6.

Des nouvelles pages feuilles sont ajoutées à un index B-Tree quand un tuple entrant ne peut pas tenir dans une page feuille existante. Une opération de fractionnement de page a alors lieu et libère de la place pour les éléments qui appartiennent à la page surchargée en déplaçant une portion de ces éléments dans une nouvelle page. Le fractionnement de page doit aussi insérer un lien descendant vers la nouvelle page dans la page parente, ce qui peut causer à son tour le fractionnement du parent. Le fractionnement de page se produit en « cascade vers les niveaux supérieurs » de façon récursive. Si la page racine ne peut finalement pas porter le lien descendant, une opération de fractionnement de page racine se produit. Elle ajoute un nouveau niveau dans la structure arborescente en créant une nouvelle page racine un niveau au dessus de la page racine d'origine.

Les index B-Tree n'ont pas directement connaissance que sous MVCC, il peut y avoir plusieurs versions existantes de la même ligne logique d'une table ; pour un index, chaque ligne est un objet indépendant qui a besoin de sa propre entrée d'index. Le « renouvellement des versions » (version churn dans la version originale) des lignes peut parfois s'accumuler et nuire à la latence et au débit des requêtes. Ceci se produit typiquement avec des charges élevées en UPDATE où la plupart des mises à jour individuelles ne peuvent appliquer l'optimisation HOT. Changer la valeur de seulement une colonne couverte par un index durant un UPDATE nécessite toujours un nouveau ensemble d'entrées d'index -- un pour chaque et tous les index sur la table. Notons en particulier que cela inclut les index qui ne sont pas « modifiés logiquement » par la commande UPDATE. Tous les index nécessiteront une entrée d'index physique successeur qui pointe vers la dernière version en table. Chaque nouvelle entrée à l'intérieur de chaque index aura besoin, en général, de coexister avec l'entrée « modifiée » originale pour une courte période de temps (typiquement jusque peu après que la transaction de l'UPDATE soit validée).

Les index B-Tree suppriment de manière incrémentielle les entrées d'index de renouvellement de version en effectuant des passes de suppression ascendante de l'index. Chaque passe de suppression est déclenchée en réaction à un « fractionnement de page de renouvellement de version » anticipée. Ceci se produit avec les index qui ne sont pas modifiés logiquement par les déclarations UPDATE, dans lesquels des accumulations concentrées de versions obsolètes dans des blocs particuliers auraient lieu autrement. Un fractionnement de bloc sera normalement évité, bien qu'il est possible que certains niveaux d'implémentation d'heuristique échoueront même à identifier et à supprimer une ligne à renouveller (garbage tuple dans la version originale) d'index (dans ce cas, un fractionnement de bloc ou une passe de dédoublement résout le problème de l'entrée d'une nouvelle ligne qui ne rentre pas dans le bloc feuille). Le pire nombre de versions que n'importe quel parcours d'index doit traverser (pour n'importe quel enregistrement unique logique) est un contributeur important pour la réactivité et le débit globaux du système. Une passe de suppression ascendante d'index cible les lignes à renouveller supposées dans un bloc feuille unique par des distinctions qualitatives impliquant enregistrements logiques et versions. Ceci diffère des nettoyages d'index « descendants » effectués par les processus de l'autovacuum, qui sont déclenchés quand certains seuils quantitatifs au niveau table sont dépassés (voir Section 25.1.6).

Les suppressions ascendantes d'index effectuent la grande majorité des nettoyages des entrées à renouveller d'index pour certains index et certaines charges de travail. C'est le cas pour les index B-Tree sujets à un renouvellement de version significatif par les UPDATE qui ne modifient logiquement que rarement ou jamais les colonnes couvertes par l'index. La valeur moyenne et la pire valeur possible de versions par enregistrement logique peuvent être maintenues basses grâce aux passes incrémentales de suppression ciblée. Il est possible que la taille sur disque de certains index n'augmentera jamais même d'un simple bloc malgré un renouvellement de version continu par les UPDATE. Même si cela était le cas, un « nettoyage » exhaustif par une opération VACUUM (typiquement exécutée par un processus autovacuum), sera éventuellement requis comme une partie de nettoyage collectif de la table et chacun de ses index.

À la différence du VACUUM, la suppression ascendante d'index ne fournit pas de solides garanties pour déterminer quel peut être la plus ancienne entrée à renouveller dans l'index. Aucun index ne peut permettre de conserver des entrées d'index « à renouvellement flottant » qui seront morts avant le moment de conservation limite partagé collectivement par la table et tous ses index. Cette constante fondamentale au niveau table implique qu'il est sans danger de recycler les TID d'une table. C'est ainsi qu'il est possible pour les enregistrements logiques distincts de réutiliser les mêmes TID dans une table au cours du temps (bien que cela ne peut jamais se produire avec deux enregistrements logiques dont l'espérance de vie couvre le même cycle VACUUM).

Un doublon est un tuple de page feuille (un tuple qui pointe sur un enregistrement en table) où toutes les valeurs des colonnes clés de l'index correspondent aux valeurs de colonnes respectives d'au moins un autre tuple de page feuille dans le même index. Les tuples doublons sont assez communs en pratique. Les index B-Tree peuvent utiliser une représentation spéciale gérant efficacement l'espace pour les doublons lorsqu'une fonctionnalité est activée : le dédoublement.

Le dédoublement fonctionne en fusionnant périodiquement les groupes d'enregistrements doublons ensemble, formant une liste d'affectation unique pour chaque groupe. Le ou les valeurs de colonnes clés n'apparaissent qu'une fois dans cette représentation. Elles sont suivies par un tableau trié des TID pointant sur les lignes en table. Ceci réduit significativement la taille de stockage des index où chaque valeur (ou chaque combinaison distincte de valeur de colonne) apparait plusieurs fois en moyenne. La latence des requêtes peut sensiblement diminuer. Le débit général des requêtes peut augmenter sensiblement. Le coût supplémentaire de la routine de vacuum d'index peut aussi être notablement réduite.

Le processus de dédoublement se déroule avec le moins d'effort possible, quand un nouveau élément est inséré et ne peut rentrer dans une page feuille existante, mais seulement quand la suppression d'entrée d'index ne peut pas libérer suffisamment d'espace pour le nouvel élément (typiquement la suppression est brièvement considérée puis ignorée). Contrairement à la liste chainée d'enregistrements GIN, la liste chainée d'enregistrements B-Tree n'a pas besoin de s'étendre à chaque fois qu'un nouveau doublon est inséré ; ils sont simplement une représentation physique différente du contenu logique de la page feuille. Ce concept priorise l'uniformité des performances sur des charges de travail mixte en lecture-écriture. La plupart des applications clientes verront un bénéfice modéré sur les performances en utilisant le dédoublement. Le dédoublement est activé par défaut.

CREATE INDEX et REINDEX appliquent la déduplication pour créer les listes de lignes, bien que la stratégie utilisée soit un peu différente. Chaque groupe de lignes ordinaires dupliquées rencontré dans l'entrée triée prise à partir de la table est assemblé en une liste avant d'être ajouté à la page feuille en cours. Les listes individuelles sont assemblées avec autant de TID que possible. Les pages feuilles sont écrites de la façon habituelle, sans passe de déduplication séparée. Cette stratégie convient bien à CREATE INDEX et REINDEX car ce sont des opérations de groupe en lot unique.

Les charges de travail majoritaires en écriture et qui ne bénéficient pas du dédoublement du fait qu'il y a peu ou pas de doublons dans les index, encoureront une pénalité stable et légère de performance (sauf si le dédoublement est explicitement désactivé). Le paramètre de stockage deduplicate_items peut être utilisé pour désactiver le dédoublement au niveau de chaque index. Il n'y a jamais de pénalité de performance avec des charges de travail en lecture seule, puisque la lecture de liste chainée des tuples est au moins aussi efficace que la lecture de la représentation standard des tuples. Désactiver le dédoublement n'est en général pas utile.

Il est parfois possible pour des index uniques (autant que pour des contraintes uniques) d'utiliser le dédoublement. Cela permet aux blocs feuilles d'« absorber » temporairement les doublons supplémentaires des renouvellement de version. Le dédoublement des index uniques augmente les suppressions ascendantes d'index, spécialement dans les cas où une longue transaction garde un instantané qui bloque la collecte des éléments à nettoyer. Le but est de gagner du temps pour que la stratégie de suppression ascendante d'index devienne encore efficace. Retarder les fractionnements de blocs jusqu'à ce qu'une transaction longue finisse naturellement peut permettre à une passe de suppression ascendante de réussir là où une passe de suppression précédente a échoué.

Le dédoublement ne peut pas être utilisé dans tous les cas à cause des restrictions au niveau de l'implémentation. L'innocuité du dédoublement est déterminé quand CREATE INDEX ou REINDEX est exécutée.

Notez que le dédoublement est considéré comme non sécurisé et ne peut être utilisé dans les cas suivants qui impliquent des différences significatives au niveau sémantique parmi des données identiques :

Une autre restriction au niveau de l'implémentation existe et pourra être levée dans une version future de PostgreSQL:

Une autre restriction au niveau de l'implémentation s'applique quel que soient les classes d'opérateur ou collations employées :