    Приложения 

     В приложениях А, Б и В собран разнообразный материал по 
различным темам. В приложении А приведен вводный обзор наиболее 
распространенных систем хранения данных и технологий доступа к данным. В 
приложении Б для демонстрации основных принципов работы существующих 
реляционных СУБД дан краткий обзор одной из коммерческих СУБД, а именно 
программного продукта DB2 фирмы IBM. Наконец, приложение В, по сути, является 
введением в логические базы данных (т.е. в СУБД, широко использующие приемы 
логического программирования). 

    Приложение А 

    Структуры хранения и методы доступа 

    А.1. Введение 

    В этом приложении представлен вводный обзор технологий физического 
хранения и осуществления доступа к данным, хранящимся на диске. (Далее под 
термином диск будут подразумеваться все устройства хранения данных прямого 
доступа, т.е. прежде всего традиционные жесткие диски с подвижными магнитными 
головками, внешние запоминающие устройства большой емкости, оптические диски и 
др.) Предполагается, что читатель знаком с основами архитектуры дисков и 
такими понятиями, как время поиска, время доступа, цилиндр, трек (или 
дорожка), головка чтения/записи и т.д. Существуют достаточно подробные и 
полезные руководства по этой тематике, например [А.4].	* 
    Внимание специалистов к структурам хранения и методам доступа вызвано 
очень медленной оперативной памяти. Типичные значения времени поиска и доступа 
к диску равняются приблизискоростью доступа к диску по сравнению с доступом к 
тельно 10 мс, а типичное значение интенсивности (скорости) передачи данных с 
диска— 5— 10 млн байт/с. Для оперативной памяти значение времени поиска и 
доступа на четыре-пять порядков ниже, а интенсивность передачи данных — выше, 
причем независимо от типа сравниваемого диска. Основной целью повышения 
производительности является минимизация числа дисковых операций ввода-вывода 
данных. В этом приложении описаны основные технологии, разрабатываемые для 
достижения этой цели, т.е. методы оптимального упорядочения данных на диске с 
минимальным числом операций ввода-вывода, необходимых для доступа к заданной записи. 
    Как упоминалось ранее, любое упорядочение (расположение) данных на диске 
называется структурой хранения. Можно организовать самые разные структуры 
хранения, обладающие различной производительностью и оптимальные для различных 
способов использования. Однако не существует идеальной структуры хранения, 
которая была бы оптимальна для любых задач. Исходя из этого, можно заключить, 
что совершенная СУБД должна содержать несколько разных структур хранения для 
различных частей системы. Кроме того, следует также предусмотреть возможность 
изменения структуры хранения по мере изменения требований к производительности системы. 
    В целом приложение А построено таким образом. В следующем за введением 
разделе (А.2) дается обзор процесса локализации и доступа к отдельной записи, 
а также основных компонентов программного обеспечения, вовлеченных в этот 
процесс. (Везде, где речь идет о структурах хранения данных, вместо 
традиционной терминологии в этом приложении используется терминология, 
принятая при работе со структурами хранения, т.е. файлы, записи и т.д.) В 
следующем разделе (А.З) подробно описываются понятия диспетчер файлов (file 
manager) и диспетчер дисков (disk manager). При первом чтении разделы А.2 и 
А.З можно пропустить, поскольку изложенный в них материал не обязателен для 
понимания последующих разделов. Однако разделы А.4-А.7 пропускать не 
рекомендуется, так как в них представлена наиболее важная часть этой главы — 
широко используемые в настоящее время технологии структур хранения: 
индексирование, хеширование, создание цепочек указателей и сжатие. Наконец, в 
разделе А.8 дается краткое заключение. 

    674	Приложения 


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


    А.2. Доступ к базе данных: обзор 

    Прежде чем начать описание структур хранения, следует вкратце указать 
основные этапы процесса доступа к базе данных. Поиск и предоставление данных 
пользователю осуществляется с помощью нескольких программ доступа к данным. 
Конечно, отдельные детали работы этих программ в разных СУБД могут значительно 
отличаться, но в целом работа СУБД построена стандартным образом и включает 
три основных этапа (рис. АЛ). 
    1. Сначала в СУБД определяется искомая запись, а затем для ее извлечения 
запрашивается диспетчер файлов. (Для простоты изложения здесь предполагается, 
что в данной СУБД запись может быть указана сразу и точно. Однако на практике 
сначала следует считать и поместить в оперативную память набор записей и 
только после поиска в оперативной памяти указать нужную запись. Это, в 
сущности, означает, что приведенные ниже действия придется повторить для 
каждой записи из набора.) 
    2.  Диспетчер файлов определяет страницу, на которой находится искомая 
запись, а затем для извлечения этой страницы запрашивает диспетчер дисков. 

    Запрос хранимой записи 
    Запрос хранимой страницы 
    Дисковая операция ввода/вывода 
    Возвращение хранимой записи 
    Возвращение хранимой страницы 
    Чтение данных с диска 

    Рис. А.1.   Схема   взаимодействия   СУБД,   диспетчера файлов и 
диспетчера дисков 


    Хранимая база данных 

    3.   Наконец, диспетчер дисков определяет физическое положение искомой 
страницы на диске и посылает соответствующий запрос на ввод-вывод данных. 
Замечание. Конечно, искомая страница может уже находиться в оперативной памяти 
в результате выполнения предыдущих операций извлечения набора данных. 
Очевидно, что в таком случае не придется извлекать страницу описанным в этом 
пункте способом. 
    Иначе говоря, с точки зрения СУБД база данных выглядит как набор записей, 
которые могут просматриваться с помощью диспетчера файлов. В свою очередь, с 
точки зрения диспетчера файлов база данных выглядит как набор страниц, которые 
могут просматриваться с помощью диспетчера дисков. Наконец, диспетчер дисков 
участвует в непосредственной работе с диском. Более подробно эти этапы 
описываются ниже. 

    Диспетчер дисков 

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

    Приложение А. Структуры хранения и методы доступа 675 

    Для выполнения этих операций необходимо знать значения физических адресов 
на диске. Например, если диспетчер файлов запрашивает некоторую страницу р, 
для ее извлечения диспетчеру дисков необходимо знать, где конкретно находится 
страница р на физическом диске. Однако "пользователю" диспетчера дисков, т.е. 
диспетчеру файлов, не обязательно знать физические адреса. Вместо этого 
диспетчеру файлов достаточно рассматривать диск как набор страниц 
фиксированного размера (т.е. набор "ячеек" памяти одинакового размера) с 
уникальным идентификационным номером набора страниц. Каждая страница, в свою 
очередь, обладает уникальным внутри данного набора идентификационным номером 
страницы, причем наборы не имеют общих страниц. Соответствие физических 
адресов на диске и номеров страниц достигается с помощью диспетчера дисков. 
Главным (и не единственным) преимуществом такой организации является изоляция 
программного кода, зависящего от конкретного устройства диска, внутри одного 
из компонентов системы, а именно внутри диспетчера дисков, В таком случае все 
компоненты высокого уровня, в частности диспетчера файлов, могут быть 
аппаратно независимыми. 
    Как уже упоминалось выше, все страницы диска делятся на несвязанные 
наборы. Один из таких наборов, набор пустых страниц, содержит все имеющиеся 
свободные страницы, которые в данный момент не используются для размещения 
данных (набор пустых страниц также называется свободным пространством на 
диске). Введение или освобождение страниц в/из наборов страниц осуществляется 
диспетчером дисков по запросу диспетчера файлов. Ниже перечислены основные 
операции, выполняемые диспетчером дисков с наборами страниц, т.е. операции, на 
выполнение которых поступил запрос со стороны диспетчера файлов, 
    •   Извлечь страницу/? из набора страниц s, 
    •   Заменить страницу/? из набора страниц 5. 
    •  Добавить новую страницу в набор страниц s (т.е. извлечь одну страницу 
из набора пустых страниц и возвратить новую страницу с номером р). 
    •  Удалить страницу р из набора страниц 5 (т.е. возвратить одну страницу с 
номером р в набор пустых страниц). 
    Первые две операции являются базовыми операциями ввода-вывода на уровне 
страниц, а две другие позволяют увеличивать или уменьшать наборы страниц по 
мере необходимости. 

    Диспетчер файлов 

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

    Замечание. Хотя по изложенным ниже причинам сама по себе СУБД не управляет 
наборами страниц, для ее работы часто бывают нужны некоторые сведения о 
наборах страниц. Например, такие сведения необходимы, когда два сохраненных 
файла размещаются в одном и том же наборе страниц или когда две записи 
размещаются на одной странице. 

    Каждый хранимый файл имеет имя (file name) или идентификационный номер 
(file ID), уникальные в данном наборе страниц. А каждая хранимая запись, в 
свою очередь, обладает идентификационным номером записи (record number или 
record ID), уникальным, по крайней мере, в пределах данного хранимого файла. 
(На самом деле обычно идентификационные номера уникальны не только для данного 
файла, но и для всего диска. Дело в том, что их обычно составляют на основе 
комбинации номера страницы и некоторого значения, уникального внутри данной 
страницы. Подробнее это описано ниже.) 

    676	Приложения 

    Далее перечислены основные операции с файлами, выполняемые диспетчером 
файлов, т.е. операции, на выполнение которых поступил запрос со стороны СУБД. 
    •	Извлечь хранимую запись г из хранимого файла/ 
    •	Заменить хранимую запись г в хранимом файле/ 
    •	Добавить новую хранимую запись г в хранимый файл/ 
    •	Удалить хранимую запись г из хранимого файла/ 
    •	Создать новый хранимый файл/ 
    •	Удалить хранимый файл/ 
    С помощью этих простых операций с файлами в СУБД можно создавать структуры 
хранения и управлять ими (об этом речь идет ниже). 

    Замечание. В одних системах диспетчер файлов является компонентом 
операционной системы, а в других — поставляется в составе СУБД. Однако для 
выяснения принципов его работы такое различие не существенно. При этом следует 
заметить, что диспетчеры файлов, содержащиеся в составе операционных систем, 
не всегда наилучшим образом удовлетворяют требованиям, предъявляемым 
специализированными приложениями, например СУБД. Более подробно этот вопрос 
обсуждается в [А.44]. 

    Кластеризация 

    Нельзя завершить этот краткий обзор без упоминания технологии 
кластеризации данных. В ее основе лежит принцип как можно более близкого 
физического размещения на диске логически связанных между собой и часто 
используемых данных. Физическая кластеризация данных — чрезвычайно важное 
условие высокой производительности, что можно продемонстрировать следующим 
примером. Допустим, что наиболее часто используется хранимая запись rl 
страницы pi, для работы с которой также требуется вызывать хранимую запись г2 
страницы р2. Тогда возможно возникновение следующих ситуаций: 
    1. Если страницы р! и р2 совпадают, то для доступа к записи г2 не 
потребуется выполнять еще одну физическую операцию ввода-вывода, поскольку 
нужная страница уже будет находиться в оперативной памяти. 
    2.   Если страницы р! и р2 не совпадают, но физически размещаются 
достаточно близко, например смежные страницы, то для доступа к записи г2 
потребуется выполнить еще одну физическую операцию ввода-вывода (если, 
конечно, страница р2 еще не находится в оперативной памяти). Однако, поскольку 
головка чтения/записи уже будет находиться в непосредственной близости от 
нужного положения, время поиска будет очень малым. А если страницы р! и р2 
находятся на одном цилиндре, время поиска вообще будет равно нулю. 
    В качестве примеров ниже в этом приложении часто будет рассматриваться 
база данных поставщиков и деталей. (Для простоты изложения материала далее в 
этом приложении предполагается, что отдельные данные об определенном 
поставщике и детали или группа взаимосвязанных данных о поставке каких-то 
деталей располагаются в отдельных хранимых записях на диске, за исключением 
особо оговоренных случаев.) 
    •   Если в системе часто требуется осуществлять доступ к данным о 
поставщике согласно его порядковому номеру, то все записи о поставщиках 
следует физически размещать таким образом, чтобы запись о поставщике S1 была 
возле записи S2, запись S2 — возле записи S3 и т.д. Это пример внутрифайловой 
кластеризации, когда кластеризация осуществляется в рамках одного хранимого файла. 
    •   С другой стороны, если в системе часто требуется осуществлять доступ к 
данным о поставщике и обо всех его поставках деталей одновременно, то записи о 
поставщиках и их поставках должны располагаться рядом. Например, записи о

    Приложение А. Структуры хранения и методы доступа	677 

поставках деталей поставщиком S1 должны располагаться возле записи с данными 
о самом поставщике S1, записи о поставках деталей поставщиком S2 — возле 
записи с данными о поставщике S2 и т.д. Это пример межфайловой кластеризации, 
когда охвачено сразу несколько файлов. 
    Конечно, в каждый момент времени кластеризацию файла или набора файлов 
можно осуществлять только одним из этих способов. 
    Внутрифайловую и межфайловую кластеризацию СУБД может осуществлять, 
размещая логически связанные записи на одной странице (если это возможно) или 
на смежных страницах (если это невозможно). Вот почему СУБД важно иметь 
сведения не только о сохраненных файлах, но и о страницах. При создании в СУБД 
новой записи необходимо, чтобы она с помощью диспетчера файлов была размещена 
"возле" некоторой текущей страницы, т.е. на той же или, по крайней мере, на 
логически близкой странице. В свою очередь, диспетчер дисков должен 
обеспечить, чтобы логически близкие страницы были физически близко расположены 
на диске. Подробнее это обсуждается ниже. 
    Конечно, кластеризация внутри СУБД возможна только в том случае, если 
администратор базы данных организует ее. В совершенных СУБД часто 
предусмотрено задание нескольких различных типов кластеризации данных из 
разных файлов. Администратор базы данных в таком случае может изменять 
кластеризацию внутри данного файла или набора файлов в соответствии с новыми 
требованиями, предъявляемыми к производительности СУБД. Более того, если 
кластеризация поддерживается независимо от данных, то при изменении физической 
кластеризации не потребуется вносить никаких изменений в код программ. 

    А.З. Наборы страниц и файлы 

    Как упоминалось выше, основной функцией диспетчера дисков является скрытие 
