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

Эта статья про обратный индекс (СУБД). Для обратного индекса (поисковая система) см. Индекс (поисковая система).

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

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

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

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

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

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

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

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

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

Смотрите также

Сноски

  1. ^ «Введение в индексы с обратным ключом: Часть I». Блог Ричарда Фута Oracle. 2008-01-14. Получено 2019-04-13.

внешняя ссылка