ЦЕПОЧКИ УКАЗАТЕЛЕЙ

Снова предположим, как и в начале раздела Г.4, что важное значение имеет запрос: "Определить всех поставщиков из города с". Еще одним хранимым представлением, позволяющим достаточно успешно выполнять этот запрос (возможно, даже лучше по сравнению с индексом, хотя и не всегда), является представление, в котором используются цепочки указателей. Такое представление показано на рис. Г. 16. Как показано на этом рисунке, в нем используются два файла — файл поставщиков и файл городов, во многом аналогично тому, как и в индексном представлении, показанном на рис. Г.9 (но на этот раз оба файла, скорее всего, должны находиться в одном и том же наборе страниц по причинам, которые будут описаны в разделе Г.7). Но в представлении на основе цепочки указателей, показанном на рис. Г. 16, файл городов — это не индекс, а структура, которую иногда называют родительским файлом. В соответствии с этим, файл поставщиков именуется дочерним файлом и вся эта структура может рассматриваться как пример родительско-дочерней организации данных.

В данном примере родительско-дочерняя структура основана на значениях названий городов поставщиков. Родительский файл (файл городов) содержит по одной записи для каждого отдельного города поставщика, которая предоставляет значение названия города и служит в качестве головы цепочки, или кольца указателей, связывающих друг с другом все дочерние записи (поставщиков) с данными о поставщиках из этого города. Обратите внимание на то, что поле города из файла поставщиков удалено; для получения данных обо всех поставщиках (скажем, из Лондона) СУБД может выполнить поиск в файле городов записи, относящейся к Лондону, а затем пройти по соответствующей цепочке указателей.

Принципиальное преимущество этой родительско-дочерней структуры состоит в том, что алго­ритмы вставки и удаления становятся немного проще и поэтому могут оказаться более эффективными по сравнению с соответствующими алгоритмами для индекса; кроме того, такая структура, по всей видимости, может занимать меньше памяти, чем соответствующая индексная структура, поскольку каждое значение названия города присутствует в файле один и только один раз, а не повторяется многократно. Основные недостатки этой структуры перечислены ниже.

■ Какой бы город ни рассматривался, единственный способ доступа к n-му поставщику состоит в том, чтобы пройти по цепочке и обратиться также к данным о первом, втором,..., (п-1)-м поставщике. Если записи поставщиков не кластеризованы должным образом, то для каждой операции доступа потребуется выполнить отдельную операцию поиска на диске, и время, требуемое для доступа к n-му поставщику, может оказаться довольно значительным.

■ Хотя эта структура может оказаться подходящей для запроса: "Определить поставщиков из указанного города", она не способствует (фактически может даже воспрепятствовать) успешному выполнению противоположного запроса: "Определить название города, где находится указан­ный поставщик" (где поставщик указан с помощью номера поставщика). Для выполнения последнего запроса, по-видимому, потребуется хэширование или индексирование файла

поставщиков; следует отметить, что теперь родительско-дочерняя структура, основанная на номерах поставщиков, не будет иметь какого-либо смысла (объясните, почему).

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

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

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

■ Примечание. Кстати, для создания нового хэшированного файла также обычно требуется ре­организация существующего файла, если только применяемый метод хэширования не является косвенным [Г.24].

Возможны некоторые варианты этой основной родительско-дочерней структуры, например, как описано ниже.

■ Указатели могут быть сделаны двунаправленными. Одним из преимуществ этого варианта является то, что он упрощает процесс корректировки записей, необходимость которой возни­кает в результате выполнения операции удаления дочерней записи.

■ Еще одно дополнение может состоять в том, что должен быть предусмотрен указатель ("указа­тель родительской записи") от каждой дочерней записи непосредственно на соответствующую родительскую запись. Такое дополнение позволяет сократить количество переходов по цепочке, требуемых для поиска ответа на запрос: "Определить город, где находится указанный пос­тавщик" (но следует отметить, что при этом не исключается необходимость использовать хэш или индекс для обеспечения успешного выполнения данного запроса).

■ Еще один вариант состоит в том, что поле города нужно не удалить, а повторить в записях поставщиков (простая форма контролируемой избыточности). В таком случае некоторые операции выборки (например: "Определить город поставщика S4") становятся более эффективными. Но следует отметить, что указанное повышение эффективности никак не связано с применением структуры с цепочками указателей как таковой; заслуживает также внимания то, что, по-видимому, все равно потребуется применить хэш-функцию или создать индекс на номерах поставщиков.

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

структуры, в одной из которых в качестве родительского используется файл городов (как на рис. Г. 16), а в другой — файл статуса. Файл поставщиков является дочерним для обеих этих структур.