Обратный индекс

Системы управления базами данных предоставляют несколько типов индексов для повышения производительности и целостности данных в различных приложениях. Типы индексов включают b-деревья , растровые изображения и r-деревья .

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

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

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

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

Запрос данных

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

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

Обычно приложения удаляют более старые данные в среднем перед удалением более новых данных. Таким образом, данные с более низкими порядковыми номерами обычно идут раньше, чем данные с более высокими значениями. С течением времени в стандартных b-деревьях блоки индексов для более низких значений в конечном итоге содержат мало значений с соразмерным увеличением неиспользуемого пространства, называемого «гниением». Гниль не только тратит пространство, но и замедляет скорость запросов, поскольку в любой момент времени в памяти помещается меньшая часть блоков гнилого индекса. В b-дереве, если 14538 удаляется, его индексное пространство остается пустым. В обратном индексе, если 14538 идет до прибытия 24538, 24538 может повторно использовать пространство 14538. ^{[ нужна ссылка ]}

См. также

Сноски

^ «Введение в реверс ключевых индексов: Часть I» . Блог Oracle Ричарда Фута . 14 января 2008 г. Проверено 13 апреля 2019 г.

Внешние ссылки

«Техники проектирования баз данных» . docs.oracle.com . Проверено 13 апреля 2019 г.

[1] «Введение в реверс ключевых индексов: Часть I» . Блог Oracle Ричарда Фута . 14 января 2008 г. Проверено 13 апреля 2019 г.

[1]