от диспетчера файлов всех деталей физических дисковых операций ввода-вывода и 
замена их логическими "страничными" операциями ввода-вывода. Эта функция 
диспетчера дисков называется управлением страницами. Ниже приведен пример 
использования этой функции. 
    Предположим, что в рассматриваемом примере с поставщиками и поставками в 
каждой таблице требуется логически упорядочить записи согласно ключевому полю. 
(Следует отметить, что термин "ключевое ноле" не имеет четкого определения, 
если только оно не является составным. Например, данные о поставках деталей 
могут быть упорядочены либо по номеру заказа о поставке конкретной детали, 
либо как-то иначе.) Для простоты изложения допустим, что каждый хранимый файл 
занимает один набор страниц, для каждой записи требуется отдельная страница, а 
общее количество страниц на диске 65 536 = 64 К (такое предположение не так уж 
бессмысленно, как может показаться на первый взгляд). Ниже приведена примерная 
последовательность наиболее типичных действий. 
    1. На начальном этапе база данных совсем не содержит данных. В ней имеется 
набор пустых страниц, в котором содержатся все страницы диска, за исключением 
страницы "нуль", о которой речь пойдет ниже. Все остальные страницы 
последовательно пронумерованы, начиная с номера "один". 
    2. Для размещения записей с данными о поставщиках диспетчер файлов создаст 
набор страниц и разместит на них данные о поставщиках S1-S5. Для этого 
диспетчер дисков переместит страницы 1-5 из набора пустых страниц и пометит их 
как "набор страниц поставщиков". 
    3.   Аналогичные действия будут выполнены для размещения данных о деталях 
и поставках. В результате будет создано четыре набора страниц: о поставщиках 
(страницы 1— 5), о деталях (страницы 6-11), о поставках (страницы 12-23) и 
набор пустых страниц (страницы 24,25,26 и т.д.). Размещение страниц 
схематически показано на рис. А.2. 

    678	Приложения 

    Теперь рассмотрим выполнение различных действий. 
    4.  Допустим, необходимо добавить новую запись с данными о новом 
поставщике S6. Для этого диспетчер файлов вставляет новую хранимую запись, а 
диспетчер дисков осуществляет поиск первой пустой страницы (в данном примере 
это страница 24), а затем добавляет ее к набору страниц поставщиков. 

    -OJ	JJ S1	JJ S2	JJ S3	АЛ S4	_LJ S5 
    _ej PI	JJ Р2	JJ РЗ	JJ Р4	ни Р5	±LJ Р6 
    J2J S1/P1	J3J S1/P2	Ли S1/P3	J5J S1/P4	16J S1/P5	1LJ S1/P6 
    ли S2/P1	19J S2/P2	20J S3/P2	Ш S4/P2	22J S4/P4	23J S4/P5 
    24J	_25J	26J	27J	28J	29J 
    ^^		__	г-~~~^~ —	— - —— ——	_^-J 
    _- ————— ^              \ 

    Рис. А.2. Размещение страниц на диске после создания базы данных и 
начальной загрузки данных о поставщиках и деталях 

    5.  Если необходимо удалить хранимую запись с данными о поставщике S2, 
диспетчер файлов удаляет ее, а диспетчер дисков возвращает страницу поставщика 
S2 (страница 2) в набор пустых страниц. 
    6.  Если теперь необходимо вставить новую запись с данными о детали 
(деталь Р7), диспетчер файлов вставит ее, а диспетчер дисков найдет первую 
пустую страницу в наборе пустых страниц (страница 2) и добавит ее в набор 
страниц о деталях. 
    7.   Если нужно удалить хранимую запись с данными о поставщике S4, 
диспетчер файлов удалит ее, а диспетчер дисков возвратит страницу поставщика 
S4 (страница 4) в набор пустых страниц. 
    Размещение страниц после проведенных действий схематически показано на 
рис. А.З. Рассматривая этот пример, можно сделать вывод о том, что после 
выполнения нескольких самых обычных действий нельзя гарантировать, что 
логически близкие страницы будут физически располагаться одна возле другой. 
Поэтому логическую последовательность страниц в данном наборе следует задавать 
с помощью указателей, а не на основе их физически близкого размещения на 
диске. Для этого каждая страница содержит заголовок страницы с информацией о 
физическом дисковом адресе страницы, которая логически следует за данной 
страницей (рис. А.4). 
    Ниже перечислены некоторые особенности использования указателей. 
    •   Заголовки страниц, в частности указатели "следующей страницы", 
обрабатываются диспетчером дисков и должны быть скрыты для диспетчера файлов. 
    •  Как уже объяснялось выше, желательно сохранять логически связанные 
страницы в физически близких местах диска (настолько, насколько это возможно). 
Поэтому диспетчер дисков обычно размещает или удаляет страницы в наборах не по 
одной, а целыми группами физически связанных страниц, или блоками (также 
называемыми экстентами; экстент— непрерывная область на диске), например по 64 
страницы сразу. 

    Приложение А. Структуры хранения и методы доступа 679 


    .OJ	JJ S1	-U P7	JJ S3	JJ	_5J S5 
    jU PI	JJ P2	JJ P3	_aj P4	IflJ PS	1U P6 
    J2J S1/P1	JU S1/P2	L14J S1/P3	1LJ S1/P4	ULU S1/P5	JLJ S1/P6 
    Jll S2/P1	J9J S2/P2	JOJ S3/P2	2JJ S4/P2	22J S4/P4	23J S4/P5 
    24J S6	Jll	J6J	1LJ	28J	29J 
    J||?>--- — I			k--i_^- ———		u^^— I 
    
    
    Рис. А.З, Размещение страниц на диске после вставки и удаления записей 

    _OJ 
    б т   г7 тт   иг si    i_a_-LJ    Iю ю I    in 111 
    Р1 
    181       Ц9. S2/P1 
    24J       IX 251 
    S6 
    Р2 
    РЗ 
    Р4 
    Р5 
    UЩ Р6 
    29[    ЦО 

    Рис. А.4. Размещение страниц на диске, показанное на рис. А.З, с 
указателями "следующей страницы" в правом верхнем углу каждой страницы 

    •   Возникает вопрос, каким образом диспетчер дисков получает информацию о 
размещении различных наборов страниц, точнее, о размещении первой страницы 
каждого набора страниц? (Достаточно знать расположение только первой страницы 
из набора, поскольку положение второй и последующих страниц можно определить с 
помощью указателей в заголовках страниц.) Для этого на диске организуется 
отдельное место, в котором сохраняется вся необходимая информация. Это место, 
точнее, страница часто называется таблицей содержания диска, каталогом диска, 
каталогом наборов страниц или просто страницей 0 (страницей "нуль"). На ней 
перечислены все имеющиеся на данном диске наборы страниц вместе с указателями 
на первые страницы каждого из наборов (рис. А.5). 
    Диспетчер дисков скрывает все подробности физической организации 
ввода-вывода от диспетчера файлов и предоставляет ему возможность вести работу 
только на логическом уровне. Точно так же диспетчер файлов скрывает все 
подробности операций ввода-вывода на основе страниц от СУБД и предоставляет ей 
возможность вести работу только с хранимыми записями и файлами. Такая работа, 
выполняемая диспетчером файлов, называется управлением хранимыми записями. Она 
рассматривается ниже на примере базы данных поставщиков и деталей. 
    Предположим (теперь это более реальное предположение), что на одной 
странице может размещаться не одна, как в предыдущем примере, а несколько 
хранимых записей. Однако логический порядок расположения записей остается 
прежним, т.е. согласно номеру поставщика. В качестве примера выполним 
перечисленные ниже действия. 

    680 Приложения 

    1.  Вставим пять хранимых записей поставщиков S1-S5 и сохраним их на 
странице/? так, как показано на рис. А.6. Обратите внимание, что на странице р 
остается достаточно свободного пространства. 

    0			X 
    
    
    Набор страниц	Адрес первой страницы набора 
    Свободное пространство	4 
    Поставщики	1 
    Детали	6 
    Поставки	12 
    
    
    P		(Остальная часть заголовка) 
    S1	Smith		20	London	S2 Jones    10   Paris 
    S3	Blake		30	Paris	S4   Clark    20  London 
    S5	Adams		30	Athens 
    
    
    Рис. А.5. Каталог диска (страница 0) 

    Рис. А.6. Размещение записей на странице р после начальной загрузки пяти 
записей с данными о поставщиках S1-S5 

    2.  Допустим, что СУБД необходимо вставить новую запись, например для 
нового поставщика S9. Диспетчер файлов сохранит эту запись на странице р 
(поскольку на ней есть свободное пространство) вслед за сохраненной записью S5. 
    3.   А теперь предположим, что СУБД необходимо удалить запись поставщика 
S2. Диспетчер файлов удалит запись S2 со страницы р и, чтобы заполнить 
образовавшийся пустой промежуток между записями S1 и S3, "передвинет" страницы 
S3, S4, S5 и S9. 
    4.   Если необходимо СУБД вставить новую запись для другого поставщика S7, 
диспетчер файлов разместит эту запись на странице р (поскольку в ней есть 
свободное пространство) вслед за записью S5, но перед записью S9, сдвигая ее 
вниз. Полученное расположение записей схематически показано на рис. А.7. 

    Рис. А.7. Размещение записей на странице р после вставки записи S9, 
удаления записи S2 и вставки записи S7 

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

    Р		(Остальная часть заголовка) 
    S1	Smith		20	London	S3	Blake	20	Paris 
    S4	Clark		20	London	S5	Adams	10	Athens 
    S7					S9			.... 
    
    
    Приложение А. Структуры хранения и методы доступа 681 

    Как отмечалось выше, хранимые записи идентифицируются с помощью 
идентификационного номера записи (record ID — RID), На рис. А.8 схематически 
показана структура такого номера. Идентификационный номер записи г состоит из 
двух частей — номера страницы г, на которой данная запись находится, и байта 
смещения слота от конца страницы р, который, в свою очередь, содержит байт 
смещения записи г от начала страницы р. Эта схема является компромиссом между 
быстротой непосредственной адресации и гибкостью косвенной адресации. 
Действительно, записи внутри страницы могут сдвигаться вверх или вниз так, как 
показано на рис. А.7 и А.8, без изменения идентификационных номеров записей 
(изменяются только значения локальных смещений в конце страницы). К тому же, 
если известен идентификационный номер записей, доступ к данной записи 
осуществляется очень быстро, поскольку используется только доступ к данной 
странице, (Желательно, чтобы идентификационные номера записей вовсе не 
изменялись, поскольку они могут использоваться в качестве указателей записей 
во всей базе данных, например как индексы. При изменении одного из 
идентификационных номеров записи может понадобиться изменить все связанные с 
ним указатели во всей базе данных.) 

    Страница р 
    Номер      ; Смещение страницы i слота от конца страницы 

    Рис. А.8, Структура идентификационного номера записи (record ID — RID) 

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

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

    682 Приложения 

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

    А.4. Индексирование 

    Рассмотрим в качестве примера таблицу с данными о поставщиках, а также 
часто используемый и потому очень важный запрос типа "Найти всех поставщиков 
из города С", где С — некий параметр. При таких условиях администратор базы 
данных может выбрать способ сохранения данных, схематически показанный на рис. 
А.9. Он основан на двух хранимых файлах: файле с данными о поставщиках и файле 
с данными о 

    Приложение А. Структуры хранения и методы доступа	683 

    городах; файлы могут размещаться в различных наборах страниц. 
Предполагается, что в файле городов используется упорядочение по алфавитному 
перечню их названий, т.е. по ключевому полю CITY (город) с RID-указателями на 
соответствующие записи в файле поставщиков. 

    Файл поставщиков (данные) 
    Файл городов (индекс) 
    V 
    S1	Smith	20	London 
    S2	Jones	10	Paris 
    S3	Blake	30	Paris 
    S4	Clark	20	London 
    S5	Adams	30	Athens 

    Рис. А,9. Индексирование файла поставщиков по полю CITY файла городов 

    Ниже приведены стратегии, которые можно применить для поиска всех 
поставщиков из Лондона. 
    1.  Найти весь файл поставщиков, найти все записи, для которых названием 
города является строка London (Лондон). 
    2.   Найти файл городов со строкой London (Лондон), а затем согласно 
указателям извлечь все соответствующие записи из файла поставщиков. 
    Если доля всех поставщиков из Лондона по отношению к общему количеству 
поставщиков достаточно мала, вторая стратегия будет гораздо эффективнее 
первой. Дело в том, что, во-первых, СУБД известна физическая 
последовательность записей в файле городов (поиск будет прекращен после 
извлечения следующего за Лондоном в алфавитном порядке названия города). А 
во-вторых, даже если придется просмотреть файл городов полностью, для такого 
поиска потребуется гораздо меньше операций ввода-вывода, поскольку физический 
размер файла городов меньше, чем размер файла поставщиков из-за меньшего 
размера записей. 
    В рассматриваемом примере файл городов называется индексным файлом или 
индексом по отношению к файлу поставщиков, и наоборот, файл поставщиков 
индексирован (называется индексированным файлом) по отношению к файлу городов. 
Индексный файл — это хранимый файл особого типа, в котором каждая запись 
состоит из двух значений, а именно данных и RID-указателя. Данные необходимы 
для некоторого поля (индексного поля) из индексированного файла, а указатель — 
для связывания с соответствующей записью индексированного файла. Индексное 
поле также называется индексным ключом (index key), но в данной книге такое 
название использоваться не будет. 

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

    Терминология, Если индексирование организовано на основе ключевого поля, 
например на основе поля S# файла поставщиков, то индекс называется первичным. 
А если индекс организован на основе другого поля, например поля CITY, как в 
рассматриваемом примере, то он называется вторичным. Кроме того, индекс, 
организованный на основе ключевого поля или другого ключа, называется уникальным. 

    684 Приложения 


    Как используются индексы 

    Основным преимуществом использования индексов является значительное 
ускорение процесса выборки или извлечения данных, а основным недостатком — 
замедление процесса обновления данных. Действительно, при каждом добавлении 
новой записи в индексированный файл потребуется также добавить новый индекс в 
индексный файл. В качестве примера рассмотрим, какие изменения потребуется 
внести в СУБД, в которой один из поставщиков, например S2, переехал из Парижа 
в Лондон (см. рис. А.9). В любом случае при выборе некоторого поля для 
индексирования необходимо выяснить, что более важно для данной СУБД: скорость 
извлечения данных или скорость обновления? 
    В этом приложении рассматривается пример СУБД, для которой наиболее 
существенным фактором является скорость извлечения данных. 
    Индексы можно использовать двумя совершенно разными способами. Во-первых, 
их можно использовать для последовательного доступа к индексированному файлу, 
где термин последовательный обозначает "последовательность, заданную 
значениями индексного поля". Например, индекс CITY из рассматриваемого примера 
будет определять доступ к записям файла поставщиков согласно алфавитному 
перечню городов. Во-вторых, индексы могут использоваться для прямого доступа к 
отдельным записям индексированного файла на основе заданного значения 
индексного поля. Пример запроса "Найти поставщиков из Лондона" является 
типичным примером такого использования индексов. 
    Для практического применения эти два основных подхода можно обобщить 
следующим образом. 
    •   Последовательный доступ. Индекс может использоваться для составления 
запросов на поиск набора записей, например: "Найти поставщиков из городов, 
названия которых начинаются с буквы из некоторого диапазона" (например, от Л 
до Р). В этом случае можно выделить два отдельных варианта: "Найти поставщиков 
из города, название которого начинается с буквы, предшествующей некоторой 
букве (или следующей за некоторой буквой)" и "Найти поставщиков из города, 
название которого размещается первым (последним) в алфавитном перечне". 
    •  Прямой доступ. Такое индексирование может оказаться полезным при 
