Индексы-B-деревья в PostgreSQL представляют собой многоуровневые иерархические структуры, в которых каждый уровень дерева может использоваться как двусвязный список страниц. Единственная метастраница индекса хранится в фиксированной позиции в начале первого файла сегмента индекса. Все остальные страницы делятся на внутренние и на листовые. Листовые страницы находятся на самом нижнем уровне дерева. Все более высокие уровни состоят из внутренних страниц. Листовая страница содержит кортежи, указывающие на строки в таблице, а внутренняя страница — кортежи, указывающие на следующий уровень в дереве. Обычно листовые страницы составляют около 99% всех страниц индекса. И для тех, и для других страниц используется один стандартный формат, описанный в Разделе 73.6.

Новые листовые страницы добавляются в B-дерево когда существующая листовая страница не может вместить новый поступающий кортеж. При этом выполняется операция разделения страницы, освобождающая место на переполнившейся странице, перенося подмножество изначально содержащихся на ней элементов на новую страницу. При разделении страницы в её родительскую страницу также должна быть добавлена ссылка вниз, что может потребовать произвести разделение и этой родительской страницы. Разделение страниц «каскадно поднимается вверх» рекурсивным образом. Когда же и корневая страница не может вместить новую ссылку вниз, производится операция разделения корневой страницы. При этом в структуру дерева добавляется новый уровень, на котором оказывается новая корневая страница, стоящая над той, что была корневой ранее.

В реализации индексов-B-деревьев не учитывается, что в среде MVCC может быть несколько версий одной логической строки таблицы; для индекса каждый кортеж является независимым объектом, требующим отдельного элемента в индексе. Кортежи «отработанных версий» иногда могут накапливаться, что чревато задержками и замедлением при выполнении запросов. Это обычно происходит при нагрузке с преобладанием UPDATE, когда для большинства отдельных операций изменения данных нельзя применить оптимизацию HOT. Изменение значения даже одного индексируемого столбца во время UPDATE всегда требует добавления нового набора индексных кортежей — отдельного кортежа для каждого индекса в таблице. Более того, обратите внимание, что новые кортежи требуются и для тех индексов, которые не были «логически изменены» командой UPDATE. Во всех индексах будут нужны дополнительные физические кортежи, указывающие на последнюю версию строки в таблице. Каждый новый кортеж в каждом индексе, как правило, должен сосуществовать с исходным подвергшимся изменению кортежем в течение короткого периода времени (обычно недолго после фиксации транзакции UPDATE).

В индексах-B-деревьях постепенно удаляются кортежи отработанных версий в ходе процедуры восходящего удаления индексных кортежей. Каждый проход процедуры удаления вызывается, когда ожидается, что произойдёт «разделение страниц из-за отрабатывания версий». Это касается только тех индексов, которые не были логически изменены операторами UPDATE, так как именно в них возможно концентрированное накопление устаревших версий на определённых страницах. Реализация обычно старается избежать разделения страниц, хотя вполне возможно, что определённые решения на её уровне не позволят идентифицировать и удалить ни одного мусорного кортежа в индексе (в этом случае проблема размещения нового кортежа на заполненной листовой странице решается путём разделения страницы или в результате исключения дубликатов). Большое количество версий каждой отдельной логической строки, которое нужно прочитать при каждом сканировании индекса, является важным отрицательным фактором общей производительности и скорости отклика системы. Процедура восходящего удаления индексных кортежей выбирает на листовой странице предположительно мусорные кортежи на основании качественных характеристик, определяемых логическими строками и версиями. Это отличает её от «нисходящей» уборки индекса, выполняемой процессами автоочистки, которая запускается при превышении определённых количественных пороговых значений на уровне таблицы (см. Подраздел 25.1.6).

При определённой нагрузке восходящее удаление индексных кортежей выполняет основную работу по уборке мусорных кортежей из индексов. Такой эффект ожидается для любого индекса-B-дерева, который в значительной мере затрагивается активностью отрабатывания версий из-за команд UPDATE, почти никогда не изменяющих логически столбцы, покрываемые индексом. Среднее и наибольшее количество версий для логической строки может поддерживаться на низком уровне исключительно за счёт постоянных точечных проходов удаления. Вполне возможно, что размер определённых индексов на диске никогда не увеличится ни на одну страницу/блок, несмотря на постоянное отрабатывание версий, вызываемое командами UPDATE. Но даже в этом случае в конце концов потребуется полная «зачистка» индекса процедурой VACUUM (обычно запускаемой в рабочем процессе автоочистки) как часть совместной уборки таблицы и всех её индексов.

