63.4. Реализация

В этом разделе освещаются детали реализации индекса-B-дерева, знание которых может быть полезно для специалистов. В дереве исходного кода имеется файл src/backend/access/nbtree/README, в котором реализация B-дерева рассматривается ещё глубже, на уровне алгоритмов.

63.4.1. Структура B-дерева

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

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

63.4.2. Исключение дубликатов

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

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

Примечание

Исключение дубликатов в B-дереве работает эффективно и с «дубликатами», содержащими значение NULL, несмотря на то, что значения NULL не считаются равными между собой согласно операторам =, входящим в классы операторов btree. Это объясняется тем, что с точки зрения реализации, работающей с внутренним представлением структуры B-дерева, NULL является просто одним из элементов множества всех возможных значений в индексе.

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

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

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

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

Подсказка

Для определения необходимости провести процедуру исключения дубликатов в уникальном индексе применяются дополнительные соображения. В таких индексах как правило можно перейти сразу к разделению листовой страницы, не расходуя лишние циклы на бесполезные проходы в поиске дубликатов. Если вас беспокоят возможные издержки, которые могут быть связаны с исключением дубликатов, вы можете установить значение deduplicate_items = off для отдельных индексов. Однако его вполне можно оставить включённым и для уникальных индексов.

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

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

  • Исключение дубликатов не может применяться с типами text, varchar и char в случае использования недетерминированных правил сортировки, так как в равных значениях должны сохраняться возможные различия в регистре и диакритических знаках.

  • Исключение дубликатов невозможно с типом numeric, так как для равных значений должен сохраняться числовой масштаб, который может быть разным.

  • Исключение дубликатов не может применяться с типом jsonb, так как внутри класса операторов B-дерева jsonb используется тип numeric.

  • Исключение дубликатов невозможно для типов float4 и float8. В этих типах имеются разные представления значений -0 и 0, которые при этом считаются равными. Однако отличие между ними должно сохраняться.

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

  • Исключение дубликатов невозможно с типами-контейнерами (это составные, диапазонные типы, а также массивы).

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

  • Исключение дубликатов не может применяться в индексах с INCLUDE.