Физическая структура индекса PostgreSQL

Question

Я пытаюсь понять, как физическая структура индекса PostgreSQL. Я узнал, что индексы - это хранилища как часть набора страниц со структурой данных B-дерева. Я пытаюсь понять, как пылесос влияет на показатели. Это помогает содержать его размер?

Answer 1

Индексы B-дерева - технология десятилетней давности, поэтому веб-поиск найдет много хороших подробных описаний. В двух словах:

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

Это эскиз индекса с глубиной три, но помните следующее:

• некоторые узлы опущены, в действительности все конечные узлы находятся на уровне 3
• на самом деле здесь не три записи (ключи) в одном узле, а около 100

                                     ┌───────────┐
                level 1 (root node)  │ 20 75 100 │
                                     └───────────┘
                                   ╱    ╱   │     ╲
                                  ╱    ╱    │      ╲
                                 ╱    ╱     │       ╲
                    ┌───────────┐┌─────┐┌──────────┐┌─────┐
           level 2  │ 5  10  15 ││ ... ││ 80 87 95 ││ ... │
                    └───────────┘└─────┘└──────────┘└─────┘
                                       ╱   ╱   │    ╲
                                      ╱   ╱    │     ╲
                                     ╱   ╱     │      ╲
                             ┌─────┐┌─────┐┌──────────┐┌─────┐
        level 3 (leaf nodes) │ ... ││ ... ││ 89 91 92 ││ ... │
                             └─────┘└─────┘└──────────┘└─────┘

Некоторые заметки:

• Указатели на следующий уровень фактически находятся в промежутках между записями, поиск в индексе подобен "детализации" до правильной конечной страницы.
• Каждый узел также связан со своими братьями и сестрами, чтобы облегчить вставку и удаление узлов.
• Когда узел заполнен, он разделяется на два новых узла. Это расщепление может повторяться и даже достигать корневого узла. Когда корневой узел разделен, глубина индекса увеличивается на 1.
• В реальной жизни глубина индекса B-дерева едва ли может превышать 5.
• При удалении записи индекса остается пустое место. Существуют методы, позволяющие объединить это путем объединения страниц, но это сложно, и PostgreSQL этого не делает.

Теперь к вашему вопросу:

Когда запись таблицы (кучи) удаляется VACUUM поскольку он не виден ни для какого активного снимка, соответствующая запись в индексе также удаляется. Это приводит к пустому пространству в индексе, которое может быть использовано в будущих записях индекса.

Пустые индексные страницы могут быть удалены, но глубина индекса никогда не будет уменьшена. Так что массовое удаление можно (после VACUUM выполнил свою работу) уменьшил размер индекса, но с большей вероятностью приведет к раздутому индексу со страницами, которые содержат только несколько ключей и много пустого пространства.

Некоторое количество раздувания индекса (до 50%) является нормальным, но если необычные шаблоны использования, такие как массовые обновления и удаления, вызывают плохое раздувание индекса, вам придется переписать индекс с REINDEX, тем самым избавляясь от вздутия. К сожалению, эта операция блокирует индекс, поэтому весь параллельный доступ блокируется до тех пор, пока он не будет выполнен.