Вариант 1 ввода данных индекса

Question

Одним из трех вариантов того, что хранить в качестве записи данных в индексе, является запись данных k*, которая является фактической записью со значением ключа поиска k. Мой вопрос: если вы собираетесь хранить фактическую запись в индексе, то какой смысл создавать индекс?

Answer 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 Стоимость выражается в терминах обращений к странице, потому что операции ввода-вывода из / во второе хранилище являются самыми дорогими с точки зрения времени (мы игнорируем стоимость сканирования всей страницы в основной памяти, но мы рассматриваем только стоимость доступа к нему).