Tantor BE B-Tree индексы являются многоуровневыми структурами дерева, где каждый уровень дерева может быть использован в качестве двусвязного списка страниц. Одна метастраница хранится в фиксированной позиции в начале первого сегментного файла индекса. Все остальные страницы являются либо листовыми страницами, либо внутренними страницами. Листовые страницы - это страницы на самом нижнем уровне дерева. Все остальные уровни состоят из внутренних страниц. Каждая листовая страница содержит кортежи, указывающие на строки таблицы. Каждая внутренняя страница содержит кортежи, указывающие на следующий уровень вниз по дереву. Обычно более 99% всех страниц являются листовыми страницами. Как внутренние, так и листовые страницы используют стандартный формат страницы, описанный в Раздел 70.6.

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

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

Индексы B-Tree пошагово удаляют версии устаревших кортежей индекса, выполняя проходы удаления индекса снизу вверх. Каждый проход удаления запускается в ответ на ожидаемое “разделение страницы из-за изменения версии”. Это происходит только с индексами, которые не изменяются логически с помощью операторов UPDATE, иначе на определенных страницах могло бы накапливаться большое количество устаревших версий. Обычно разделение страницы избегается, хотя возможно, что некоторые эвристические алгоритмы на уровне реализации не смогут идентифицировать и удалить ни одного ненужного кортежа индекса (в этом случае разделение страницы или проход дедупликации разрешает проблему входящего нового кортежа, который не помещается на листовую страницу). Максимальное количество версий, которые должен просмотреть любой сканирующий индекс (для любой отдельной логической строки), является важным фактором общей отзывчивости и пропускной способности системы. Проход удаления индекса снизу вверх нацелен на предполагаемые ненужные кортежи на одной листовой странице на основе качественных различий, касающихся логических строк и версий. Это отличается от “сверху вниз” очистки индекса, выполняемой рабочими процессами автоочистки, которая запускается, когда превышаются определенные количественные пороги на уровне таблицы (см. Раздел 23.1.6).

Удаление индексов снизу вверх выполняет подавляющее большинство всех операций очистки мусорных кортежей индекса для определенных индексов с определенной нагрузкой. Это ожидаемо для любого индекса B-Tree, который подвержен значительным изменениям версий от команд UPDATE, которые редко или никогда логически не изменяют столбцы, которые покрывает индекс. Среднее и наихудшее количество версий на логическую строку можно поддерживать на низком уровне только через целенаправленные инкрементальные проходы удаления. Вполне возможно, что размер индексов на диске никогда не увеличится даже на одну страницу/блок, несмотря на постоянные изменения версий от команд UPDATE. Даже в этом случае, исчерпывающая "чистка" операцией VACUUM (обычно выполняемая в рабочем процессе автоматической очистки) в конечном итоге потребуется в качестве части коллективной очистки таблицы и каждого из ее индексов.

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

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

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

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

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

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

Иногда уникальные индексы (а также уникальные ограничения) могут использовать дедупликацию. Это позволяет временно "поглотить" дубликаты версий на листовых страницах. Дедупликация в уникальных индексах дополняет стратегию удаления индекса снизу вверх, особенно в случаях, когда долговременная транзакция удерживает снимок, который блокирует сборку мусора. Цель состоит в том, чтобы купить время для повторного вступления в силу стратегии удаления индекса снизу вверх. Отсрочка разделения страниц до тех пор, пока не исчезнет единственная долговременная транзакция, может позволить успешно выполнить проход удаления снизу вверх, где ранее проход удаления не удался.

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

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

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

Существует еще одно ограничение на уровне реализации, которое применяется независимо от класса оператора или правила сортировки: