Введение

Обратная стратегия индексации баз данных
Обратный индекс (СУБД)

Системы управления базами данных предоставляют различные типы индексов для повышения производительности и обеспечения целостности данных в широком спектре приложений. К типам индексов относятся b-деревья, растровые индексы и r-деревья. В системах управления базами данных стратегия индекса обратного ключа меняет порядок значения ключа перед его добавлением в индекс. Например, значение 24538 в индексе становится 83542. Изменение порядка значения ключа особенно полезно для индексации данных, таких как порядковые номера, где каждое новое значение ключа больше предыдущего, то есть значения монотонно возрастают. Индексы обратного ключа стали особенно важными в системах обработки больших объемов транзакций, поскольку они снижают конкуренцию за индексные блоки.

Создание данных

Индексы с обратным ключом используют структуру b-дерева, но предварительно обрабатывают значения ключей перед вставкой. Если упростить, b-деревья размещают схожие значения в одном блоке индекса, например, 24538 и 24539 могут храниться в одном и том же блоке. Это делает их эффективными как для поиска конкретного значения, так и для поиска значений в заданном диапазоне. Однако, если приложение вставляет значения последовательно, каждая вставка требует доступа к самому новому блоку индекса для добавления нового значения. Если несколько пользователей пытаются выполнить вставку одновременно, всем им приходится записывать данные в этот блок и ждать своей очереди, что замедляет работу приложения. Это особенно актуально для кластеризованных баз данных, которым может потребоваться копирование блока из памяти одного компьютера в память другого, чтобы следующий пользователь мог выполнить вставку. Обращение ключей распределяет новые схожие значения по всему индексу, вместо того чтобы концентрировать их в одном блоке листа. Это означает, что 24538 может оказаться в том же блоке, что и 14538, а 24539 – в другом блоке, что устраняет причину возникновения конфликтов. (Поскольку 14538 был бы создан задолго до 24538, их вставки не будут мешать друг другу.)

Данные запроса

Обратные индексы столь же эффективны, как и прямые индексы при поиске конкретных значений, однако они бесполезны для запросов по диапазону. Запросы по диапазону редко используются для искусственных значений, таких как номера последовательности. При поиске в индексе процессор запросов просто меняет порядок искомого значения на обратный перед его поиском.

Удаление данных

Как правило, приложения удаляют более старые данные в среднем, прежде чем удалять новые. Таким образом, данные с меньшими номерами последовательности обычно удаляются раньше, чем данные с большими номерами. Со временем в стандартных B-деревьях индексные блоки для меньших значений оказываются малозаполненными, что приводит к пропорциональному увеличению неиспользуемого пространства, называемого "вырождением" (или "разложением"). Вырождение не только приводит к потере места, но и замедляет скорость запросов, поскольку в память помещается меньшая часть блоков вырожденного индекса. В B-дереве, если удаляется значение 14538, его индексное пространство остается пустым.