составлении запросов по спискам, а именно: "Найти поставщиков из городов, 
находящихся в заданном списке" (например, из Лондона, Парижа и Нью-Йорка). 
    В дополнение к этому существуют запросы для проверки наличия значений, 
которые могут быть выполнены без обращения к индексированному файлу. Например, 
результатом выполнения запроса "Есть ли поставщики в Афинах" будет ответ "Да", 
если в индексе городов CITY есть запись о городе Афины. 
    Хранимый файл может иметь несколько индексов: например, хранимый файл 
поставщиков может иметь индекс CITY (город) и индекс STATUS (статус) (рис. 
АЛО). Они могут как раздельно, так и совместно использоваться для более 
эффективного доступа к записям о поставщиках. В качестве иллюстрации 
"совместного" использования индексов рассмотрим запрос "Найти поставщиков из 
Парижа со статусом 30". Если согласно индексу CITY для поставщиков из Парижа 
найдены записи с RID-указателями г2 и гЗ, а согласно индексу STATUS — записи с 
RID-указателями гЗ и г5, то на основе сравнения этих двух наборов записей 
становится ясно, что условиям запроса удовлетворяет только запись с данными о 
поставщике гЗ. Только после этого в СУБД будет организован доступ к файлу 
поставщиков и будет извлечена данная запись. 

    Приложение А. Структуры хранения и методы доступа	685 

    Индекс CITY 
    файл с данными о поставщиках 
    Индекс STATUS 
    V 
    S1 
    S2 
    S3 
    S4 
    S5 
    Smith 
    Jones 
    Blake 
    Clark 
    Adams 
    20 
    10 
    30 
    20 
    30 
    London 
    Paris 
    Paris 
    London 
    Athens 
    10 
    20 
    20 
    30 
    30 

    Рис, А, 10, Индексирование файла поставщиков одновременно по полям CITY и STATUS 

    Терминология. Индексы часто называют инвертированными списками. Дело в 
том, что если файл поставщиков (см. рис. АЛО) имеет традиционную структуру 
списка набора значений полей для каждой записи, то индекс содержит список 
набора записей для каждого значения индексированного поля. Кроме того, файл с 
индексами по каждому полю иногда называется полностью инвертированным. 

    Индексирование на основе комбинации полей 

    Индекс можно также создать на основе комбинации двух или более полей. 
Например, на рис. А. 11 показана схема индексирования файла поставщиков на 
основе комбинации полей CITY и STATUS. При такой организации в СУБД можно 
выполнить запрос типа "Найти поставщиков из Парижа со статусом 30" на основе 
однократного просмотра с помощью одного индекса. Если бы вместо комбинации 
использовалась пара индексов на основе полей CITY и STATUS, то для выполнения 
запроса потребовалось бы два отдельных просмотра. Более того, скорость 
выполнения запроса может сильно зависеть от последовательности выполнения 
отдельных просмотров по двум индексам. К тому же, порой бывает довольно сложно 
определить, какой порядок индексов приведет к более быстрому выполнению 
данного запроса. 

    Индекс CITY /STATUS 
    Файл с данными о поставщиках 
    S1	Smith	20	London 
    S2	Jones	10	Paris 
    S3	Blake	30	Paris 
    S4	Clark	20	London 
    S5	Adams	30	Athens 

    Рис, A.11. Индексирование файла поставщиков на основе комбинации полей 
CITY и STATUS 

    Обратите внимание, что комбинированный индекс CITY/STATUS может также 
служить индексом по одному полю CITY, поскольку все записи в комбинированном 
индексе расположены по крайней мере последовательно. (Если потребуется также 
индексирование по полю STATUS, необходимо использовать второй индекс.) Вообще, 
индекс на основе комбинации полей Fl, F2, F3,,.. Fn (в перечисленном порядке) 
может использоваться либо для отдельного индексирования по полю F1, либо для 
индексирования на основе комбинации F1F2 (или F2F]), либо для индексирования 
на основе комбинации F1F2F3 (или любого их сочетания) и т.д. Таким образом, 
становится понятно, что для создания достаточно сложного индексирования может 
потребоваться совсем немного индексных полей (подробнее это изложено в 
упражнениях в конце приложения). 

    686 Приложения 


    Плотное и неплотное индексирование 

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

    Замечание. Фактически в приведенной ранее аналогии с предметным указателем 
обыкновенной книги уже отмечалось, что подобные указатели являются указателями 
страниц, а не "записей". 

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

    Индекс S# 
    
    """ — *1	S1	Smith	20	London 
    S2	Jones	10	Paris 
    ^ — + ^->	S3	Blake	30	Paris 
    S4	Clark	20	London 
    S5	Adams	30	Athens 
    
    страница р - 1 
    страница р 
    страница р + 1 

    Рис. А.12. Пример использования неплотного индекса 

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

    Приложение А. Структуры хранения и методы доступа 687 

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

    Структуры типа Б-дерева 

    Одним из наиболее важных и распространенных индексов является структура 
типа Б-дерева (B-tree). Хотя не существует универсальной структуры хранения, 
оптимальной для любых приложений, все же нет сомнений, что для использования в 
простых системах следует выбирать индекс бинарного типа. Благодаря тому что 
бинарные индексы обладают в большинстве случаев сравнительно высокой 
производительностью, их использование предусмотрено почти во всех СУБД, а 
некоторые СУБД работают только на основе такого индекса. 
    Прежде чем дать описание структуры типа Б-дерева, следует разъяснить суть 
таких основных понятий, как многоуровневый или древовидный индекс. 
    Причина необходимости создания структуры типа Б-дерева заключается в 
желании избежать обязательного просмотра всего содержимого индексированного 
файла согласно его физической последовательности. Дело в том, что если 
индексированный файл имеет большой размер, то и его индекс также очень велик. 
Поэтому последовательный просмотр даже одного только индекса требует больших 
затрат времени. Разрешить эту проблему можно тем же способом, что и раньше: 
рассмотреть индексный файл как обычный хранимый файл и создать для него еще 
один индекс. Эту операцию можно осуществлять повторно нужное количество раз 
(обычно она применяется трижды, поскольку создание большого количества 
иерархических уровней индексирования требуется для очень больших файлов). При 
этом индекс на каждом из уровней будет неплотным по отношению к нижнему 
индексируемому уровню (он обязательно должен быть неплотным, иначе такая 
структура бессмысленна, так как уровень п содержал бы такое же количество 
записей, что и уровень п+1, а дл я просмотра потребовалось бы такое же 
длительное время). 
    Структура типа Б-дерева является частным случаем индекса древовидного типа 
и впервые описана в статье Байера (Вауег) и Мак-Крайта (McCreight) в 1972 году 
[А. 16]. С тех пор Байером и другими исследователями было предложено множество 
вариантов реализации этой идеи. В результате бинарные индексы различных типов 
стали широко использоваться во всех современных СУБД. В данной книге в 
качестве примера рассматривается вариант, предложенный Кнутом (Knuth) [A.I]. 
(Следует отметить, что индексная структура в методе доступа к виртуальным 
структурам хранения (Virtual Storage Access Method — VSAM), разработанного 
специалистами фирмы IBM, весьма близка структуре, предложенной Кнутом. Однако 
индекс VSAM был разработан независимо и обладает некоторыми дополнительными 
характеристиками, например способностью к сжатию. Один из предшественников 
индекса VSAM был описан еще в 1969 году [А. 19].) 
    Согласно терминологии VSAM в варианте Кнута индекс состоит из двух частей: 
набора последовательностей и набора индексов. 
    •  Набор последовательностей включает одноуровневый индекс для реальных 
данных, который обычно является плотным, но может быть и неплотным, если в 
индексированном файле проведена кластеризация на основе индекса. Записи внутри 
индекса сгруппированы по страницам, а страницы связаны в цепочку таким

    688	Приложения 

образом, чтобы логическое упорядочение на основе индекса осуществлялось внутри 
первой страницы, затем с помощью физической последовательности записей внутри 
второй страницы этой последовательной цепочки и т.д. Таким образом, с помощью 
набора последовательностей можно организовать быстрый последовательный доступ 
к индексированным данным. 
    •   Набор индексов, в свою очередь, обеспечивает быстрый непосредственный 
доступ к набору последовательностей (а значит, и к данным). По сути, набор 
индексов является древовидным индексным файлом для набора последовательностей 
или, строго говоря, индексом со структурой Б-дерева. Комбинация набора 
индексов и набора последовательностей называется структурой типа Б-плюс-дерева 
(B-plus tree или B+-tree). На самом верхнем уровне такого индекса находится 
только один элемент структуры (страница, содержащая множество записей), 
который называется корневым (root). 
    На рис. А. 13 показан простой пример такой структуры. Числа 6, 8, 12, ... 
97, 99 являются значениями индексированного поля F. Корневой элемент содержит 
два значения поля F (50 и 82) и три указателя (номера страниц). Данные со 
значением поля F, равным или меньшим 50, могут быть найдены с помощью левого 
указателя; данные со значением поля F, большим 50 и равным или меньшим 82, — с 
помощью среднего указателя; наконец, данные со значением поля F, большим 82, — 
с помощью правого указателя. Другие элементы набора индексов следует 
интерпретировать подобным образом. Обратите внимание, что благодаря переходу 
на второй уровень по левому указателю в дальнейшем поиск по правому указателю 
будет осуществляться ко всем записям со значением поля F, большим 32 и равным 
или меньшим 50. 
    Индекс на основе Б-дерева (т.е. набор индексов), показанный на рис. А. 13, 
не реален по двум причинам. 
    •   Во-первых, элементы Б-дерева обычно не содержат одинакового количества 
записей с данными. 
    •   Во-вторых, элементы Б-дерева обычно содержат некоторое количество 
свободного пространства. 
    Вообще, "Б-дерево порядка и" содержит не менее п и не более 2п записей с 
данными в каждом из элементов структуры (для каждых k записей требуется также 
k+1 указателей). Кроме того, ни одна из записей не может использоваться двумя 
разными элементами. Ниже приводится обобщенный алгоритм поиска некоторого 
значения V с помощью Б-дерева порядка п, показанного на рис. А. 13. 

    set N to the root ;	/* переход к корневому элементу */ do until N is a 
sequence-set node ;          /* выполнение цикла */ 
    /* внутри элемента */ let X, Y (X < У) be the data values in node N ; 
    /* задание краевых условий */ if V< X then set N to the left lower node of 
N ; 
    I* если V < X, перейти к левому элементу */ if X < V < Y then set N to the 
middle lower node of N ; 
    /* если X < V < У, перейти к среднему элементу */ if V > У then set N to 
the right lower node of N ; 
    I* если V > Y, перейти к правому элементу */ end ; 
    if V occurs in node N then exit	/* значение найдено */ if V does not occur 
in node N then exit    /* значение не найдено */ 

    Одним из недостатков иерархических структур является несбалансированность 
их работы после удаления или вставки некоторых элементов. Дело в том, что в 
результате таких изменений структуры элементы с реальными данными могут 
оказаться на разных уровнях и на разных расстояниях от корневого элемента. 
Поскольку во время поиска при каждом посещении элементов структуры происходит 
обращение к диску, общая продолжительность поиска в несбалансированной 
древовидной структуре может оказаться совершенно непредсказуемой. 

    Приложение А. Структуры хранения и методы доступа	689 


    Замечание. Хотя на практике для сокращения числа обращений к диску 
корневой уровень (а также некоторые другие уровни) при работе СУБД в основном 
содержится в оперативной памяти, этот недостаток все же является весьма существенным. 

    Однако замечательным преимуществом структуры типа Б-дерева является 
возможность сбалансированной вставки или удаления значений. (Вот почему для 
английского написания такого индекса, "B-tree", иногда употребляют вместо 
символа "В" эпитет "сбалансированный" (balanced).) Ниже приводится краткий 
алгоритм вставки нового значения V в структуру типа Б-дерева порядка п. Он 
рассчитан на вставку значения только лишь в набор индексов, но может быть 
достаточно просто расширен для вставки записи с данными в набор последовательностей. 
    •   На самом низком уровне набора индексов следует найти элемент 
(допустим, что это элемент /V), с которым логически связано вставляемое 
значение V. Если элемент /V содержит свободное пространство, то значение V 
вставляется в него и на этом процесс завершается. 
    •  В противном случае (если свободного пространства нет, т.е. придется 
создать еще один уровень) элемент N (допустим, что он содержит 2п индексных 
записей) разделяется на два элемента — N1 и N2. Обозначим символом S множество 
из 2п+1 значений, в котором 2п исходных значений и одно новое значение V. 
Тогда п первых значений этой логической (уже упорядоченной) последовательности 
необходимо поместить в элемент N1, п последних — в элемент N2, а среднее между 
ними значение W— в родительский элемент Р на более высоком структурном уровне. 
Впоследствии, при осуществлении поиска значения U и достижении элемента Р, 
поиск будет перенаправлен в сторону элемента N1, если U<W, либо в сторону 
элемента N2, если U>W, 
    •  Далее этот процесс следует повторить для вставки среднего значения W в 
родительский элемент Р на более высоком структурном уровне. 
    В худшем случае процесс разделения элементов структуры может продлиться 
вплоть до корневого элемента всей структуры с образованием нового 
иерархического уровня. 
    Для удаления некоторого значения следует применить аналогичный алгоритм, 
но только в обратном порядке. А для изменения значения его можно удалить, а 
затем вставить новое. 

    А.5. Хеширование 

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

    690	Приложения 


    M50I.I82M 
    Набор индексов 
    последовательностей 
    16 I 8 |12|   115118132|   1351401501   |51|52|58|   |60|62|70|   
|71|78|82|   |83|85|89|   |91|93|94|   ШШ (с указателями на III        III     
   III         III        III        III        III        III        III    
записи с реальными 
    данными) 
    Рис. А.13. Пример структуры типа Б-дерева 
    О |				Jj				Jj                              [Jj                           
  [±J									.У 
    S300	Blake	30	Paris	I									S200	Jones	10	Paris 
    и				JJ				H	Jj				UJ				»J 
    S500	Adams	30	Athens						S100	Smith	30	London	S400	Clark	20	London	I 
    N				I I 
    
    
    Рис. А.14. Пример использования хеширования 


    В качестве простой иллюстрации предположим, что у нас есть записи с 
данными о поставщиках с номерами S100, S200, S300, S400, S500 (вместо SI, S2, 
S3, S4, S5), для хранения каждой из них предназначается отдельная страница, а 
в качестве хеш-функции используется следующая: 

    хеш-адрес (т.е. номер страницу) = 
    остаток от деления на 13 числа, содержащегося в поле номера записи S# 

    Это простейший пример общего класса хеш-функций типа деление/остаток. (В 
качестве делителя следует выбирать простое натуральное число; объяснение этого 
факта выходит за рамки данной книги.) В этом примере номерами страниц для 
заданных записей будут 9, 5, \, 10 и 6 соответственно. Схематически взаимное 
расположение записей на страницах показано на рис. А. 14. 
    Из вышеизложенного ясно, что хеширование отличается от индексирования тем, 
что в файле может быть любое количество индексов, но только одна структура 
хеширования или, иначе говоря, одно хеш-поле. (В этом замечании 
предполагается, что хеширование является прямым, однако в файле можно задать 
любое количество косвенных хеширований. Подробнее этот вопрос излагается в [А.24].) 
    Помимо демонстрации принципа работы хеширования, в данном примере также 
показано, почему возникает необходимость использовать для хеш-функции 
специальную функцию. Теоретически можно было бы для определения адреса вместо 
функции использовать непосредственно значение ключевого поля (если это поле 
имеет числовой тип). Однако практически такой способ неприемлем, поскольку 
диапазон возможных значений ключевого поля может быть гораздо шире диапазона 
имеющихся адресов. В предыдущем примере номера записей с данными о поставщиках 
находятся в диапазоне SOOO-S999, т.е. их может быть около 1000, тогда как в 
действительности может быть только десять реальных поставщиков. Таким образом, 
во избежание неэффективного использования дискового пространства следует найти 
такую хеш-функцию, чтобы можно было сузить диапазон 000-999, например, до 0-9. 
Для того чтобы зарезервировать дополнительное пространство (размером 20% от 
исходной величины), диапазон 0-9 в данном примере расширен до 0-12. 
    В этом примере также наглядно проявляется недостаток хеширования. Дело в 
том, что физическая последовательность записей внутри хранимого файла почти 
всегда отличается от последовательности ключевого поля, а также любой другой 
логически заданной последовательности. (К тому же, между последовательно 
размещенными записями могут быть промежутки неопределенной протяженности.) 
Практически всегда физическая последовательность записей в хранимом 
хешированном файле не имеет ничего общего с заданной в нем логической последовательностью. 
    (Конечно, в хешированном файле всегда можно принудительно задать с помощью 
индекса одну логическую последовательность или даже несколько таких 
последовательностей на основе нескольких индексов. Более подробно эти вопросы, 
а также схемы хеширования с сохранением логической последовательности 
обсуждаются в [А.35, А.37].) 
    Еще одним недостатком хеширования является возможность возникновения 
коллизий, т.е. ситуаций, когда две или более различных записи ("синонимы") 
имеют одинаковые адреса. Допустим, что файл поставщиков из предыдущего примера 
(с записями S100, S200 и т.д.) содержит также запись с номером S1400. При 
использовании хеш-функции типа "остаток от деления на 13" возникнет коллизия 
(по адресу 9) с записью S100. Ясно, что такая хеш-функция неадекватна и для 
устранения коллизий необходимо ее исправить. 
    В рассматриваемом примере одним из вариантов исправления могло быть 
использование остатка от деления на 13 не в качестве адреса, а в качестве 
стартовой точки для дополнительного просмотра и поиска. Таким образом, для 
вставки записи с номером поставщика S1400 (допуская, что в файле уже 
содержатся записи S100-S500) следует перейти к странице 9, а затем найти 
первую свободную страницу. В данном 

    692	Приложения 

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

    Расширяемое хеширование 

    Еще один недостаток описанного выше способа хеширования — возрастание 
числа коллизий с увеличением размера хранимого файла. Это, в свою очередь, 
может привести к значительному увеличению среднего времени доступа, поскольку 
все больше и больше времени придется тратить на поиск записей в наборах 
конфликтующих записей. Однако этот недостаток можно устранить, если 
реорганизовать файл, т.е. выгрузить данный файл и загрузить его вновь, 
используя новую хеш-функцию. 
    Расширяемое хеширование [А.28] — прекрасный способ разрешения этой 
проблемы. Действительно, с использованием расширяемого хеширования потребуется 
не более двух доступов к диску для поиска заданной записи (т.е., записи, 
имеющей заданное значение ключевого поля), а в некоторых случаях будет 
достаточно даже одного доступа независимо от размера файла. (При этом также не 
потребуется дополнительной реорганизации файла.) 

    Замечание. При использовании расширяемого хеширования необходимо, чтобы 
все значения хеш-поля были уникальны, что может быть реализовано только в том 
случае, если хеш-поле является ключевым. 

    Ниже приводится описание основных принципов работы метода расширяемого хеширования. 
    1.  Допустим, что в качестве хеш-функции используется функция /?, а 
значение ключевого поля для некоторой записи г равно k. В результате 
хеширования значения ключевого поля k, т.е. вычисления значения хеш-функции 
h(k), будет получено значение псевдоключа для записи г. Псевдоключ 
используется не в качестве адреса записи, а лишь как косвенный указатель на 
место их хранения. Подробнее об этом сказано ниже. 
    2.  Хранимый файл имеет связанный с ним каталог, который также сохраняется 
на диске. Он состоит из заголовка, содержащего значение d, которое называется 
глубиной каталога, а также 2е1 указателей на страницы с несколькими записями 
данных на каждой. Таким образом, с помощью каталога глубиной d можно 
организовать управление файлом, содержащим 2J различных страниц с данными. 
    3.  Если рассматривать первые d бит псевдоключа (т.е. первые d бит 
значения, полученного в результате вычисления хеш-функции от значения 
ключевого ключа) как целое беззнаковое двоичное число Ь, то /-и указатель в 
каталоге (1</<2'') будет относиться к странице, содержащей все записи, для 
которых величина Ь равна /—1. 

    Приложение А. Структуры хранения и методы доступа	693 

    Иначе говоря, первый указатель будет относиться к странице с записями, у 
которых b составлено из нулей, второй указатель — на страницу с записями, у 
которых b равно 0...01, и т.д. (Как отмечается в следующих пунктах, не все 
указатели, созданные таким образом, будут различными, а количество страниц 
будет меньше 2J.) Теперь, для того чтобы найти запись со значением ключевого 
поля, равным k, нужно с помощью хеш-функции вычислить значение псевдоключа s, 
затем по первым d бит псевдоключа определить численное значение /—1 и найти в 
каталоге (первый доступ (первое обращение) к диску) соответствующий ему /-и 
указатель на страницу, содержащую искомую запись (второй доступ к диску). 
Замечание. Обычно каталог имеет достаточно малый размер, чтобы его можно было 
разместить в оперативной памяти и сократить число обращений к диску. 
    4.  Каждая страница данных имеет заголовок с указанием локальной глубины р 
этой страницы (p<d). Предположим, например, что d равняется трем и первый 
указатель в каталоге указывает на страницу с локальной глубиной/», равной 
двум. Этот пример схематически изображен на рис. А. 15. Равенство локальной 
глубины двум означает, что страница содержит не только записи со значениями 
псевдоключа 000, но и со значениями псевдоключа 00 (например, 000 и 001). 
Иначе говоря, указатель каталога 001 также указывает на эту страницу. 

    Страницы с данными 


    Глубина Указатель 000 Указатель 001 Указатель 010 Указатель 011 Указатель 
100 Указатель 101 Указатель 110 Указатель 111 
    *	2 | Локальная глу 
    я 
    равны 00 
    Локальная глубина: Первые три бита равны 010 

    Рис, А. 15, Пример реализации расширяемого хеширования 

    5.  Теперь предположим, что требуется вставить еще одну запись с псев до 
ключом 000 (или 001) на полностью заполненную страницу 000. В таком случае 
страница будет разделена на две части с увеличенной на единицу локальной 
глубиной. Одна из 

    694 Приложения 

частей (старая страница) будет содержать все записи с псевдоключами 000, и на 
нее будет указывать указатель 000, а в другую часть (новую страницу) будут 
перемещены все записи с псевдоключами 001, и на нее будет указывать указатель 001. 
    6.  Предположим, что через некоторое время страница 000 опять 
переполнилась и ее следует снова разделить с увеличением локальной глубины. К 
сожалению, это невозможно сделать, поскольку локальная глубина уже сравнялась 
с глубиной каталога. В таком случае следует создать дубликат каталога, т.е. 
увеличить его глубину на единицу и заменить каждый указатель парой смежных 
указателей. Теперь страница с данными может быть снова разделена на две части 
с прежним указателем 0000 на старую страницу и новым указателем 0001 на вновь 
созданную. Обратите внимание, что для дублирования каталога не требуется почти 
никаких затрат ресурсов, поскольку при этом не происходит обращения к страницам. 
    Здесь был описан лишь один из вариантов хеширования —расширяемое 
хеширование, однако существует множество других способов реализации этой 
основной идеи. Подробную информацию о них можно получить, например, в [А.29-А.36]. 

    А.6. Цепочки указателей 

    Для выполнения запроса типа "Найти поставщиков из города С" можно 
применить другой способ сохранения данных с использованием цепочек указателей. 
Этот способ часто бывает более эффективен, чем индексирование. На рис. А. 16 
показан пример использования цепочек указателей для файла поставщиков и файла 
городов. Однако, в отличие от примера с индексированием (см. рис. А.9), теперь 
оба файла могут находиться в одном наборе файлов. Причем файл городов 
называется не индексным, а родительским файлом. Соответственно файл 
поставщиков называется дочерним фатом, а подобная структура в целом называется 
родительско-дочерней. 
    В данном примере родительско-дочерняя структура организована на основе 
файлов поставщиков и городов. Родительский файл (файл городов) содержит одну 
хранимую запись для каждого города, предоставляя по требованию название города 
в качестве заголовка цепочки или кольца указателей, связывающих вместе все 
дочерние записи поставщиков из этого города. Обратите внимание, что поле с 
названиями городов удалено из файла поставщиков, потому что в СУБД для поиска 
всех поставщиков из Лондона будет предпринят поиск строки со словом "London" в 
файле городов, а затем извлечена вся связанная с данной строкой цепочка указателей. 
    Принципиальным преимуществом родительско-дочерней структуры является 
значительно более простое выполнение операций вставки или удаления записей по 
сравнению с индексной структурой. Кроме того, родительско-дочерняя структура 
занимает меньше места на диске, чем соответствующая индексная структура, 
поскольку в ней не повторяются названия городов. Однако такая структура имеет 
и некоторые недостатки. 
    •  Для данного города единственным путем доступа к и-му поставщику 
является цепочка с последовательным перебором всех предыдущих записей 
поставщиков: 1-й, 2-й, ... (и-1)-й. Если для этих записей не выполнена 
кластеризация, то для каждого доступа может потребоваться отдельная операция 
поиска, а время доступа к записи с данными и-го поставщика может оказаться 
очень большим. 
    •  Хотя такая структура может быть оптимальной для выполнения запроса типа 
"Найти поставщиков из заданного города", она весьма неэффективна для обратного 
запроса— "Найти город данного поставщика", где поставщик задан с помощью 
номера. Для обратного запроса лучше подошла бы индексная или хеширо-ванная 
структура, а родительско-дочерняя структура на основе номеров поставщиков была 
бы крайне неэффективной. Дело в том, что, даже зная номер

    Приложение А. Структуры хранения и методы доступа	695 

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

    Замечание. Для хеширования набора записей также придется провести полную 
реорганизацию базы данных, если только хеширование не является косвенным [А.24]. 

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

    А.7. Технологии сжатия 

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

    696	Приложения 


    ч			J                ^ —— П ""'"""   IJI	S^T   |     r«»      ,,.,r  rnnonQB 
    /      •   • 
    J	( 
    '                                            ^ 
    r 
    lr 
    |S1  | Smith     20 |f|     | S2 | Jones   | 10 |»f>| S3 | Blake   | 30 
|'				|S4	Clark	20 |l	i|     | S5    Adams | 30   4	1 |  поставщиков 
    [                 t 
    
    
    Рис. А.16. Пример реализации родительско-дочерней структуры 


    ^    ^„UUM     |   -   ,	S^**     "°   i	.J 
    
    
    J 
    ^ 
    
    
    t=	^ 
    :				, , 
    г п ——— Н | S1  | Smith   |  '	III     I S2  | Jones   |   ,	-f>| S3  | 
Blake   |   !	|4     | S4 ] Clark   |   |  |	| S5 | Adams |    • | 
    t	1    I          1	\       I	==j— 4-	._J 
    1	S   ]	\	i 
    ^	——— 1 —— -i_	X	————      _4. 
    *~		i ••                                                   ^	s\ 
    r— 1 — *	' —— !	—————   ~          |	^/ 
    1        1 L_J ,n 1   1   1	i   _ i L^Unl    1	Г __ J" L^J ™ 1    1 
    

    Рис. А. 17. Пример совместного использования двух разных 