В отличие от VACUUM, восходящее удаление не даёт никаких надёжных гарантий относительно возраста старейшего мусорного индексного кортежа. Ни в одном индексе не допускается сохранение «плавающих мусорных» кортежей, ставших мёртвыми до консервативной точки отсечения, являющейся общей для таблицы и всех её индексов. Этот фундаментальный инвариант на уровне таблицы позволяет обеспечивать безопасную циркуляцию табличных идентификаторов (TID). Именно таким образом разные логические строки могут повторно использовать один и тот же идентификатор с течением времени (хотя это невозможно для двух логических строк, время жизни которых укладывается в один и тот же цикл VACUUM).

Дубликатом называется кортеж на листовой странице (кортеж, указывающий на строку таблицы), у которого все ключевые столбцы индекса имеют значения, соответствующие значениям столбцов из как минимум одного другого кортежа на листовой странице в том же индексе. Дублирующиеся кортежи довольно часто встречаются на практике. В индексах-B-деревьях такие дубликаты могут представляться особым экономичным образом при включении дополнительного механизма — исключения дубликатов.

Работа этого механизма заключается в периодическом объединении групп дублирующихся кортежей и формировании одного кортежа со списком идентификаторов для каждой группы. В таком представлении значения ключевых столбцов хранятся в единственном экземпляре, а за ними идёт отсортированный массив идентификаторов TID, указывающих на строки в таблице. Это существенно уменьшает размер хранящихся индексов, в которых каждое значение (или каждое уникальное сочетание значений столбцов) появляется в среднем несколько раз. В результате может значительно увеличиться скорость выполнения запросов, а также могут сократиться издержки, связанные с регулярной очисткой индексов.

Процесс исключения дубликатов осуществляется по необходимости, когда вставляется новый элемент, не умещающийся на существующей листовой странице, но только тогда, когда удаление индексного кортежа не может освободить достаточно места для нового элемента (обычно удаление недолго рассматривается, а затем пропускается). В отличие от кортежей со списками идентификаторов GIN, в B-дереве эти кортежи не должны расширяться при каждом добавлении нового дубликата; они просто образуют другое физическое представление исходного логического содержимого листовой страницы. При таком подходе обеспечивается стабильная производительность при смешанной нагрузке чтения-записи. Исключение дубликатов должно дать как минимум заметное увеличение производительности для большинства клиентских приложений. По умолчанию оно включено.

Команды CREATE INDEX и REINDEX также выполняют исключение дубликатов, создавая кортежи со списками идентификаторов, но применяют несколько другую стратегию. Каждая группа дублирующихся обычных кортежей, обнаруженных в отсортированных данных, преобразуется в кортеж со списком идентификаторов до того, как данные добавляются в текущую листовую страницу. При этом в каждый такой кортеж упаковывается как можно больше идентификаторов (TID). После этого листовые страницы записываются обычным способом, без дополнительного прохода для исключения дубликатов. Эта стратегия подходит для команд CREATE INDEX и REINDEX, так как они обрабатывают все данные сразу.

Если же в профиле нагрузки преобладает запись и исключение дубликатов не приносит выигрыша ввиду отсутствия или небольшого числа дублирующихся значений, этот механизм может породить небольшие постоянные издержки (если он не отключён). В таких случаях его можно отключить для отдельных индексов с помощью параметра хранения deduplicate_items. При нагрузке только на чтение никакие дополнительные издержки не возникают, так как кортежи со списком идентификаторов читаются так же эффективно, как и кортежи в стандартном представлении. Поэтому чаще всего отключение этого механизма не будет полезным.

Исключение дубликатов иногда может использоваться для уникальных индексов (а также уникальных ограничений). Благодаря этому дополнительные дубликаты отработанных версий могут временно «поглощаться» листовыми страницами. Исключение дубликатов в уникальных индексах дополняет восходящее удаление индексных кортежей, особенно в тех случаях, когда длительная транзакция держит снимок, препятствующий сборке мусора. Тем самым выигрывается время для восстановления эффективности стратегии восходящего удаления индексных кортежей. Откладывание разделения страниц до естественного завершения одной длительной транзакции позволяет успешно произвести проход восходящего удаления, который ранее был невозможен.

Исключение дубликатов может применяться не всегда ввиду ограничений на уровне реализации. Возможность его применения определяется во время выполнения CREATE INDEX или REINDEX.

Учтите, что исключение дубликатов считается небезопасным и не может применяться в следующих случаях, когда возможны семантические различия равных значений:

Имеется ещё одно ограничение на уровне реализации, которое может быть снято в будущих версиях PostgreSQL:

Есть ещё одно ограничение на уровне реализации, действующее вне зависимости от применяемого класса операторов или правила сортировки: