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 69.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.

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. Cela permet (ou au moins repousse) le fractionnement de page feuille. 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.

Pour les index B-Tree, sous MVCC, il peut y avoir plusieurs versions existantes du même enregistrement logique en table ; pour un index, chaque tuple est un objet indépendant qui nécessite sa propre entrée dans l'index. Les « duplicatats de version » peuvent parfois s'accumuler et affecter négativement la latence et le débit des requêtes. Ceci survient typiquement avec les charges de travail lourdes en UPDATE où la plupart des mises à jours individuelles ne peuvent pas utilisées l'optimisation HOT (souvent parce qu'au moins une colonne indexée est modifiée, nécessitant ainsi un nouvel ensemble de versions de lignes d'index -- une nouvelle ligne pour chacun des index). En fait, la déduplication B-Tree améliore la fragmentation des index causée par le versionnement. Notez que même les lignes d'un index unique ne sont pas nécessairement physiquement uniques lors du stockage sur disque à cause du versionnement. L'optimisation de la déduplication est appliquée sélectivement dans les index uniques. Elle cible les pages qui semblent avoir des duplicatas de versions. Le but principal est de donner plus de temps pour l'exécution du VACUUM avant qu'une division de page « inutile » causée par le versionnement puisse se faire.

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 :