родительско-дочерних структур 


697	Приложения 


    Технологии сжатия основаны на том, что данные редко имеют совершенно 
беспорядочную структуру и гораздо чаще их можно просто предсказать. Если, 
например, имя некоторого человека в базе данных с именами и адресами 
начинается с буквы R, весьма вероятно, что следующее имя в ней также 
начинается с этой буквы. При том условии, конечно, что значения имен в этой 
базе данных отсортированы по алфавиту. 
    Наиболее распространенной является технология сжатия на основе различий, 
при которой некоторое значение заменяется сведениями о его отличиях от 
предыдущего значения. Следует отметить, что для реализации такой технологии 
требуется размещать данные последовательно, поскольку для их распаковки 
необходимо иметь значение предыдущей величины. Такое сжатие весьма эффективно 
для данных, к которым необходим последовательный доступ, например для записей 
в одноуровневом списке. Более того, в таких случаях наряду с данными можно 
также сжать и указатели. Дело в том, что если логическая последовательность в 
файле соответствует физической последовательности размещения данных на диске, 
то соседние указатели будут незначительно отличаться друг от друга. В таком 
случае сжатие указателей может оказаться весьма полезным и эффективным. Как 
показывает опыт, использовать сжатие для записей с индексами, даже если 
сжимаются одни только данные, а не данные вместе с указателями, очень выгодно. 
    В качестве примера рассмотрим страницу с записями из списка имен 
сотрудников с такими данными: 

    Roberton Robertson Robertstone Robinson 

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

    О	- Robertonf++-t 
    6	- son+++ 
    7	- tone+ 
    3	- inson+++^ 

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

    О - 7 - Roberto 
    6 - 2 - so 
    7 - 1 - t 3 - 1 - i 

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

    Roberto????? Robertso???? Robertst???? Robi???????? 

    Такая потеря информации допустима только, если в каком-то другом месте эти 
данные сохранены полностью, например в файле с данными о сотрудниках. 
    

    698	Приложения 


    Иерархическое сжатие 

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

    Athens		S5	Adams	30 
    
    
    London		S1	Smith	»		1 S4      Clark    I 20 
    
    
    Paris		S2	Jones	*		1 S3      Blake    I 30 

    Рис. А. 18. Пример реализации внутрифайлового иерархического сжатия 

    Хранимая иерархическая запись, показанная на рис. А. 18, состоит из двух 
частей: постоянной — поля с названиями городов, и переменной — набора записей 
о поставщиках. (В последней части переменным является число записей о 
поставщиках, которые входят в состав иерархической записи данного города.) 
Такой набор значений переменного количества внутри одной записи обычно 
называется группой повторения. Таким образом, можно сказать, что иерархическая 
запись, показанная на рис. А. 18, состоит из значения поля городов и группы 
повторения с информацией о поставщиках, которая, в свою очередь, состоит из 
поля с номерами поставщиков, поля с именами поставщиков и поля статуса (по 
одному экземпляру группы для каждого поставщика в соответствующем городе). 
    Иерархическое сжатие такого типа полезно применять для индекса, в котором 
несколько последовательно расположенных значений содержат одни и те же 
повторяющиеся значения данных, но различные значения указателей. 
    Здесь было описано иерархическое сжатие на основе внутрифайловой 
кластеризации. Однако этот тип реализации может также применяться и в случае 
.межфайловой кластеризации. Предположим, что записи о поставщиках и поставках 
размещены в результате межфайловой кластеризации так, как было описано выше в 
этом приложении, т.е. записи о поставках поставщика S1 размещаются 
непосредственно за записью этого поставщика S1, записи о поставках поставщика 
S2 — непосредственно за записью этого поставщика S2 и т.д. Точнее, допустим, 
что запись поставщика S1 и записи о его поставках размещены на странице р/, 
запись поставщика S2 и записи о его поставках — на странице р2 и т.д. Тогда 
межфайловое сжатие схематически будет организовано так, как показано на рис. 
А. 19. 

    Замечание. Хотя описанная выше структура названа межфайловой, она на самом 
деле равносильна внутрифайловой для файла, содержащего как записи о 
поставщиках, так и записи о поставках. Таким образом, она по своей сути не 
очень отличается от структуры, представленной на рис. А. 18. 


    Приложение А. Структуры хранения и методы доступа 699 


    Страница р1 
    Страница р2 
    S1	Smith		20	London		JP1	300 
    Р2	200	РЗ	400	h	200	Р5	100 
    
    
    Рб	100J 
    
    
    S2 
    Jones 
    10 
    Paris 
    (аналогично для страниц рЗ, р4, р5) 

    Рис. А, 19. Пример реализации межфайлового иерархического сжатия 

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

    Кодирование Хафмана 

    Кодирование Хафмана (Huffman) [A.39] — это технология кодирования 
символов, которая не очень распространена в современных СУБД, но может быть 
весьма эффективной для сжатия различных символов, встречающихся с разной 
частотой (что, в сущности, отражает реальную ситуацию). Основная идея этого 
метода заключается в кодировании отдельных символов битовыми строками 
различной длины, причем наиболее часто встречающиеся символы кодируются 
строками наименьшей длины. Кроме того, код любого символа длиной п не должен 
совпадать с первыми п символами кода какого-либо другого символа. 
    Предположим, что некоторые данные записаны с помощью символов А, В, С, D, 
Е; относительная частота, с которой они встречаются, а также их коды показаны ниже. 

    Символ	Частота, %	Код 
    Е	35	1 
    А	30	01 
    D	20	001 
    С	10	0001 
    В	5	0000 

    Символ Е встречается чаще остальных и потому имеет самый короткий код, 
состоящий из одного бита — единицы. Все остальные коды должны быть длиннее 
(нельзя использовать код на основе одного нуля, так как он будет совпадать с 
начальной частью других более длинных кодов) и начинаться с нуля. Для 
следующего по частоте использования символа А выбран следующий самый короткий 
код— 01, и потому все остальные коды должны начинаться с битов 00. Аналогично 
для символов ' D, С и В назначаются коды 001, 0001 и 0000 соответственно. 
    На основе несложного вычисления можно получить среднюю длину 
закодированного символа в битах: 

    0,35 *  1 + 0,30 *  2 +  0,20 *  3 + 0,10 * 4 + 0,05 *  1 = 2,15 

    Если бы эти символы кодировались битовыми строками одинаковой длины, то 
для каждого из пяти закодированных символов потребовалось бы по крайней мере 
три бита, т.е. в этом случае общая длина закодированного текста (в среднем) 
была бы почти на 40% больше, чем при кодировании Хафмана. 

    700 Приложения 

    Упражнение. Какие английские слова закодированы с помощью битовых строк, 
приведенных ниже? 
    1.       00110001010011 
    2.    01000Ю00110011 

    А.8. Резюме 

    В этом приложении был дан обширный (но далеко не исчерпывающий) обзор 
наиболее важных современных структур хранения данных. При этом вкратце была 
описана общая схема функционирования программного обеспечения, 
предназначенного для доступа к данным, а также распределение выполнения этих 
задач между СУБД, диспетчером файлов и диспетчером дисков. Основной целью 
изложения было разъяснение общих идей и концепций без описания отдельных 
подробностей их реализации в разных практически используемых системах и 
структурах хранения. И хотя изложение велось в достаточно общем виде, описания 
отдельных деталей избежать не удалось. 
    Ниже приводится краткий итог изложенного материала. Прежде всего, описана 
идея кластеризации, которая заключается в близком физическом размещении 
совместно используемых записей. Также рассматривалось, как хранимые записи 
идентифицируются с помощью идентификационного номера записей, RID-указателя. 
Затем обсуждались некоторые наиболее важные структуры хранения, часто 
используемые на практике. 
    •   Индексы (несколько различных вариантов, в частности Б-деревья) и их 
использование для последовательного и прямого доступа. 
    •   Хеширование (включая расширяемое хеширование) и его использование для 
прямого доступа. 
    •   Цепочки указателей (также известные как родительско-дочерние 
структуры) и их многочисленные варианты. 
    Кроме того, были описаны некоторые технологии сжатия. 
    В заключение следует отметить, что многие пользователи не подозревают (или 
не желают даже знать) о содержании изложенного здесь материала. Правда, 
единственный пользователь, которому необходимо разбираться во всех 
подробностях этих подходов, — это администратор базы данных: он несет 
ответственность за физическую организацию СУБД, следит за ее 
производительностью и осуществляет настройку. Остальные пользователи могут и 
не знать всех тонкостей внутренней организации системы, хотя обладание такими 
знаниями позволило бы им лучше выполнять свою работу. А для разработчиков СУБД 
знание этого материала (причем в гораздо большем и полном объеме), если не 
обязательно, то весьма желательно. 

    Упражнения 

    Упражнения А.1-А.8 могут быть полезны для коллективного обсуждения, они 
предназначены для более глубокого изучения и понимания различных физических 
конструкций баз данных, а упражнения А.9 и АЛО имеют математический характер. 
    АЛ. Изучите любую доступную вам систему баз данных (чем крупнее, тем 
лучше) и попытайтесь определить, какие ее компоненты выполняют описанные в 
этом приложении функции диспетчера дисков, диспетчера файлов и СУБД. Какие 
типы дисков поддерживаются этой системой? Каков размер' файловой страницы? 
Какова теоретическая (в байтах) и реальная (в страницах) емкость диска? Какова 
скорость обмена данными? Каково время доступа? Насколько время доступа к диску 
отличается от времени доступа к 

    Приложение А. Структуры хранения и методы доступа	701 

оперативной памяти? Существуют ли какие-либо ограничения на размер файла 
или базы данных? Если да, то какие? Какую из структур хранения поддерживает 
данная система? Поддерживаются ли в ней другие структуры хранения? Если да, то какие? 
    А.2. База данных о персонале фирмы содержит информацию о филиалах, отделах 
и сотрудниках этой компании. Каждый сотрудник работает в одном отделе, каждый 
отдел является частью одного из филиалов. Придумайте некоторый пробный набор 
данных и попытайтесь создать макет возможных структур хранения. По возможности 
попробуйте перечислить преимущества той или иной структуры, т.е. рассмотрите, 
как будут выполняться в том или ином случае операции извлечения или обновления 
данных. Подсказка. Условия типа "каждый сотрудник работает в одном отделе" и 
"каждый отдел является частью одного филиала" по своей структуре аналогичны 
условию "каждый поставщик живет в одном городе" (они являются примерами связи 
типа многие-к-одному). Различие заключается в том, что в базе данных фирмы 
содержится больше информации об отделах и филиалах, чем в базе данных 
поставщиков информации о городах. 
    А.З. Повторите упр. А.2 для базы данных с информацией о клиентах и 
товарах. Каждый клиент может заказать любое количество товаров, а каждый товар 
может быть заказан любым количеством клиентов. Подсказка. Это пример связи 
.многие-ко-многим между клиентами и товарами. Один из способов реализации 
такой связи — использование двойного индекса (для одновременного 
индексирования двух файлов). Одно значение такого индекса соответствует паре 
связанных записей — по одной из каждого файла — и содержит два значения данных 
и два указателя. Сможете ли вы предложить какой-нибудь другой способ 
представления связей типа многие-ко-многим? 
    А.4, Повторите упр. А.2 для базы данных с информацией о конструкциях и 
деталях, где каждая деталь также может быть конструкцией, состоящей из деталей 
более низкого уровня. Подсказка. Насколько это упражнение отличается от упр. А.З? 
    А,5. Хранимый файл с записями данных без заданной структуры доступа к 
данным (т.е. без индекса, хеш-функции и т.п.) иногда называется кучей. Новые 
записи в куче вставляются в первое попавшееся свободное место. Для малых 
файлов, т.е. практически для любого файла, содержащего не более девяти или 
десяти страниц, такая структура является оптимальной. Однако на самом деле 
многие файлы имеют гораздо больший размер и для них требуется создать 
специальную структуру доступа к данным, например с помощью индекса или 
ключевого поля. Опишите преимущества и недостатки индексированной структуры по 
сравнению со структурой кучи. 
    А.6. Несколько раз в этом приложении упоминалась физическая кластеризация. 
Например, может быть очень выгодно с точки зрения повышения производительности 
расположить вместе логически связанные записи с данными о поставщиках так, 
чтобы физическая последовательность в наибольшей сте-; пени соответствовала 
логической последовательности согласно полю с но; мерами поставщиков (поле 
кластеризации). Как можно в СУБД организовать физическую кластеризацию? 
    А.7. Выше в этом приложении уже упоминалось, что для разрешения коллизий 
хеширования можно было бы использовать значение хеш-функции в качестве 
начальной точки для дальнейшего последовательного просмотра (технология 
последовательного перебора). Какие трудности могут возникнуть при реализации 
этой схемы? 

    702	Приложения 

    А.8. Какие преимущества и недостатки присущи множественной 
родитель-ско-дочерней организации? Выясните преимущества и недостатки 
множественного индексирования. Какие у этих двух структур сходства и различия? 
    А.9. Допустим, термин "полное индексирование" означает, что для каждой 
комбинации полей индексированного файла задан индекс. Например, если файл 
содержит только два поля — А и В, то для полного индексирования файла 
потребуется задать два индекса: один на основе комбинации полей АВ, а другой 
на основе обратной комбинации ВА. Сколько индексов потребуется для полного 
индексирования файла на основе: а) трех полей; б) четырех полей; в) N полей. 
    АЛО. Рассмотрим простой вариант Б-дерева (набор индексов и набор 
последовательностей), в котором набор последовательностей содержит указатели 
на каждую из N хранимых записей с данными, а каждый уровень над набором 
последовательностей (т.е. каждый уровень набора индексов) содержит указатель 
на каждую страницу, расположенную в нижнем уровне. При этом на самом верхнем 
уровне (корневом) находится одна страница. Предположим также, что каждая 
страница из набора индексов содержит п значений индексов. Выведите выражение 
для полного числа уровней и числа страниц во всем этом Б-дереве. 
    А.11. Ниже перечислены первые десять значений индексированного поля 
некоторого индексированного файла: 
    Abrahams, GK Ackermann,LZ Ackroyd,S Adams,Т Adams,TR Adamson, CR Alien,S 
Ayres,ST Bailey,ТЕ Baileyman, D 
    Каждая запись содержит справа несколько пробелов для заполнения строки 
длиной 15 символов. Как будут выглядеть эти значения после переднего и заднего 
сжатия, описанных в этом приложении? Какая часть пространства будет 
сэкономлена (в процентах)? Какие действия и в какой последовательности 
потребуется выполнить, чтобы извлечь (или попытаться извлечь) хранимые записи 
для значений Ackroyd, s и Adams, v? Какие действия нужно выполнить ДЛЯ ВСТавКИ 
НОВОЙ хранимой ЗаПИСИ Allingham,M? 

    Список литературы 

    Приведенный ниже список литературы сгруппирован по следующему принципу. 
Сначала представлены публикации [А.1-А.10], которые затрагивают вопросы, 
изложенные в этом приложении. В [A.I 1-A.I5] приведено несколько формальных 
подходов к данной теме, в [А.16-А.23] подробно описано индексирование, 
особенно на основе Б-деревьев. Кроме того, представлена подборка литературы по 
хешированию [А.24-А.38], технологиям сжатия [А.39-А.40], другим структурам 
хранения и связанным с ними вопросам [А.41—А.59]. 
    АЛ. Knuth D.E. The Art of Computer Programming. Volume III: Sorting and 
Searching. — Reading, Mass.: Addison-Wesley, 1973. 
    Это третий том классической серии книг Кнута с всеобъемлющим анализом 
алгоритмов поиска. 

    Приложение А. Структуры хранения и методы доступа	703 

    A,2, Martin J, Computer Data-Base Organization. (2nd ed.). — Englewood 
Cliffs, N.J.: Prentice-Hall, 1977, 
    Книга содержит две основные части — "Logical Organization" и "Physical 
Organization". В последней приведено подробное описание (около 300 страниц) 
структур хранения и соответствующих методов доступа. 
    А,3, T'eorey T.J., Fry J.P. Design of Database Structures. — Englewood 
Cliffs, N.J.: Prentice-Hall, 1982. 
    Учебное пособие и справочное руководство по логическому и физическому 
устройству баз данных (более 200 страниц посвящено физическому устройству), 
    А.4. Wiederhold G. Database Design (2nd ed.). — New York, N.Y.: 
McGraw-Hill, 1983. 
    Книга (15 глав) содержит прекрасный обзор устройств хранения информации с 
характеристиками их производительности (одна глава, около 50 страниц), а также 
подробный анализ структур хранения (четыре главы, более 250 страниц). 
    А,5, Merrett Т.Н. Relational Information Systems. — Reston, VA.: Reston 
Publishing Company, Inc., 1984. 
    Предложен обширный обзор и анализ нескольких структур хранения (около 100 
страниц), среди них есть и такие, которые не были описаны в данном приложении. 
    А,6. Ullman J.D. Principles of Database and Knowledge-Base Systems: Volume 
I.— Rockville, MD.: Computer Science Press, 1988. 
    Приведено описание структур хранения, которое носит более теоретический 
характер, чем предложенное в данном приложении. 
    А.7. Korth H.F., Silberschatz A. Database System Concepts (2nd ed.). — New 
York, N.Y.: McGraw-Hill, 1991. 
    A.8. Smith P.O., Barnes G.M. Files and Databases: An Introduction. -•-- 
Reading, Mass.: Addison-Wesley, 1987. 
    A.9, Elmasri R., Navathe S.B.  Fundamentals of Database Systems (2nd ed.). 
— Redwood City, Calif: Benjamin/Cummings, 1994. 
    Книги [А.7-А.9] являются учебниками по базам данных, они содержат материал 
о структурах хранения, в некотором отношении выходящий за рамки материала, 
изложенного в данном приложении (это особенно касается [А.8]). 
    АЛО, Ghosh S.P. Data Base Organization for Data Management (2nd ed.). — 
Orlando, Fla: Academic Press, 1986. 
    Основное внимание в этой книге уделяется структурам хранения и связанным с 
ними методам доступа —- этой теме посвящено по крайней мере шесть глав из 
десяти. Изложение ведется в очень краткой форме. 
    A.ll, Hsiao D.K., Harary F. A Formal System for Information Retrieval from 
Files // С ACM, — 1970. — 13, №2. 
    Это, вероятно, самая первая попытка обобщить идеи, касающиеся различных 
структур хранения, особенно индексов и цепочек указателей, для создания общей 
формальной теории таких структур. 
    А.12. Severance D.G. Identifier Search Mechanisms: A Survey and 
Generalized Model // ACM Сотр. Surv. — 1974. — 6, № 3. 
    Эта статья состоит из двух частей. Первая содержит вводный учебный 
материал о некоторых структурах хранения, в основном о хешировании и

    704	Приложения 

индексировании. Вторая по тематике совпадает с [АЛ 1], так как в ней 
определена некая унифицированная структура под названием трап-дерево 
(trie-tree), в которой собраны и обобщены идеи, изложенные в первой части. 
Термин trie ("трай"), который произносится так же, как и try, был впервые 
предложен в статье Фредкина [А.42]. Такая структура на основе небольшого 
количества параметров может представлять широкий диапазон моделей различных 
структур хранения. Она может использоваться (и даже используется) для выбора 
той или иной частной структуры хранения в процессе макетирования физической 
организации реальной базы данных. 
    Различие между этой и предыдущей работой заключается в том, что в 
структуре трай-дерева используется хеширование, а в структуре, упомянутой в 
[АЛ 1], — цепочки указателей. 
    А.13. Senko M.E., Altman E.B., Astrahan M.M., Fehder P.L. Data Structures 
and Accessing in Date-Base Systems // IBM Sys. J. — 1973. — 12, № 1. 
    Статья состоит из трех частей. 
    1.Evolution of Information Systems (Эволюция информационных систем). 
    2.Information Organization (Организация информации). 
    S.Data Representations and the Data Independent Accessing Model 
(Представления данных и независящая от данных модель доступа). 
    Первая часть представляет собой исторический обзор развития СУБД до 1973 
года. Во второй части приводится описание модели "целостного множества", 
которая образует основу последующего описания некоторого предприятия в 
терминах целостности и целостных множеств (оно концептуально связано с 
архитектурой ANSI/SPARC). Третья часть наиболее оригинальна и значительна, 
поскольку в ней изложены основы не зависящей от данных модели доступа (Data 
Independent Accessing Model — DIAM). По сути, это попытка описать базу данных 
на основе четырех последовательных абстрактных уровней, а именно: целостного 
множества (наивысший уровень), строки, кодирования и физического устройства. 
Их можно представить как более подробное, но все еще абстрактное определение 
концепции и внутреннего устройства архитектуры ANSI/SPARC. 
    Основное назначение модели DIAM (как и [АЛ 1, А Л 2]) состоит в построении 
основы систематической теории структур хранения и методов доступа. Недостатком 
такого подхода (а также формальных подходов, предлагаемых в [АЛ 1, А. 12]) 
является его статичное устройство, тогда как в реальных ситуациях наилучшим 
способом выполнения заданного запроса была бы сортировка, которая является 
динамическим процессом. 
    А.14. Yao S.B. An Attribute Based Model for Database Access Cost Analysis 
// ACM TODS.— 1977.—2, № 1. 
    Цель этой статьи в некотором смысле та же, что и [АЛ 1, А.12], т.е. ее 
можно рассматривать как комбинированное и расширенное продолжение этих работ, 
в котором приведена обобщенная модель структур хранения баз данных. В статье 
также представлено несколько обобщенных алгоритмов доступа и анализ их 
эффективности в рамках обобщенной модели. Кроме того, приведен список ссылок 
на публикации, в которых описываются результаты работы с анализатором 
физической организации файлов в рамках представленных в этой статье идей. 

    Приложение А. Структуры хранения и методы доступа	705 
    23 Введение в системы баз данных 


    А, 15. Batory  D.S.  Modeling  the  Storage  Architectures  of Commercial  
Database Systems // ACM TODS. — 1985. — 10 , № 4. 
    В статье представлен набор простых операций, элементарных преобразований, 
с помощью которых можно совершить явное отображение концептуальной схемы на 
соответствующую внутреннюю схему (так называемое отображение 
концептуальный-внутренний — см. главу 2) с последующим тщательным изучением. 
Элементарные преобразования состоят из расширения хранимой записи приставкой 
кодирования (для конвертирования данных в используемую внутреннюю форму, 
например сжатие), а также сегментации (разделения записи на несколько частей в 
целях сохранения). В статье утверждается, что любое отображение 
концептуальный-внутренний может быть представлено соответствующей 
последовательностью этих элементарных преобразований. Таким образом, эти 
преобразования могут стать основой автоматизированного подхода для разработки 
системы управления данными. В качестве иллюстрации в статье рассмотрены три 
реальных системы: INQUIRE, ADABAS и System 2000. 
    А. 16. Bayer R., McCreight С. Organization and Maintenance of Large 
Ordered Indexes // Acta Informatica. — 1972. — 1, № 3. 
    A, 17. Comer D. The Ubiquitous B-tree // ACM Сотр. Surv. — 1979. — 11, № 2. 
    Прекрасное учебное пособие по Б-деревьям. АЛ8. Wagner R.E. Indexing Design 
Considerations // IBM Sys. J. — 1973. — 12, № 4. 
    Описание основных концепций индексирования, включая технологии сжатия, с 
подробным изложением некоторых концепций, используемых в методе VSAM фирмы IBM. 
    А. 19. Chang   H.K.   Compressing   Indexing  Method  //  IBM   Technical  
 Disclosure Bulletin.— 1969.—II, № 11. 
    A.20. Gupta G.K. A Self-Assessment Procedure Dealing with Binary Search 
Trees and B-trees // CACM. — 1984. — 27, № 5. 
    A.21. Lum V.Y. Multi-Attribute Retrieval with Combined Indexes // Ibid. — 
1970. — 13, № 11. 
    Впервые рассмотрена технология индексирования на основе комбинации 
нескольких полей. 
    А.22. Mullin J.K. Retrieval-Update Speed Tradeoffs Using Combined Indices 
// Ibid. — 1971.—14, № 12. 
    Продолжение работы [А.21]; здесь приводится сравнительный статистический 
анализ производительности систем с индексированием на основе комбинации 
нескольких полей для разных соотношений количества операций извлечения/обновления. 
    А.23. Shneiderman В. Reduced Combined Indexes for Efficient Multiple 
Attribute Retrieval // Information Systems. — 1976. — 2, № 4. 
    Изложена модернизированная версия индексирования на основе комбинации 
нескольких полей, предложенная в [А.21], с существенным сокращением 
необходимого для хранения пространства и времени поиска. Например, комбинацию 
индексов ABCD, BCDA, CDAB, DABC, ACBD, BDAC (см. ответ на упр. А.9,б) можно 
заменить комбинацией ABCD, BCD, CDA, DAB, AC, BD. Так, если каждое из полей А, 
В, С, D содержит по 10 различных значений, то в худшем случае для оригинальной 
комбинации индексов потребуется около 60 000 значений индексов, а для 
модернизированной — только 13 200. 

    706	Приложения 

    А.24. Morris R. Scatter Storage Techniques // CACM. — 1968. — 11, № 1. 
    Статья в основном посвящена описанию хеширования символьных таблиц 
транслятора или компилятора, а именно косвенному хешированию на основе таблиц 
разброса. В таких таблицах содержатся адреса записей со структурой, подобной 
структуре каталога для расширяемого хеширования [А.28]. Таблицу разброса можно 
рассматривать как одноуровневый индекс для основных данных, но в этом случае 
индекс может быть найден напрямую с помощью хеш-функции без необходимости 
последовательного поиска. Обратите внимание, что в хранимом файле с основными 
данными может быть определено несколько таблиц разброса, с помощью которых 
можно обеспечить доступ к данным на основе значений разных хеш-полей (за счет 
дополнительного числа операций ввода-вывода). 
    Несмотря на явный уклон в сторону программирования, в статье есть 
прекрасное введение в технологии хеширования, а весь излагаемый материал может 
быть также применен для хеширования баз данных. 
    А.25. Maurer W.D., Lewis T.G. Hash Table Methods // ACM Сотр. Surv. — 
1975. — 7,№ 1. 
    Прекрасное учебное пособие, хотя и немного устаревшее, в котором описаны 
новые подходы, такие как, например, расширяемое хеширование. Статья содержит 
разделы об основных технологиях хеширования (не только типа деление/остаток, 
но также и случайное, среднеквадратичное, алгебраическое, на основе сложения и 
цифрового анализа), о переполнении ячеек хеш-таблицы и управлении коллизиями, 
о теоретическом анализе различных технологий, об альтернативах хешированию (в 
случаях, когда хеширование невозможно или его не следует применять). 
Замечание. Под ячейкой хеш-таблицы подразумевается элементарный участок 
хранения данных (обычно это страница, содержащая несколько записей), адрес 
которого вычисляется с помощью хеш-функции. 
    А.26. Lum V.Y., Yuen P.S.T., Dodd M. Key-to-Address Transform Techniques: 
A Fundamental Performance Study on Large Existing Formatted Files // CACM. — 
1971. —14, №4. 
    Исследование производительности нескольких различных основных (т.е. 
"нерасширяемых") алгоритмов хеширования. В статье делается заключение, что 
метод типа "деление/остаток" обладает наилучшей производительностью. 
    А.27. Ramakrishna M.V. Hashing in Practice: Analysis of Hashing and 
Universal Hashing // Proc. 1988 ACM S1GMOD Intern. Conf. on Management of 
Data. — Chicago, 111., 1988. 
    Как подчеркивается в этой статье (вслед за книгой Кнута [А.1]), в любой 
системе, использующей хеширование, необходимо разрешить две независимые друг 
от друга проблемы: выбрать эффективную хеш-функцию и эффективный метод 
разрешения коллизий. Автор статьи утверждает, что большинство исследований 
посвящено решению второй проблемы, тогда как совсем немного — решению первой, 
т.е. сравнению производительности использования разных хеш-функций с 
теоретической и практической точек зрения. В этом смысле работа [А.26] 
является исключением. Как разработчику СУБД выбрать ту или иную оптимальную 
хеш-функцию? В статье делается утверждение, что с помощью правильного выбора 
такой функции можно приблизить величину практической производительности 
системы к теоретически запланированной. В подтверждение этого представлен ряд 
теоретических результатов. 

    Приложение А. Структуры хранения и методы доступа	707 

    А.28, Fagin R., Nievergelt J., Pippenger N., Strong H.R, Extendible 
Hashing — A Fast Access Method for Dynamic Files // ACM TODS. — 1979. — 4, № 3. 
    A.29. Knott G.D. Expandable Open Addressing Hash Table Storage and 
Retrieval // Proc. 1971 ACM SIGF1DET Workshop on Data Description, Access, and 
Control. — San Diego, Calif., 1971. 
    A.30. Larson P.-A. Dynamic Hashing // BIT. — 1978. — 18. 
    A.31. Litwin W. Virtual Hashing: A Dynamically Changing Hashing // Proc. 
4th Intern. Conf. on Very Large Data Bases. — Berlin, FOR, 1978. 
    A.32. Litwin W. Linear Hashing: A New Tool for File and Table Addressing 
// Proc. 6th Intern. Conf. on Very Large Data Bases. — Montreal, Canada, 1980. 
    A.33. Larson P.-A. Linear Hashing with Overflow-Handling by Linear Probing 
// ACM TODS.— 1985.—10, № 1. 
    A.34. Larson P.-A. Linear Hashing with Separators — A Dynamic Hashing 
Scheme Achieving One-Access Retrieval // Ibid. — 1988. — 13, № 3. В работах 
[A.28-A.34] представлены способы расширяемого хеширования того или иного рода. 
В [А.29] они представлены наиболее явно и отличаются от описанных в других 
работах, но все же в общем они сходны с методами, предложенными в [А.28]. То 
же самое можно сказать и о динамическом хешировании [А.30]. В отличие от 
[А.28], в этих двух работах предлагается использовать каталог с древовидной 
структурой вместо простого непрерывного каталога, представленного в [А.28]. 
"Виртуальное" хеширование — это несколько иной подход, описанный в [А.31]. 
"Линейное" хеширование, представленное в [А.32] и усовершенствованное в [А.33, 
А.34], является модернизированным вариантом виртуального хеширования. 
    А.35. Litwin W. Trie Hashing // Proc. 1981 ACM SIGMOD Intern. Conf. on 
Management of Data. — Ann Arbor, Midi., 1981. 
    Представлена схема расширенного хеширования с перечисленными ниже свойствами. 
    • Сохранение порядка, т.е. "физическая" последовательность хранимых 
записей соответствует логической последовательности, заданной значениями хеш-поля. 
    • Отсутствие сложной организации, которая обычно присуща системам с 
сохранением порядка. 
    • Доступ к любой записи (или получение сообщения о ее отсутствии) с 
помощью только одного обращения к диску, даже если файл содержит миллионы записей. 
    • Способность файла произвольно изменяться (в отличие от этой схемы, 
многие другие схемы хеширования, по крайне мере нерасширяемые, демонстрируют 
плохую работоспособность при большом количестве операций вставки записей). 
    Сама по себе хеш-функция (которая изменяется со временем, как и во всех 
других расширяемых алгоритмах хеширования) представлена с помощью 
трай-структуры [А.42], которая при использовании файла постоянно находится в 
оперативной памяти, независимо от размера файла и роста количества сохраненных 
в нем данных. Этот файл хранится согласно "физической" последовательности 
значений хеш-поля, логическая последовательность данных самого нижнего уровня 
в трай-структуре в точности соответствует "физической" последовательности 
записей с данными. При переполнении файла используется технология разделения 
страниц, которая в общем подобна технологии, применяемой для Б-деревьев. 

    708	Приложения 

    Схема трай-хеширования, как и другие схемы хеширования, обеспечивает более 
высокую производительность, чем индексирование для прямого доступа (одна 
операция ввода-вывода вместо двух или трех для структуры Б-дерева). Она 
предпочтительнее многих других схем хеширования, поскольку в ней 
поддерживается сохранение порядка, что, в свою очередь, означает ускорение 
последовательного доступа. При этом ни структуры Б-дерева, ни другой 
дополнительной структуры не требуется для обеспечения быстрого 
последовательного доступа. Однако необходимо, чтобы вся трай-структура 
помещалась в оперативной памяти (это достаточно реальное требование). Если это 
требование нельзя удовлетворить, например из-за очень большого размера файла с 
данными, или если сохранения порядка не требуется, то в качестве 
альтернативной схемы можно использовать линейное хеширование [А.32] или любое другое. 
    А.36. Lomet D.B. Bounded Index Exponential Hashing // ACM TODS. — 1983. — 
8, № 1. 
    Описана еще одна схема расширяемого хеширования, имеющая следующие преимущества: 
    • Прямой доступ к любой записи за счет приблизительно (в среднем) одной 
операции ввода-вывода (но никогда не более двух). 
    • Производительность не зависит от размера хранимого файла (в качестве 
обратного примера можно сказать, что многие схемы расширяемого хеширования 
подвержены временному снижению производительности, поскольку обычно требуется 
использовать разделение сразу нескольких страниц). 
    • Дисковое пространство можно использовать весьма эффективно. 
    • Эту схему нетрудно реализовать на практике. 
    А.37. Card А.К.,  Gotlieb С.С.  Order-Preserving Key Transformations // 
Ibid. — 1986.— 11, №2. 
    Как упоминалось в комментариях к [А.35], хеш-функция (или преобразование 
ключа) называется сохраняющей порядок, если физическая последовательность 
хранимых записей соответствует логической последовательности этих записей, 
заданной с помощью значений хеш-поля. Сохраняющее порядок хеширование 
желательно использовать по вполне очевидным причинам. Одна простая функция, 
сохраняющая порядок, имеет следующий синтаксис: 
    хеш-адрес = остаток от деления значения хеш-поля на некоторую константу 
(например, 10 000) 
    Очевидной проблемой при использовании хеш-функции является то, что она 
малоэффективна, если значения хеш-поля распределены неравномерно (что обычно 
бывает на практике). Поэтому некоторые исследователи предложили идею 
хеш-функций, не зависящих от распределения и сохраняющих порядок. Такие 
функции преобразуют беспорядочно распределенные значения хеш-поля в 
упорядоченно распределенные хеш-адреса с сохранением порядка. 
(Трай-хеширование [А.35] является примером такого подхода.) В этой статье 
представлен метод конструирования таких хеш-функций для реальных файлов с 
данными и демонстрируется гибкость их практического применения. 
    А.38. Ramakrishna M.V., Larson P.-A. File Organization Using Composite 
Perfect Hashing // Ibid. — 1989. — 14, № 2. 
    Хеш-функция называется совершенной, если она не приводит к "переполнению". 
(Отсутствие "переполнения" не означает отсутствия "коллизий". Например, если 
предположить, что хеш-функция генерирует значения адресов страниц, а не 
адресов записей, и каждая страница может содержать

    Приложение А. Структуры хранения и методы доступа	709 

более чем п хранимых записей, то хеш-функция будет совершенной, если она 
никогда не приводит к отображению более чем п записей на одной странице.) 
Совершенная хеш-функция позволяет извлечь любую запись с помощью всего лишь 
одной операции ввода-вывода. В этой статье представлен практический метод 
поиска и использования таких совершенных функций. 
    А.39. Huffman D.A. A Method for the Construction of Minimum Redundancy 
Codes // Proc. IRE. — 1952. — 40. 
    A.40. Marron B.A., Maine P.A.D. Automatic Data Compression // CACM. — 
1967. — 10, № 11. 
    Описание двух алгоритмов сжатия/распаковки: NUPAK— для числовых данных, 
ANPAK — для алфавитно-цифровых или "любых" данных (т.е. для любой 
последовательности битов). 
    А.41. Severance D.G., Lohman G.M. Differential  Files:  Their Application 
to the Maintenance of Large Databases // ACM TODS. — 1976. — 1, № 3. 
    Обсуждаются преимущества "дифференциальных файлов". Основная идея 
заключается не в обновлении непосредственно самой базы данных, а в записи 
изменений в отдельно размещенном файле (дифференциальном файле) и последующем 
объединении этого файла с базой данных в ближайший удобный для этого момент. В 
статье перечислено несколько преимуществ такого подхода. 
    • Расходы на запись содержимого оперативной памяти на диск понижаются. 
    • Возможна пошаговая запись содержимого оперативной памяти на диск. 
    • Запись содержимого оперативной памяти на диск и реорганизация могут 
выполняться параллельно с операциями обновления. 
    • Восстановление после ошибки программного обеспечения происходит очень быстро. 
    • Восстановление после ошибки аппаратного обеспечения происходит очень быстро. 
    • Риск серьезной потери данных понижается. 
    • Эффективно поддерживаются мемо-файлы. (Мемо-файлы предназначены для 
чернового копирования некоторой части базы данных, выполняемого для 
обеспечения быстрого доступа к данным, которые, вероятно, были обновлены и 
исправлены, хотя полной уверенности в этом нет.) 
    • Разработка программного обеспечения упрощается. 
    • Структура основного файла программного обеспечения упрощается. 
    • Предстоящие затраты на хранение данных сокращаются. 
    В работе не обсуждается поддержка эффективного последовательного доступа к 
данным, т.е. с помощью индексирования, когда одни записи расположены в базе 
данных, а другие — в дифференциальном файле. 
    А.42, Fredkin E. TRIE Memory // CACM. — 1960. — 3, № 9. 
    Трай-структура (trie) — это основанная на древовидной структуре 
разновидность организации файла с данными, а не указателей на эти данные, если 
только файл с данными не является индексным файлом для другого файла, как это, 
например, реализовано в трай-хешировании [А.35]. Каждый элемент трай-структуры 
состоит из п различных символов, предназначенных для представления значений 
данных. Например, если в качестве данных используются десятичные целые числа, 
то каждый элемент будет содержать 10 

    710	Приложения 

символов: О, 1, 2,... 9. Рассмотрим в качестве примера значение данных 
"4285". На самом верхнем элементе древовидной структуры для символа "4" будет 
содержаться указатель на другой элемент, который содержит все данные с первой 
цифрой "4". В свою очередь, этот элемент для символа "2" будет содержать 
указатель на элемент, содержащий все данные с первыми цифрами "42". В 
следующем в этой цепочке элементе для символа "8" будет содержаться указатель 
на элемент, который содержит все данные с первыми цифрами "428". Если, 
например, в базе данных нет данных, которые начинаются с цифр "429", то в 
элементе "42"для символа "9" не будет никаких указателей на другие элементы. 
Иначе говоря, такая древовидная структура не содержит пустых элементов. (Таким 
образом, трай-структура, вообще говоря, не является сбалансированным деревом.) 
    Замечание. Термин трай (trie) происходит от английского слова "retrieval" 
(поиск), однако его принято произносить как английское слово try. 
Трай-структуры также известны как "радиксные" или цифровые структуры поиска. 
    А.43. Wong E., Chiang T.C. Canonical Structure in Attribute Based File 
Organization // Ibid.— 1971.—14, №9. 
    В статье предлагается новая структура хранения на основе булевой алгебры. 
Предполагается, что все запросы доступа строятся на основе элементарных 
булевых условий типа "поле = значение", а все эти условия предполагаются 
известными. Тогда в целях хранения файл может быть разбит на отдельные части, 
"атомы" булевой алгебры, состоящие из множества подмножеств всех записей, 
извлекаемых с помощью булевых запросов. Ниже приведены отмеченные в статье 
преимущества такого способа. 
    • Ни при каких обстоятельствах не используется множество пересечений атомов. 
    • Произвольный булев запрос может быть легко конвертирован в запрос 
объединения нескольких атомов. 
    • Для создания такого объединения не требуется исключать какие-то записи. 
    А.44. Stonebraker M. Operating System Support for Database Management // 
Ibid. — 1981. —24, №7. 
    Обсуждаются причины, по которым разные компоненты операционной системы (в 
частности, диспетчер файлов) часто не обеспечивают поддержку целого набора 
сервисных функций, необходимых для СУБД, и предлагаются некоторые 
усовершенствования этих частей. 
    А.45. Schkolnick M. A Survey of Physical Database Design Methodology and 
Techniques // Proc. 4th Intern. Conf. on Very Large Data Bases. — Berlin, FOR, 1978. 
    A.46. Finkelstein S., Schkolnick M., Tiberio P. Physical Database Design 
for Relational Databases // ACM TODS. — 1988. — 13, № 1. 
    В некотором отношении проблема физического макетирования базы данных 
значительно труднее решается для реляционных баз данных, чем для систем 
другого типа. Дело в том, что система, а не пользователь определяет, как 
предстоит "передвигаться" по структуре хранения. Таким образом, система будет 
работать удовлетворительно, если разработчиком была выбрана такая структура 
хранения, которая максимально соответствует практическим задачам. Это значит, 
что при создании базы данных разработчик должен максимально учитывать 
внутренние особенности работы системы. Несмотря на это, обычно разработчики не 
имеют таких сведений. Для решения этой проблемы очень важно было бы создать 
специальные автоматизированные 

    Приложение А. Структуры хранения и методы доступа.  711 

средства разработки макета баз данных, В этой статье описан один из таких 
инструментов, DBDSGN, разработанный для совместной работы с системой System R 
[8,12, 8,13]. В качестве входных данных для DBDSGN используется определение 
типичной рабочей нагрузки (т.е. набор запросов пользователя и соответствующих 
последовательностей операций), а в качестве выхода — предлагаемый физический 
макет. Инструмент взаимодействует с оптимизатором системы для получения 
соответствующей информации об этой базе данных (например, размеры таблиц и 
т.д.), а также для вычисления эффективности. 
    Инструмент DBDSGN был использован в качестве основы для программного 
продукта RDT фирмы IBM, который является специальным компонентом макетирования 
базы данных в программном обеспечении SQL/DS. 
    А.47. Sevcik K.C. Data Base System Performance Prediction Using an 
Analytical Model // Proc. 7th Intern. Conf. on Very Large Data Bases. — 
Cannes, France, 1981. 
    Как видно из названия, в этой работе излагается более обширный материал, 
