Главная » SQL, Базы данных » Плотная и неплотная индексация

0

Как уже было несколько раз отмечено, основное назначение любого индекса состоит в повышении быстродействия  выборки,  а  именно,  индекс  предназначен  для  уменьшения  количества  дисковых операций ввода—вывода, необходимых для выборки некоторой указанной  записи. По сути, эта задача выполняется с помощью указателей, а вплоть до этого момента  предполагалось, что все такие указатели представляют собой указатели на записи (т.е.  идентификаторы записей). Но фактически для достижения указанной цели достаточно, чтобы эти указатели представляли собой просто указатели на страницы (т.е. номера страниц). Верно, что  после этого для поиска требуемой записи на указанной странице система должна выполнить  некоторую дополнительную работу, которая заключается в том, что в оперативной памяти  осуществляется  поиск  данных  на  странице,  но  количество  операций  ввода—вывода  остается неизменным.

Примечание. В действительности, приведенная выше аналогия с предметным указателем книги представляет собой пример индекса, в котором указатели являются указателями на  страницы,  а не указателями на "записи" (под чем подразумеваются строки или слова).

Рассмотрим эту идею более подробно. Напомним, что любой конкретный файл имеет единственную

"физическую"  последовательность, представленную в  виде  комбинации,  во-первых,  последовательности записей на каждой странице и, во-вторых, последовательности страниц в  содержащем этот файл наборе страниц. Предположим, что хранение файла поставщиков на диске организовано таким образом, что  его  физическая  последовательность соответствует логической  последовательности, которая  определена с  помощью значений некоторого  поля, скажем,  поля  номеров поставщиков. Иными словами, допустим,  что  файл  поставщиков  кластеризован  по   этому  полю  (см.  описание  внутрифайловой кластеризации в конце раздела Г.2). Предположим  также, что для этого поля требуется индекс. В таком случае  нет  необходимости,  чтобы  этот   индекс  содержал  отдельный  элемент  для  каждой  записи  в индексированном файле (т.е. в  данном примере для каждой записи в файле поставщиков); требуется лишь предусмотреть для  каждой страницы по одному элементу, в котором указан максимальный номер поставщика на  этой странице и соответствующий номер страницы, как показано на рис. Г.12 (здесь для упрощения предполагается, что  каждая  конкретная  страница может хранить не  больше двух  записей поставщиков).

В качестве примера рассмотрим, какие  действия должны быть выполнены для выборки  данных о поставщике  S3  с  использованием этого  индекса.  Вначале  система  должна  просканировать  индекс, отыскивая первую запись с номером поставщика, большим или равным  S3. Система находит элемент индекса  для поставщика S4, который  указывает  (скажем) на  страницу р. Затем выполняется выборка страницы р и просмотр ее в оперативной памяти для  поиска требуемой записи (которая в данном примере, безусловно, будет обнаружена очень быстро).

Рис. Г. 12. Пример неплотного индекса

Индекс, подобный приведенному на рис. Г.12, принято называть неплотным— nondense (или  иногда разреженным — sparse), поскольку он не содержит по одному элементу для каждой  записи  индексированного файла. (В отличие от этого, все индексы, рассматриваемые в  данном  приложении, до этого момента были плотными — dense.) Одно из преимуществ  неплотного индекса состоит в том, что он занимает меньше места  по  сравнению с  соответствующим плотным индексом,  по  той  очевидной причине, что он содержит меньше элементов. В результате просмотр этого индекса также, скорее всего, происходит быстрее.  Недостатком  такого  индекса  может оказаться  то, что при его использовании больше нет возможности проводить проверки на наличие данных с применением лишь одного индекса (см.  краткое  замечание по  поводу выполнения проверок  на  наличие данных в  подразделе  "Способы использования индексов" выше в этом разделе).

Вообще говоря, следует отметить, что  любой конкретный  файл  может иметь  не  больше  одного неплотного  индекса,  поскольку  такой  индекс  основан  на  (уникальном)  физическом   упорядочении рассматриваемого файла. Все другие индексы обязательно должны быть плотными.

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии