 |
|
Организация индексов в виде B-tree (В-деревьев)
Калькированный термин "B-дерево", в котором смешивается английский символ "B" и добавочное слово на русском языке, настолько устоялся в литературе, посвященной организации физического хранения данных, что я не решусь его корректировать.
Встретив как-то термин "Б-дерево", я долго его трактовала, потому что привыкла уже к устоявшемуся обозначению. Поэтому будем работать с этим термином.
Построение В-деревьев связано с простой идеей построения индекса над уже построенным индексом. Действительно, если мы построим неплотный индекс, то сама индексная область может быть рассмотрена нами как основной файл, над которым надо снова построить неплотный индекс, а потом снова над новым индексом строим следующий и так до того момента, пока не останется всего один индексный блок.
Мы в общем случае получим некоторое дерево, каждый родительский блок которого связан с одинаковым количеством подчиненных блоков, число которых равно числу индексных записей, размещаемых в одном блоке. Количество обращений к диску при этом для поиска любой записи одинаково и равно количеству уровней в построенном дереве. Такие деревья называются сбалансированными (balanсed) именно потому, что путь от корня до любого листа в этом древе одинаков. Именно термин "сбалансированное" от английского "balanced" — "сбалансированный, взвешенный" и дал название данному методу организации индекса.
Построим подобное дерево для нашего примера и рассчитаем для него количество уровней и, соответственно, количество обращений к диску.
На первом уровне число блоков равно числу блоков основной области, это нам известно, — оно равно 12 500 блоков. Второй уровень образуется из неплотного индекса, мы его тоже уже строили и вычислили, что количество блоков индексной области в этом случае равно 172 блокам. А теперь над этим вторым уровнем снова построим неплотный индекс.
Мы не будем менять длину индексной записи, а будем считать ее прежней, равной 14 байтам. Количество индексных записей в одном блоке нам тоже известно, и оно равно 73. Поэтому сразу определим, сколько блоков нам необходимо для хранения ссылок на 172 блока.
KIB3 = KIB2/KZIB = 172/73 = 3 блока
Мы снова округляем в большую сторону, потому что последний, третий, блок будет заполнен не полностью.
И над третьим уровнем строим новый, и на нем будет всего один блок, в котором будет всего три записи. Поэтому число уровней в построенном дереве равно четырем, и соответственно количество обращений к диску для доступа к произвольной записи равно четырем (рис. 9.9). Это не максимально возможное число обращений, а всегда одно и то же, одинаковое для доступа к любой записи.
Tд = Rуровн. =4
Рис. 9.9. Построенное В-дерево
Механизм добавления и удаления записи при организации индекса в виде В-дерева аналогичен механизму, применяемому в случае с неплотным индексом.
И наконец, последнее, что хотелось бы прояснить, — это наличие вторых названий для плотного и неплотного индексов.
В случае плотного индекса после определения местонахождения искомой записи доступ к ней осуществляется прямым способом по номеру записи, поэтому этот способ организации индекса и называется индексно-прямым.
В случае неплотного индекса после нахождения блока, в котором расположена искомая запись, поиск внутри блока требуемой записи происходит последовательным просмотром и сравнением всех записей блока. Поэтому способ индексации с неплотным индексом называется еще и индексно-последовательным.
Моделирование отношений "один-ко-многим" на файловых структурах
Отношение иерархии является типичным для баз данных, поэтому моделирование иерархических связей является типичным для физических моделей баз данных.
Для моделирования отношений 1:М (один-ко-многим) и М:М (многие-ко-мно-гим) на файловых структурах используется принцип организации цепочек записей внутри файла и ссылки на номера записей для нескольких взаимосвязанных файлов.
Моделирование отношения 1:М с использованием однонаправленных указателей
В этом случае связываются два файла, например F1и F2, причем предполагается, что одна запись в файле F1может быть связана с несколькими записями в файле F2. Условно это можно представить в виде, изображенном на рис. 9.10.
Рис. 9.10. Иерархическая связь между файлами
При этом файл F1в этом комплексе условно называется "Основным", а файл F2— "зависимым" или "подчиненным". Структура основного файла может быть условно представлена в виде трех областей.
"Основной файл" F1.
| Ключ | Запись | Ссылка-указатель на первую запись в "Подчиненном" файле, с которой начинается цепочка записей файла F2, связанных с данной записью файла F1 |
В подчиненном файле также к каждой записи добавляется специальный указатель, в нем хранится номер записи, которая является следующей в цепочке записей "подчиненного" файла, связанной с одной записью "основного" файла.
Таким образом, каждая запись "подчиненного файла" делится на две области: область указателя и область, содержащую собственно запись.
Структура записи "подчиненного" файла.
| Указатель на следующую запись в цепочке | Содержимое записи |
В качестве примера рассмотрим связь между преподавателями и занятиями, которые эти преподаватели проводят. В файле F1приведен список преподавателей, а в файле F2— список занятий, которые они ведут.
| F1 | ||||
| Номер записи | Ключ и остальная запись | Указатель | ||
| Иванов И. Н. … | ||||
| Петров А. А. | ||||
| Сидоров П. А. | ||||
| Яковлев В. В. | ||||
| F2 | ||||
| Номер записи | Указатель на следующую запись в цепочке | Содержимое записи | ||
| 4306 Вычислительные сети | ||||
| - | 4307 Контроль и диагностика | |||
| 4308 Вычислительные сети | ||||
| 84305 Моделирование | ||||
| - | 4309 Вычислительные сети | |||
| - | 84405 Техническая диагностика | |||
| - | ||||
В этом случае содержимое двух взаимосвязанных файлов F1и F2может быть расшифровано следующим образом: первая запись в файле F1связана с цепочкой записей файла F2, которая начинается с записи номер 1, следующая запись номер 4 и последняя запись в цепочке — запись номер 5. Последняя — потому что пятая запись не имеет ссылки на следующую запись в цепочке. Аналогично можно расшифровать и остальные связи. Если мы проведем интерпретацию данных связей на уровне предметной области, то можно утверждать, что преподаватель Иванов ведет предмет " Вычислительные сети" в группе 4306, "Моделирование" в группе 84305 и "Вычислительные сети" в группе 4309.
Аналогично могут быть расшифрованы и остальные взаимосвязанные записи.
Алгоритм нахождения нужных записей "подчиненного" файла
· Шаг 1.Ищется запись в "основном" файле в соответствии с его организацией (с помощью функции хэширования, или с использованием индексов, или другим образом). Если требуемая запись найдена, то переходим к шагу 2, в противном случае выводим сообщение об отсутствии записи основного файла.
· Шаг 2.Анализируем указатель в основном файле если он пустой, то есть стоит прочерк, значит, для этой записи нет ни одной связанной с ней записи в "подчиненном файле", и выводим соответствующее сообщение, в противном случае переходим к шагу 3.
· Шаг 3.По ссылке-указателю в найденной записи основного файла переходим прямым методом доступа по номеру записи на первую запись в цепочке "Подчиненного" файла. Переходим к шагу 4.
· Шаг 4.Анализируем текущую запись на содержание если это искомая запись, то мы заканчиваем поиск, в противном случае переходим к шагу 5.
· Шаг 5. Анализируем указатель на следующую запись в цепочке если он пуст, то выводим сообщение, что искомая запись отсутствует, и прекращаем поиск, в противном случае по ссылке-указателю переходим на следующую запись в "подчиненном файле" и снова переходим к шагу 4.
Использование цепочек записей позволяет эффективно организовывать модификацию взаимосвязанных файлов.
Алгоритм удаления записи из цепочки "подчиненного" файла
· Шаг 1.Ищется удаляемая запись в соответствии с ранее рассмотренным алгоритмом. Единственным отличием при этом является обязательное сохранение в специальной переменной номера предыдущей записи в цепочке, допустим, это переменная NP.
· Шаг 2.Запоминаем в специальной переменной указатель на следующую запись в найденной записи, например, заносим его в переменную NS. Переходим к шагу 3.
· Шаг 3.Помечаем специальным символом, например символом звездочка (*), найденную запись, то есть в позиции указателя на следующую запись в цепочке ставим символ "*" — это означает, что данная запись отсутствует, а место в файле свободно и может быть занято любой другой записью.
· Шаг 4.Переходим к записи с номером, который хранится в NP, и заменяем в ней указатель на содержимое переменной NS.
Для того чтобы эффективно использовать дисковое пространство при включении новой записи в "подчиненный файл", ищется первое свободное место, т. е. запись, помеченная символом "*", и на ее место заносится новая запись, после этого производится модификация соответствующих указателей. При этом необходимо различать 3 случая:
1. Добавление записи на первое место в цепочке.
2. Добавление записи в конец цепочки.
3. Добавление записи на заданное место в цепочке.
Задание для самостоятельной работы
Разработать алгоритмы добавления записи для всех трех случаев
Однако часто бывает необходимо просматривать цепочку подчиненных записей в двух направлениях: прямом и обратном. В этом случае применяют двойные указатели.
В "основном файле" один указатель равен номеру первой записи в цепочке записей "подчиненного файла", а второй — номеру последней записи.
В "подчиненном файле" один указатель равен номеру следующей записи в цепочке, а другой — номеру предыдущей записи в цепочке. Для первой и последней записей в цепочке один из указателей пуст, то есть равен пробелу.
Для нашего примера это выглядит следующим образом:
| F1 | ||||||
| Номер записи | Ключ и остальная запись | Указатель на первую запись | Указатель на последнюю запись | |||
| Иванов И. Н.…. | ||||||
| Петров А. А. | ||||||
| Сидоров П. А. | ||||||
| Яковлев В. В. | ||||||
| F2 | ||||||
| Номер записи | Указатель на предыдущую запись в цепочке | Указатель на следующую запись в цепочке | Содержимое записи | |||
| - | 4306 Вычислительные сети | |||||
| - | - | 4307 Контроль и диагностика | ||||
| - | 4308 Вычислительные сети | |||||
| 84305 Моделирование | ||||||
| - | 4309 Вычислительные сети | |||||
| - | 84405 Техническая диагностика | |||||
| - | ||||||
Один файл ("подчиненный" или "основной") может быть связан с несколькими другими файлами, при этом для каждой связи моделируются свои указатели. Связь двух основных файлов F1и F2с одним связующим файлом F3моделируется на
| F1 | |||||
| Ключ | Содержимое записи | Указатель на файл A | |||
| F2 | |||||
| Ключ | Содержимое | Указатель на файл A | |||
| F3 | ||
| Цепочки для файла F1 | Содержимое записи | Цепочки для файла F2 |