Вариант 1 ввода данных индекса
Одним из трех вариантов того, что хранить в качестве записи данных в индексе, является запись данных k*, которая является фактической записью со значением ключа поиска k. Мой вопрос: если вы собираетесь хранить фактическую запись в индексе, то какой смысл создавать индекс?
1 ответ
Это крайний случай, потому что он на самом деле не соответствует разделению записей данных между записями данных (хеш-файл является примером этого случая).
(М. Лензерини, Р. Росати, Системы управления базами данных: файловый менеджер Access и оценка запросов, Римский университет "La Sapienza", 2016)
Альтернатива 1 часто используется для прямой индексации, например, в B-деревьях и хеш-индексах (см. Также Oracle, Создание доменных индексов)
Давайте сделаем конкретный пример.
У нас есть отношение R(a,b,c)
и у нас есть кластерное дерево B+-using, использующее альтернативу 2 для ключа поиска a
, Поскольку дерево сгруппировано, отношение R
должны быть отсортированы по a
,
Теперь давайте предположим, что общий запрос для отношения
SELECT *
FROM R
WHERE b > 25
поэтому мы хотим создать еще один индекс для эффективной поддержки запросов такого типа.
Случай 1 - кластерное дерево с альт. 2
Мы знаем, что кластерные деревья B+-with с альтернативой 2 эффективны с запросами диапазона, потому что им нужно просто найти первый хороший результат (скажем, тот, который имеет b=25
), затем сделайте 1-страничный доступ к странице отношения, на которую указывает этот результат, и, наконец, отсканируйте эту страницу (и, в конечном счете, некоторые другие страницы), пока записи не попадут в заданный диапазон.
Подводить итоги:
- Ищите первый хороший результат в дереве. Стоимость: журналƒ(ℓ)
- Используйте найденный указатель, чтобы перейти на определенную страницу. Стоимость: 1
- Сканирование страницы и других возможных страниц. Стоимость: Num. соответствующих страниц
Окончательная стоимость (выраженная в терминах доступа к странице)
журналƒ(ℓ) + 1 + # релевантных страниц
где ƒ
это разветвление и ℓ
количество листьев.
К сожалению, в нашем случае дерево по ключу поиска b
должно быть некластеризованным, потому что отношение уже отсортировано по a
Случай 2 - некластерное дерево с альт. 2 (или 3)
Мы также знаем, что деревья B+- не так эффективны в запросах диапазона, когда они некластеризованы. Фактически, имея дерево с альтернативой 2 или 3, в дереве мы будем хранить только указатели на записи, поэтому для каждого результата, попадающего в диапазон, нам нужно будет получить доступ к странице на другой потенциальной странице (потому что отношение имеет другой порядок относительно индекса).
Подводить итоги:
- Ищите первый хороший результат в дереве. Стоимость: журналƒ(ℓ)
- Затем просканируйте лист (и, возможно, другие листы) и сделайте другой доступ к странице для каждого кортежа, попадающего в диапазон. Стоимость: Num. других соответствующих листьев + число. соответствующих кортежей
Окончательная стоимость (выраженная в терминах доступа к странице)
logƒ(ℓ) + # other-релевантные листья + # релевантные кортежи
Обратите внимание, что количество кортежей намного больше, чем количество страниц!
Случай 3 - некластерное дерево с альт. 1
Используя альтернативу 3, у нас есть все данные в дереве, поэтому для выполнения запроса мы:
- Ищите первый хороший результат в дереве. Стоимость: журналƒ(ℓ)
- Следите за сканированием листа (и, возможно, других листьев). Стоимость: Num. других соответствующих листьев
Окончательная стоимость (выраженная в терминах доступа к странице)
logƒ(ℓ) + # другие релевантные листья
это даже меньше (или самое большее равно) стоимости случая 1, но это разрешено.
Я надеюсь, что я был достаточно ясен.
NB Стоимость выражается в терминах обращений к странице, потому что операции ввода-вывода из / во второе хранилище являются самыми дорогими с точки зрения времени (мы игнорируем стоимость сканирования всей страницы в основной памяти, но мы рассматриваем только стоимость доступа к нему).