чем в данном приложении, поскольку она посвящена вопросам общей 
производительности системы, а не только структурам хранения. Автор предлагает 
многоуровневый набор различных решений для создания макета системы, а также 
схемы взаимодействия этих решений. На каждом более низком уровне система 
описывается более подробно и с меньшим уровнем абстракции, чем на предыдущем. 
Имена этих уровней дают некоторое представление о содержащихся в них 
сведениях: абстрактная среда, логическая база данных, физическая база данных, 
доступ к участку данных, физические операции ввода-вывода и загрузка 
устройств. Автор статьи утверждает, что набор таких уровней позволяет создать 
аналитическую модель, которая может быть использована для предсказания 
многочисленных характеристик производительности, включая использование 
устройств, объем транзакций и время отклика. 
    В статье содержится обширная библиография по вопросам оценки 
производительности системы (без комментариев). В частности, в нее включен 
краткий обзор исследования производительности различных структур хранения. 
    А.48. Samet H. The Quadtree and Related Hierarchical Data Structures // 
ACM Сотр. Surv. — 1984, — 16, №2. 
    Описанные в данном приложении структуры хранения с успехом используются в 
традиционных коммерческих базах данных. Однако по мере расширения области 
применения баз данных и включения в них новых типов данных, например 
графических данных для обработки рисунков или карт, появляется необходимость 
разработки новых методов представления данных на уровне хранения. Эта статья 
является вводным пособием по некоторым из этих новых методов. Более подробную 
информацию можно найти в книге Самета [А.49], а также в [А.50-А.59]. 
    А.49. Samet H. The Design and Analysis of Spatial Data Structures. — 
Reading, Mass.: Addison-Wesley, 1990. 
    См. комментарий к предыдущей ссылке. 
    А.50. Christodoulakis S., Ford D.A. Retrieval Performance Versus Disc 
Space Utilization on WORM Optical Discs // Proc. 1989 ACM SIGMOD Intern. Conf. 
on Management of Data. — Portland, Ore., 1989. 
    См. комментарий к [А.51], 

    712	Приложения 

    А.51. Lomet D., Salzberg B. Access Methods for Multiversion Data // Ibid. 
    Оптический диск, предназначенный для однократной записи и многократного 
чтения данных, называется диском WORM (сокращенная запись выражения "Write 
Once, Read Many times" — однократная запись, многократное чтение). Эта 
технология хранения широко распространена для баз данных, в которых стали 
использоваться данные, записанные на оптических дисках. Использование таких 
дисков имеет определенные преимущества для некоторых приложений, обычно для 
систем архивирования. Такие традиционные структуры хранения, как структуры 
типа Б-деревьев не адекватны структуре оптических дисков потому, что на 
последних нельзя произвести перезапись. Следовательно, для таких дисков 
необходимо разработать новые структуры хранения. В [А.50, А.51] предлагаются и 
анализируются некоторые такие структуры. Например, в [А.51] описаны структуры, 
которые используются в приложениях, где требуется сохранить всю записанную 
ранее последовательность записей (например, в приложениях, где данные только 
добавляются, но никогда не удаляются). 
    А.52. Encarnafao J., Krause F.L. (eds.). File Structures and Data Bases 
for CAD. — New York, N.Y.: North-Holland, 1982. 
    Разработка систем автоматизированного проектирования (САПР) привела к 
появлению новых структур хранения. В книге содержатся доклады семинара по этой 
теме с разделами, перечисленными ниже. 
    1.   Data Modeling for CAD (Моделирование данных для САПР). 
    2.   Data models for geometric modeling (Модели данных для геометрического моделирования). 
    3.   Databases for geometric modeling (Базы данных для геометрического моделирования). 
    4.   Hardware structures (Организация аппаратного обеспечения). 
    5.  CAD database research issues (Исследования использования баз данных в САПР). 
    6.   Implementation problems in CAD database systems (Практическая 
реализация баз данных для САПР). 
    7.   Industrial applications (Промышленные приложения). 
    А.53 Finkel R.A., Bentley J.L. Quad-Trees — A Data Structure for Retrieval 
on Composite Keys // Acta Informatica. — 1974. — 4. 
    A.54 Nievergelt J.,  Hinterberger H.,  Sevcik K.C.  The Grid File:  An 
Adaptable, Symmetric, Multikey File Structure // ACM TODS. — 1984. — 9, № 1. 
    A.55 Guttman A. R-Trees: A Dynamic Index Structure for Spatial Searching 
// Proc. ACM SIGMOD Intern. Conf. on Management of Data. — Boston, Mass., 1984. 
    A.56 Roussopoulos N., Leifker D. Direct Spatial Search on Pictorial 
Databases Using Packed R-Trees // Ibid. — Austin, Texas, 1985. 
    A.57 Beckley D.A., Evens M.W., Raman V.K. Multikey Retrieval from K-D 
Trees and Quad-Trees // Ibid. — Austin, Texas, 1985. 
    A.58 Freeston M. The BANG File: A New Kind of Grid File // Ibid. — San 
Francisco, Calif, 1987. 
    A.59 Barnsley M.F., Sloan A.D. A Better Way to Compress Images // BYTE. — 
1988.—13, № 1. 
    Описана новая технология сжатия изображений — фрактальное сжатие. Согласно 
этой технологии сохраняется не само изображение, а некоторые 

    Приложение А. Структуры хранения и методы доступа	713 

кодированные значения, которые следует использовать во фрактальных 
уравнениях для восстановления всего изображения. Согласно этой методике 
коэффициент сжатия может достигать величины 10 000 и выше. 

    Ответы к некоторым упражнениям 

    А.5. Ниже перечислены преимущества использования индексов. 
    • Ускорение прямого доступа на основе заданного значения индексированного 
поля или комбинации полей. Без индексирования потребовалось бы использовать 
последовательный просмотр. 
    • Ускорение последовательного доступа на основе заданного значения 
индексированного поля или комбинации полей. Без индексирования потребовалось 
бы использовать сортировку. 
    Среди недостатков можно указать следующие: 
    • На диске требуется выделить дополнительное пространство для размещения 
индексов, причем этот размер при значительном индексировании может превышать 
размер пространства, занимаемого данными. 
    • Хотя индексирование, вероятно, ускоряет операции извлечения данных, оно 
также способствует замедлению операций обновления. Для любой вставки или 
удаления записей из индексируемого файла или обновлении индексированного поля 
или комбинации полей требуется соответствующее обновление индекса. 
    А.6, Для поддержки желаемой кластеризации в СУБД должно быть предусмотрено 
задание физического места для вставки новой записи о поставщике. Это 
требование, в сущности, соответствует требованию найти некоторую запись по 
заданному значению поля кластеризации. Иначе говоря, в СУБД должна быть 
предусмотрена соответствующая схема доступа, например индексирование, 
основанная на поле кластеризации. 

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

    А.7, Допустим, задана хеш-функция h и требуется извлечь запись со 
значением хешируемого поля k. 
    • Очевидным недостатком является то, что сразу неясно, сохранена ли нужная 
запись согласно хеш-адресу или в результате коллизии из-за переполнения запись 
сохранена по другому хеш-адресу. Конечно, эту ситуацию можно легко разрешить 
путем проверки значения хеш-поля для данной хранимой записи. 
    • Другая проблема состоит в том, что для заданного значения h(k) следует 
определить, в какой момент нужно прекратить последовательный поиск заданной 
строки. Эту проблему можно разрешить с помощью задания соответствующего флага 
в префиксе хранимой записи. 
    • Наконец, как указано в разделе о расширяемом хешировании, при 
переполнении хранимого файла весьма вероятно, что большинство записей будет 
располагаться не по их хеш-адресам, а по другим хеш-адресам, измененным 
вследствие переполнения. Если запись rl переполняется и сохраняется по 
хеш-адресу И2, то существует вероятность, что запись г2 со значением 
хеш-функции h2 вследствие данного переполнения может быть перенаправлена по 
адресу ИЗ, хотя на самом деле может оказаться, что ни 

    714	Приложения 

одна из записей не была непосредственно задана по хеш-адресу h2. Иначе 
говоря, при разрешении одних коллизий могут возникать другие коллизии, в 
результате чего может значительно возрасти время доступа. 
    А.9. а) 3; б) 6 (например, если есть четыре поля А, В, С, D и для 
обозначения типа индексации используется комбинация из имен полей, то будет 
достаточно индексов ABCD, BCDA, CDAB, DABC, ACBD, BDAC); в) вообще, число 
требуемых индексов равняется числу вариантов выбора п элементов из набора N 
элементов (где п — наименьшее целое число, которое больше или равно N12), т.е. 
оно равно N\l(n\*(N-n)\). Доказательство этого утверждения можно найти в 
работе Лума (Lum) [A.21]. 
    АЛО. Число уровней Б-дерева является положительным целым числом k, таким 
что nk~' < N<nk. Логарифмируя это соотношение по основанию п, получим k—1 < 
lognW < k, следовательно 
    k = cz\\(\ognN), где ceil(jc) — наименьшее целое число, которое больше или 
равно х. 
    Теперь допустим, что число страниц на /-м уровне индекса равно Р, (где / = 
1 соответствует самому низкому уровню). Можно показать, что 

    '•~<а 

    и, следовательно, общее число страниц равно 

    /=* JN^ 
    ill 
    Zceil| 
    U' 

    Рассмотрим выражение 

    ceil 
    •iW 
    ceil — 
    U'J 
    п 
    
    V	J 

    Предположим , что N = qti + r (О < г < п'-\). Тогда а) если г=0, 
    б) если r>Q, 

    •if N 
    = ceil 
    Jq + l x = ceil -—— 
    V   n 

    Приложение А. Структуры хранения и методы доступа 715 

    Предположим, что q = q'n + г' (О < г' < п -1), Тогда 

    N = (q'n + r')ri +r = q'nM + (r'ri +r), 

    а так как 0 < г' < п' -1 и 0 < г' < п -1, то 

    О < (г У +г)< пм -(п'-пм)< пм, 

    следовательно 

    N 
    ,,ceil( —— Ц' + 1, 
    Но 
    ../Уи + г' + Г х ~ ceil -————— 
    = д' + 1, 

    так как 1 < г' 4-1 < /7, Таким образом, в обоих случаях — (а) и (б) — полу
    чаем соотношение 

    ceil 
    ,/ЛЛ 
    се"Ы 
    = ceil 
    ./ N 
    V п 
    /41 

    Отсюда следует, что Р\ = cei\(N/n), а также Р\+\ — ceil(f,/w), 1 ? i < k. 
Таким образом, если Р, ~ ceil(/V/«'), то 

    />   =ceil 
    ( -/"V ceil — U'J 
    п	^•^.ii       . U' 

    A.ll. 
    Остальное доказывается методом индукции. Значения, записанные в индексе    

    Расширенная форма записи 

    О - 2 - АЬ	ДЬ 
    1 - 3 - eke	Acke 
    3 - 1 - г	Ackr 
    1 — 7 — dams,T+	Adams, TR 
    5 — 1 — о	Adamso 
    1-1-1	Al 
    1 - 1 - у	Ay 
    0 — 7 - Bailey,	Bailey, 
    6 - 1 — m	Baileym 

    Комментарии к приведенным значениям. 

    1,  Два числа, предшествующие каждому записанному значению, представляю! 
соответственно число начальных символов записи, которые совпадают с начальными 
символами предыдущей записи, и число действительно сохраненных символов. 

    716 Приложения 


    2.   Расширенная форма записи демонстрирует, какое значение может 
соответствовать данному индексу (при последовательном просмотре) без учета 
индексных записей. 
    3.   Знак "+" в четвертой строке обозначает конечный пробел. 
    4.   Предполагается, что следующее значение индексного поля не содержит 
строку "Baileym" в качестве семи начальных символов. 
    Эффективность экономии пространства при хранении этих данных равна 100*( 
150-35)/!50 = 76,67 %. 
    Алгоритм индексного поиска приводится ниже; предполагается, что У — это 
некоторое искомое значение (с конечными пробелами для полного заполнения поля 
длиной 15 символов). 
    found := false ; /* значение не найдено */ do for each index entry in turn 
; /* цикл для каждого значения индекса */ expand current index entry and let 
expanded length = N ; /* расширить закодированное значение */ /* индекса до 
длины N */ 
    if expanded entry = leftmost N characters of V /* если расширенное 
значение индекса */ /* совпадает с N самыми левыми символами V */ then do ; 
    /* тогда выполнить следующие действия */ 
    retrieve corresponding stored record ; 
    /* извлечь совпадающую запись */ if value in that record = V 
    I* если значение записи = V */ then found := true ; 
    /* тогда запись найдена */ leave loop ; 
    /* завершить выполнение цикла */ 
    end ; if expanded entry > leftmost N characters of V 
    /* если расширенное значение индекса */ 
    /* не совпадает с N самыми левыми символами V */ then leave loop ; 
    /* тогда завершить выполнение цикла */ end ; 
    if found = false /* если значение не найдено */ then /* нет хранимых 
записей для значения V * I ; else /* хранимая запись для значения V найдена */ ; 
    При поиске значения "Ackroyd, s" соответствующее значение будет найдено на 
третьей итерации; после извлечения соответствующей записи будет сделано 
заключение о их полном соответствии. 
    При поиске значения "Adams,v" после выполнения шестой итерации никаких 
соответствующих записей найдено не будет. 
    При поиске значения "Aiiingham,M" соответствующее ему значение будет 
найдено после седьмой итерации, т.е. это запись со значением "Alien, s", 
следовательно, значение "Aiiingham,M" необходимо вставить возле значения 
"Mien, s". (Однако предполагается, что значения индексного поля уникальны.) 
Для вставки значения "Aiiingham,^' необходимо выполнить перечисленные ниже 
действия. 1. Найти свободное пространство и сохранить в нем новую запись. 

    Приложение А. Структуры хранения и методы доступа	717 

    2.   Вставить в список индексов для значения "Alien, s" следующее новое значение: 
    1 - 3 - Не 
    3.  Вставить в список индексов между значениями индексов для записей 
    "Alien, s" и "Аугез,зт" новое значение: 
    3 - 1 - а 

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

    718 Приложения 

