В чем отличие индексно прямых файлов от индексно последовательных файлов
Объектно-ориентированная модель ; объект-элемент; атрибут объекта; объектное множество; лексическое объектное множество; абстрактное объектное множество.
Суррогатный ключ; составное объектное множество.
Отношение; мощность отношений; отношение “один-к-одному”, “один-ко-многим”, “много-ко-многим”.
Реляционная модель данных; таблицы и связи; атрибут реляционной таблицы; область атрибута; кортеж.
Рекурсивное отношение; порядок отношения; первичный ключ; потенциальный ключ; внешний ключ; составной ключ.
Реляционная схема базы данных.
Ограничительная условия, избыток данных. Аномалия обновления; аномалия ввода; аномалия удаления.
Целостность базы данных. Правило категорной целостности. Правило целостности на уровне ссылок.
Нормализация база данных. 1,2,3 нормальные формы; детерминант; проекция реляционной таблицы ; разбиение реляционной таблицы.
18.Преобразование концептуальной схемы в реляционную.
Распределённая обработка данных. Транзакция.
Модели “клиент - сервер” в технологии баз данных
Структурированный язык запросов SQL;основные команды
1.Информация. Необходимость управления информацией.
Под данными подразумеваются разрозненные факты, например: Корпорация Microsoft находится в США. Информация же – это обработанные данные. Информация полезна руководителям в вопросах принятия решений.
Серьезность влияния, оказываемого информацией на планирование и принятие решений, привела к пониманию того, что информация – ресурс, обладающий определенной ценностью, и, следовательно, нуждается в упорядочении и управлении. Если менеджеры хорошо информированы, то они с большей вероятностью будут принимать своевременные решения. Появившиеся информационные системы, использующие базы данных, стали основополагающим средством снабжения менеджеров точной и своевременной информацией.
Система обработки данных. Информационная система.
Информационные системы (ИС) – функционирующий на основе ЭВМ и других технических средств информатики комплекс, обеспечивающий сбор, хранение, актуализацию и обработку информации в целях поддержки какого- либо вида деятельности. Другими словами: информационная система – автоматизированная система, организующая данные и выдающая информацию.
Информационная система представляет собой программно-аппаратный комплекс, обеспечивающий выполнение следующих функций:
- надежное хранение информации в памяти компьютера;
- выполнение специфических для данного приложения преобразований информации и вычислений;
- предоставление пользователям удобного и легко осваиваемого интерфейса.
К числу основных компонентов такой системы относятся средства программного обеспечения, средства компьютеров или сети компьютеров, лингвистические средства интерфейсов пользователей, собственно информационные ресурсы, которые хранит и обрабатывает система.
Последовательный, произвольный доступ к данным. Индексно-последовательные файлы.
Первые коммерческие компьютерные системы использовались в основном для ведения бухгалтерии. Затраты ручного труда на эту работу столь велики, что стоимость компьютерных систем быстро окупалась. Так как эти системы выполняли обычные работы с документами, они были названы системами обработки данных. Компьютерные файлы соответствовали папкам для бумаг. Эти файлы допускали только последовательный доступ. Это означает, что каждая запись в файле может быть прочитана только после того, как прочитаны все предшествующие ей записи. В 60-е годы, когда хранение информации на диске обходилось относительно дорого, большинство файлов хранилось на ленте, и записи извлекались и обрабатывались последовательно.
С появлением магнитных дисков началась история систем управления данными во внешней памяти. Появилась необходимость произвольного доступа к записям в файле. Произвольный доступ к данным – возможность напрямую обращаться к конкретной записи без предварительной сортировки или последовательного чтения всех записей.
В шестидесятые годы прошлого века широко распространились индексные файлы. Эти файлы позволяют выбрать одно или несколько полей для точного задания того, какую запись извлекать. Эти поля были названы ключами.
Файлы с плотным индексом называются также индексно-прямыми файлами, а файлы с неплотным индексом называются также индексно-последовательными файлами.
Файловые системы и их недостатки.
Файловая система — порядок, определяющий способ организации, хранения и именования данных на носителях информации в компьютерах, а также в другом электронном оборудовании. Файловая система определяет формат содержимого и способ физического хранения информации, которую принято группировать в виде файлов. Конкретная файловая система определяет размер имени файла (папки), максимальный возможный размер файла и раздела, набор атрибутов файла.
Несмотря на появление файлов с произвольным доступом, быстро стало очевидным, что файловые системы любого типа обладают некоторыми недостатками.
1. Избыточность данных. Многие приложения используют свои собственные файлы данных, и следовательно, одна и та же единица данных повторяется в различных файлах.
2. Слабый контроль данных. В файловой системе нет централизованного контроля. Один и тот же элемент данных может иметь различные имена, терминология в различных отделах может быть разной.
3. Недостаточные возможности управления данными. Индексные файлы позволяют обращаться к определенной записи по ключу. Этого достаточно до тех пор, пока нам нужна отдельная запись. Если же нам нужен набор связанных данных, то такую информацию трудно или даже невозможно извлечь из файловой системы.
4. Следующей причиной стала необходимость обеспечения эффективной параллельной работы многих пользователей с одними и теми же файлами.
База данных. Система управления БД. Компоненты системы БД.
База данных (БД) – упорядоченный набор хранимых данных, связанных общей темой или назначением. Основное назначение базы данных – быстрый поиск содержащейся в ней информации.
Система управления базами данных (СУБД) – программное обеспечение, осуществляющее управление базой данных.
Программа, выполняющая конкретную практическую задачу в бизнесе, называется прикладной программой или приложением. Набор таких программ, совместно выполняющих связанные задачи, называется прикладной системой. В нашем контексте программы, с помощью которых пользователи работают с базой данных будем называть приложениями.
Информационная система, использующая базы данных, или система баз данных состоит из четырех компонентов: оборудования, программного обеспечения (СУБД), данных (БД) и людей (пользователи, администрация, обслуживающий персонал).
Реляционная схема базы данных.
Monitory (ID_tovara, Model_monitora, ID_proizvoditelya, ID_diagonali, Cena, ID_postavwika)
Внешние ключи: Proizvoditel - ID_proizvoditelya
Proizvoditel ( ID_proizvoditelya, Proizvoditel)
Postavwik (ID_postavwika, Postavwik)
Harakteristiki (ID_diagonali, Diagonal, Maxs_razrewenie)
Модели “клиент - сервер” в технологии баз данных
Информация. Необходимость управления информацией.
Система обработки данных. Информационная система.
Последовательный, произвольный доступ к данным. Индексно-последовательные файлы.
Несмотря на высокую эффективность хэш-адресации, в файловых структурах далеко не всегда удается найти соответствующую функцию, поэтому при организации доступа по первичному ключу широко используются индексные файлы. В некоторых коммерческих системах индексными файлами называются также и файлы, организованные в виде инвертированных списков, которые используются для доступа по вторичному ключу. Мы будем придерживаться классической интерпретации индексных файлов и надеемся, что если вы столкнетесь с иной интерпретацией, то сумеете разобраться в сути, несмотря на некоторую путаницу в терминологии. Наверное, это отчасти связано с тем, что область баз данных является достаточно молодой областью знаний, и несмотря на то, что здесь уже выработалась определенная терминология, многие поставщики коммерческих СУБД предпочитают свой упрощенный сленг при описании собственных продуктов. Иногда это связано с тем, что в целях рекламы они не хотят ссылаться на старые, хорошо известные модели и методы организации информации в системе, а изобретают новые названия при описании своих моделей, тем самым пытаясь разрекламировать эффективность своих продуктов. Хорошее знание принципов организации данных поможет вам объективно оценивать решения, предлагаемые поставщиками современных СУБД, и не попадаться на рекламные крючки.
Индексные файлы можно представить как файлы, состоящие из двух частей. Это не обязательно физическое совмещение этих двух частей в одном файле, в большинстве случаев индексная область образует отдельный индексный файл, а основная область образует файл, для которого создается индекс. Но нам удобнее рассматривать эти две части совместно, так как именно взаимодействие этих частей и определяет использование механизма индексации для ускорения доступа к записям.
Мы предполагаем, что сначала идет индексная область, которая занимает некоторое целое число блоков, а затем идет основная область, в которой последовательно расположены все записи файла.
В зависимости от организации индексной и основной областей различают 2 типа файлов: с плотным индексом и с неплотным индексом. Эти файлы имеют еще дополнительные названия, которые напрямую связаны с методами доступа к произвольной записи, которые поддерживаются данными файловыми структурами.
Файлы с плотным индексом называются также индексно-прямыми файлами, а файлы с неплотным индексом называются также индексно-последовательными файлами. Смысл этих названий нам будет ясен после того, как мы более подробно рассмотрим механизмы организации данных файлов.
Файлы с плотным индексом, или индексно-прямые файлы
Рассмотрим файлы с плотным индексом. В этих файлах основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, а структура индексной записи в них имеет следующий вид:
Здесь значение ключа — это значение первичного ключа, а номер записи — это порядковый номер записи в основной области, которая имеет данное значение первичного ключа.
Длина записи файла (LZ) — 128 байт. Длина первичного ключа (LZ) — 12 байт. Количество записей в файле (К2) — 100000. Размер блока (LZ) — 1024 байт.
Рассчитаем размер индексной записи. Для представления целого числа в пределах 100000 нам потребуется 3 байта, можем считать, что у нас допустима только четная адресация, поэтому нам надо отвести 4 байта для хранения номера записи, тогда длина индексной записи будет равна сумме размера ключа и ссылки на номер записи, то есть:
и = ПС + 4 = I4 + 4 = 16 байт.
Определим количество индексных блоков, которое требуется для обеспечения ссылок на заданное количество записей. Для этого сначала определим, сколько индексных записей может храниться в одном блоке:
КI2В = LB/LI = 1024/16 = 64 индексных записи в одном блоке. Теперь определим необходимое количество индексных блоков: КIВ - К2/К2IВ = 100000/64 - 1563 блока.
Мы округлили в большую сторону, потому что пространство выделяется целыми блоками, и последний блок у нас будет заполнен не полностью.
А теперь мы уже можем вычислить максимальное количество обращений к диску при поиске произвольной записи:
Тпоиска = log2КIВ + 1 = log21563 +1 = 11 + 1 = 12 обращений к диску.
Логарифм мы тоже округляем, так как считаем количество обращений, а оно должно быть целым числом.
Следовательно, для поиска произвольной записи по первичному ключу при организации плотного индекса потребуется не более 12 обращений к диску. А теперь оценим, какой выигрыш мы получаем, ведь организация индекса связана с дополнительными накладными расходами на его поддержку, поэтому такая организация может быть оправдана только в том случае, когда она действительно дает значительный выигрыш. Если бы мы не создавали индексное пространство, то при произвольном хранении записей в основной области нам бы в худшем случае было необходимо просмотреть все блоки, в которых хранится файл, временем просмотра записей внутри блока мы пренебрегаем, так как этот процесс происходит в оперативной памяти.
Количество блоков, которое необходимо для хранения всех 100 000 записей, мы определим по следующей формуле:
КВО = К2/(LB/LZ) - 100000/(1024/128) - 12500 блоков.
И это означает, что максимальное время доступа равно 12500 обращений к диску. Да, действительно, выигрыш существенный.
Рассмотрим, как осуществляются операции добавления и удаления новых записей.
При операции добавления осуществляется запись в конец основной области. В индексной области необходимо произвести занесение информации в конкретное место, чтобы не нарушать упорядоченности. Поэтому вся индексная область файла разбивается на блоки и при начальном заполнении в каждом блоке остается свободная область (процент расширения) (рис. 9.7):
Рис. 9.7. Пример организации файла с плотным индексом
После определения блока, в который должен быть занесен индекс, этот блок копируется в оперативную память, там он модифицируется путем вставки в нужное место новой записи (благо в оперативной памяти это делается на несколько порядков быстрее, чем на диске) и, измененный, записывается обратно на диск.
Определим максимальное количество обращений к диску, которое требуется при добавлении записи, — это количество обращений, необходимое для поиска записи плюс одно обращение для занесения измененного индексного блока и плюс одно обращение для занесения записи в основную область.
Тдобавления = log2 +1 + 1 + 1.
Естественно, в процессе добавления новых записей процент расширения постоянно уменьшается. Когда исчезает свободная область, возникает переполнение индексной области. В этом случае возможны два решения: либо перестроить заново индексную область, либо организовать область переполнения для индексной области, в которой будут храниться не поместившиеся в основную область записи. Однако первый способ потребует дополнительного времени на перестройку индексной области, а второй увеличит время на доступ к произвольной записи и потребует организации дополнительных ссылок в блоках на область переполнения.
Именно поэтому при проектировании физической базы данных так важно заранее как можно точнее определить объемы хранимой информации, спрогнозировать ее рост и предусмотреть соответствующее расширение области хранения.
При удалении записи возникает следующая последовательность действий: запись в основной области помечается как удаленная (отсутствующая), в индексной области соответствующий индекс уничтожается физически, то есть записи, следующие за удаленной записью, перемещаются на ее место и блок, в котором хранился данный индекс, заново записывается на диск. При этом количество обращений к диску для этой операции такое же, как и при добавлении новой записи.
Индекс – это структура данных кот помогает СУБД обнаружить отдельные записи => ускоряет время выполнения запроса.
Индексные файлы состоят из 2-х частей, эти части не обязательно совмещены физически. 1) Индексная; 2) Содержит записи файла.
Индекс исключает последовательное сканирование файлов. В зависимости от организации индексной и основной части различают 2 типа файлов:
1)С плотным индексом (индексно-прямые);
2)С не плотным разделенным индексом (индексно-последовательные).
При использовании индексных файлов используются следующий принцип распределения файлов на диске:
1) Файлы ОС должны быть отделены от файлов БД.
2) Основные файлы БД должны быть отделены от индексных файлов.
Значение в индексных файлах упорядочены по полю индексирования, кот обычно строится на базе одного атрибута. Если файл данных имеет последовательное упорядочивание, а поле индексирования является ключевым, то индекс назыв первичным индексом.
Если файл являясь упорядоченным, а поле индексирования не является ключевым, то индекс является вторичным или индексом кластеризации.
В индексном файле может быть один первичный и несколько вторичных индексов.
Индексно-прямые файлы (файлы с плотным индексом)
Состоят из записей одинаковой длины расположенных в произвольном порядке. Структура индексной части имеет вид: значение ключа, потом №записи. При последовательном просмотре БД 12500 обращений к диску. При индексно прямом – 12 обращений к диску. Операции добавления и удаления новых записей. Для добавления новых записей необходимо определить положение новой записи и найти место для всиавки. В индексной области необходимо занести информ в контекстное меню. Индексная обл разбивается на блоки и в каждом блоке оставляется свободная обл (% расширения). При вставке нужный блок модифицируется в памяти и в измененном виде записывается обратно на диск. Когда % расширения исчерпан возникает переполнение индексной обл. В этом случае поступают 2-мя способами: 1) Выполняется модификация всей индексной обл, выделяются заново блока, и заново выделяется % расширения («-» большой расход машинного времени). 2) Организовать обл переполнения для индексной обл («-» увеличивается время доступа к произвольной записи).
Обл переполнения – временный не отсортированный файл называемый файлом переполнения или файлом трансакции. При вставке записи, при нулевом % расширения записывается в файл трансакции кот. периодически сливается с основным отсортированным файлом. Таким образом операции вставки выполняются более эффективно, а операции извлечения данных дольше. При удалении записи выполн последовательность действий: 1)Запись основной обл. помечается как удаленная; 2) В индексном файле соответствующий индекс уничтожается физически; 3) Записи в индексном файле перемещаются заполняя пустое место, следовательно переписывается блок.
Отсортированный файл данных с первичным индексом. Эта структура явл компромиссом м/д файлами с последовательной и произвольной организацией. В этих файлах данные могут обрабатываться как последовательным так и прямым доступом, который выполняется поиском по заданному ключевому значению с использованием индекса.
Индексно-последовательный файл имеет более сложную структуру, которая обычно включает: первичную область хранения, отдельный индекс или последовательность индексов, область переполнения.
Не плотный индекс строится для упорядоченных файлов. В индексной обл мы ищем нужный блок по заданному значению первичного ключа. Т.к. записи упорядочены, то значение первичной записи блока позволяет быстро определить в каком блоке находится искомая запись, все остальные действия происходят в основной области.
После нахождения нужного блока, внутри блока выполняется последовательный просмотр записей поэтому и назыв файлы индексно-последовательными.
Время доступа к произвольной записи 9 обращений к диску. При добавлении новых записей ищется требуемый блок, помещается в него запись, блок модифицируется.
Реорганизация выполняется блока основной части, а индексная область не корректируется. При возрастании индексного файла организуются многоуровневые индексы.
При этой стратегии файловое пространство не разделяется на области, но для каждой записи добавляется 2 указателя: указатель на предыдущую запись в цепочке синонимов и указатель на следующую запись в цепочке синонимов. Отсутствие соответствующей ссылки обозначается специальным символом, например нулем. Для каждой новой записи вычисляется значение хэш-функции, и если данный адрес свободен, то запись попадает на заданное место и становится первой в цепочке синонимов. Если адрес, соответствующий полученному значению хэш-функции, занят, то по наличию ссылок определяется, является ли запись, расположенная по указанному адресу, первой в цепочке синонимов. Если да, то новая запись располагается на первом свободном месте и для нее устанавливаются соответствующие ссылки: она становится второй в цепочке синонимов, на нее ссылается первая запись, а она ссылается на следующую, если таковая есть.
Если запись, которая занимает требуемое место, не является первой записью в цепочке синонимов, значит, она занимает данное место "незаконно" и при появлении "законного владельца" должна быть "выселена", то есть перемещена на новое место. Механизм перемещения аналогичен занесению новой записи, которая уже имеет синоним, занесенный в файл. Для этой записи ищется первое свободное место и корректируются соответствующие ссылки: в записи, которая является предыдущей в цепочке синонимов для перемещаемой записи, заносится указатель на новое место перемещаемой записи, указатели же в самой перемещаемой записи остаются прежние.
После перемещения "незаконной" записи вновь вносимая запись занимает свое законное место и становится первой записью в новой цепочке синонимов.
Механизмы удаления записей во многом аналогичны механизмам удаления в стратегии с областью переполнения. Однако еще раз кратко опишем их.
Если удаляемая запись является первой записью в цепочке синонимов, то после удаления на ее место перемещается следующая (вторая) запись из цепочки синонимов и проводится соответствующая корректировка указателя третьей записи в цепочке синонимов, если таковая существует.
Если же удаляется запись, которая находится в середине цепочки синонимов, то производится только корректировка указателей: в предшествующей записи указатель на удаляемую запись заменяется указателем на следующую за удаляемой запись, а в записи, следующей за удаляемой, указатель на предыдущую запись заменяется на указатель на запись, предшествующую удаляемой.
Вопросы для самостоятельной работы
- Сравнить обе стратегии и определить, какая из них будет наиболее перспективной и в каких случаях.
- Разработать алгоритмы удаления записей для первой и второй стратегий. Показать, как определяются ссылки.
Индексные файлы
Несмотря на высокую эффективность хэш-адресации, в файловых структурах далеко не всегда удается найти соответствующую функцию, поэтому при организации доступа по первичному ключу широко используются индексные файлы. В некоторых коммерческих системах индексными файлами называются также и файлы, организованные в виде инвертированных списков, которые используются для доступа по вторичному ключу. Мы будем придерживаться классической интерпретации индексных файлов и надеемся, что если вы столкнетесь с иной
интерпретацией, то сумеете разобраться в сути, несмотря на некоторую путаницу в терминологии. Наверное, это отчасти связано с тем, что область баз данных является достаточно молодой областью знаний, и несмотря на то, что здесь уже выработалась определенная терминология, многие поставщики коммерческих СУБД предпочитают свой упрощенный сленг при описании собственных продуктов. Иногда это связано с тем, что в целях рекламы они не хотят ссылаться на старые, хорошо известные модели и методы организации информации в системе, а изобретают новые названия при описании своих моделей, тем самым пытаясь разрекламировать эффективность своих продуктов. Хорошее знание принципов организации данных поможет вам объективно оценивать решения, предлагаемые поставщиками современных СУБД , и не попадаться на рекламные крючки.
Индексные файлы можно представить как файлы, состоящие из двух частей. Это не обязательно физическое совмещение этих двух частей в одном файле, в большинстве случаев индексная область образует отдельный индексный файл , а основная область образует файл , для которого создается индекс . Но нам удобнее рассматривать эти две части совместно, так как именно взаимодействие этих частей и определяет использование механизма индексации для ускорения доступа к записям.
Мы предполагаем, что сначала идет индексная область, которая занимает некоторое целое число блоков, а затем идет основная область, в которой последовательно расположены все записи файла.
В зависимости от организации индексной и основной областей различают 2 типа файлов: с плотным индексом и с неплотным индексом.Эти файлы имеют еще дополнительные названия, которые напрямую связаны c методами доступа к произвольной записи, которые поддерживаются данными файловыми структурами.
Файлы с плотным индексом называются также индексно-прямыми файлами, а файлы с неплотным индексом называются также индексно-последовательными файлами. Смысл этих названий нам будет ясен после того, как мы более подробно рассмотрим механизмы организации данных файлов.
Файлы с плотным индексом, или индексно-прямые файлы
Рассмотрим файлы с плотным индексом.В этих файлах основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, а структура индексной записи в них имеет следующий вид:
Здесь значение ключа — это значение первичного ключа, а номер записи — это порядковый номер записи в основной области, которая имеет данное значение первичного ключа.
Так как индексные файлы строятся для первичных ключей, однозначно определяющих запись, то в них не может быть двух записей, имеющих одинаковые значения первичного ключа. В индексных файлах с плотным индексом для каждой
записи в основной области существует одна запись из индексной области. Все записи в индексной области упорядочены по значению ключа, поэтому можно применить более эффективные способы поиска в упорядоченном пространстве.
Длина доступа к произвольной записи оценивается не в абсолютных значениях, а в количестве обращений к устройству внешней памяти , которым обычно является диск. Именно обращение к диску является наиболее длительной операцией по сравнению со всеми обработками в оперативной памяти.
Наиболее эффективным алгоритмом поиска на упорядоченном массиве является логарифмический, или бинарный, поиск . Очень хорошо изложил этот алгоритм барон Мюнхгаузен, когда он объяснял, как поймать льва в пустыне. При этом все пространство поиска разбивается пополам, и так как оно строго упорядочено, то определяется сначала, не является ли элемент искомым, а если нет, то в какой половине его надо искать. Следующим шагом мы определенную половину также делим пополам и производим аналогичные сравнения, и т. д., пока не обнаружим искомый элемент. Максимальное количество шагов поиска определяется двоичным логарифмом от общего числа элементов в искомом пространстве поиска:
где N — число элементов.
Однако в нашем случае является существенным только число обращений к диску при поиске записи по заданному значению первичного ключа. Поиск происходит в индексной области, где применяется двоичный алгоритм поиска индексной записи, а потом путем прямой адресации мы обращаемся к основной области уже по конкретному номеру записи. Для того чтобы оценить максимальное время доступа, нам надо определить количество обращений к диску для поиска произвольной записи.
На диске записи файлов хранятся в блоках. Размер блока определяется физическими особенностями дискового контроллера и операционной системой. В одном блоке могут размещаться несколько записей. Поэтому нам надо определить количество индексных блоков, которое потребуется для размещения всех требуемых индексных записей, а потому максимальное число обращений к диску будет равно двоичному логарифму от заданного числа блоков плюс единица. Зачем нужна единица? После поиска номера записи в индексной области мы должны еще обратиться к основной области файла. Поэтому формула для вычисления максимального времени доступа в количестве обращений к диску выглядит следующим образом:
Давайте рассмотрим конкретный пример и сравним время доступа при последовательном просмотре и при организации плотного индекса.
Допустим, что мы имеем следующие исходные данные:
Длина записи файла ( LZ ) — 128 байт. Длина первичного ключа ( LK ) — 12 байт. Количество записей в файле ( KZ ) — 100000. Размер блока ( LB ) — 1024 байт.
Рассчитаем размер индексной записи. Для представления целого числа в пределах 100000 нам потребуется 3 байта, можем считать, что у нас допустима только четная адресация, поэтому нам надо отвести 4 байта для хранения номера записи, тогда длина индексной записи будет равна сумме размера ключа и ссылки на номер записи, то есть:
LI = LK + 4 = I2 + 4 = 16 байт .
Определим количество индексных блоков, которое требуется для обеспечения ссылок на заданное количество записей. Для этого сначала определим, сколько индексных записей может храниться в одном блоке:
KIZB = LB/LI = 1024/16 = 64 индексных записи в одном блоке .
Теперь определим необходимое количество индексных блоков:
KIB = KZ/KZIB = 100000/64 = 1563 блока .
Мы округлили в большую сторону, потому что пространство выделяется целыми блоками, и последний блок у нас будет заполнен не полностью.
А теперь мы уже можем вычислить максимальное количество обращений к диску при поиске произвольной записи:
Tпоиска = log2KIB + 1 = log21563 + 1 = 11 + 1 = 12 обращений к диску .
Логарифм мы тоже округляем, так как считаем количество обращений, а оно должно быть целым числом.
Следовательно, для поиска произвольной записи по первичному ключу при организации плотного индекса потребуется не более 12 обращений к диску. А теперь оценим, какой выигрыш мы получаем, ведь организация индекса связана с дополнительными накладными расходами на его поддержку, поэтому такая организация может быть оправдана только в том случае, когда она действительно дает значительный выигрыш. Если бы мы не создавали индексное пространство, то при произвольном хранении записей в основной области нам бы в худшем случае было необходимо просмотреть все блоки, в которых хранится файл, временем просмотра записей внутри блока мы пренебрегаем, так как этот процесс происходит в оперативной памяти.
Количество блоков, которое необходимо для хранения всех 100 000 записей, мы определим по следующей формуле:
KBO = KZ/(LB/LZ) = 100000/(1024/128) = 12500 блоков .
И это означает, что максимальное время доступа равно 12500 обращений к диску. Да, действительно, выигрыш существенный.
Рассмотрим, как осуществляются операции добавления и удаления новых записей.
При операции добавления осуществляется запись в конец основной области. В индексной области необходимо произвести занесение информации в конкретное место, чтобы не нарушать упорядоченности. Поэтому вся индексная область файла разбивается на блоки и при начальном заполнении в каждом блоке остается свободная область (процент расширения) (рис. 9.7):
После определения блока, в который должен быть занесен индекс, этот блок копируется в оперативную память, там он модифицируется путем вставки в нужное место новой записи (благо в оперативной памяти это делается на несколько порядков быстрее, чем на диске) и, измененный, записывается обратно на диск.
Определим максимальное количество обращений к диску, которое требуется при добавлении записи, — это количество обращений, необходимое для поиска записи плюс одно обращение для занесения измененного индексного блока и плюс одно обращение для занесения записи в основную область.
T добавления = log2N + 1 + 1 + 1 .
Естественно, в процессе добавления новых записей процент расширения постоянно уменьшается. Когда исчезает свободная область, возникает переполнение индексной области. В этом случае возможны два решения: либо перестроить заново индексную область, либо организовать область переполнения для индексной области, в которой будут храниться не поместившиеся в основную область записи. Однако первый способ потребует дополнительного времени на перестройку индексной области, а второй увеличит время на доступ к произвольной записи и потребует организации дополнительных ссылок в блоках на область переполнения.
Именно поэтому при проектировании физической базы данных так важно заранее как можно точнее определить объемы хранимой информации, спрогнозировать ее рост и предусмотреть соответствующее расширение области хранения.
При удалении записи возникает следующая последовательность действий: запись в основной области помечается как удаленная (отсутствующая), в индексной области соответствующий индекс уничтожается физически, то есть записи, следующие за удаленной записью, перемещаются на ее место и блок, в котором хранился данный индекс, заново записывается на диск. При этом количество обращений к диску для этой операции такое же, как и при добавлении новой записи.
Индексные файлы
Несмотря на высокую эффективность хэш-адресации, в файловых структурах далеко не всегда удается найти соответствующую функцию, поэтому при организации доступа по первичному ключу широко используются индексные файлы. В некоторых коммерческих системах индексными файлами называются также и файлы, организованные в виде инвертированных списков, которые используются для доступа по вторичному ключу. Мы будем придерживаться классической интерпретации индексных файлов и надеемся, что если вы столкнетесь с иной
интерпретацией, то сумеете разобраться в сути, несмотря на некоторую путаницу в терминологии. Наверное, это отчасти связано с тем, что область баз данных является достаточно молодой областью знаний, и несмотря на то, что здесь уже выработалась определенная терминология, многие поставщики коммерческих СУБД предпочитают свой упрощенный сленг при описании собственных продуктов. Иногда это связано с тем, что в целях рекламы они не хотят ссылаться на старые, хорошо известные модели и методы организации информации в системе, а изобретают новые названия при описании своих моделей, тем самым пытаясь разрекламировать эффективность своих продуктов. Хорошее знание принципов организации данных поможет вам объективно оценивать решения, предлагаемые поставщиками современных СУБД , и не попадаться на рекламные крючки.
Индексные файлы можно представить как файлы, состоящие из двух частей. Это не обязательно физическое совмещение этих двух частей в одном файле, в большинстве случаев индексная область образует отдельный индексный файл , а основная область образует файл , для которого создается индекс . Но нам удобнее рассматривать эти две части совместно, так как именно взаимодействие этих частей и определяет использование механизма индексации для ускорения доступа к записям.
Мы предполагаем, что сначала идет индексная область, которая занимает некоторое целое число блоков, а затем идет основная область, в которой последовательно расположены все записи файла.
В зависимости от организации индексной и основной областей различают 2 типа файлов: с плотным индексом и с неплотным индексом.Эти файлы имеют еще дополнительные названия, которые напрямую связаны c методами доступа к произвольной записи, которые поддерживаются данными файловыми структурами.
Файлы с плотным индексом называются также индексно-прямыми файлами, а файлы с неплотным индексом называются также индексно-последовательными файлами. Смысл этих названий нам будет ясен после того, как мы более подробно рассмотрим механизмы организации данных файлов.
Файлы с плотным индексом, или индексно-прямые файлы
Рассмотрим файлы с плотным индексом.В этих файлах основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, а структура индексной записи в них имеет следующий вид:
Здесь значение ключа — это значение первичного ключа, а номер записи — это порядковый номер записи в основной области, которая имеет данное значение первичного ключа.
Так как индексные файлы строятся для первичных ключей, однозначно определяющих запись, то в них не может быть двух записей, имеющих одинаковые значения первичного ключа. В индексных файлах с плотным индексом для каждой
записи в основной области существует одна запись из индексной области. Все записи в индексной области упорядочены по значению ключа, поэтому можно применить более эффективные способы поиска в упорядоченном пространстве.
Длина доступа к произвольной записи оценивается не в абсолютных значениях, а в количестве обращений к устройству внешней памяти , которым обычно является диск. Именно обращение к диску является наиболее длительной операцией по сравнению со всеми обработками в оперативной памяти.
Наиболее эффективным алгоритмом поиска на упорядоченном массиве является логарифмический, или бинарный, поиск . Очень хорошо изложил этот алгоритм барон Мюнхгаузен, когда он объяснял, как поймать льва в пустыне. При этом все пространство поиска разбивается пополам, и так как оно строго упорядочено, то определяется сначала, не является ли элемент искомым, а если нет, то в какой половине его надо искать. Следующим шагом мы определенную половину также делим пополам и производим аналогичные сравнения, и т. д., пока не обнаружим искомый элемент. Максимальное количество шагов поиска определяется двоичным логарифмом от общего числа элементов в искомом пространстве поиска:
где N — число элементов.
Однако в нашем случае является существенным только число обращений к диску при поиске записи по заданному значению первичного ключа. Поиск происходит в индексной области, где применяется двоичный алгоритм поиска индексной записи, а потом путем прямой адресации мы обращаемся к основной области уже по конкретному номеру записи. Для того чтобы оценить максимальное время доступа, нам надо определить количество обращений к диску для поиска произвольной записи.
На диске записи файлов хранятся в блоках. Размер блока определяется физическими особенностями дискового контроллера и операционной системой. В одном блоке могут размещаться несколько записей. Поэтому нам надо определить количество индексных блоков, которое потребуется для размещения всех требуемых индексных записей, а потому максимальное число обращений к диску будет равно двоичному логарифму от заданного числа блоков плюс единица. Зачем нужна единица? После поиска номера записи в индексной области мы должны еще обратиться к основной области файла. Поэтому формула для вычисления максимального времени доступа в количестве обращений к диску выглядит следующим образом:
Давайте рассмотрим конкретный пример и сравним время доступа при последовательном просмотре и при организации плотного индекса.
Допустим, что мы имеем следующие исходные данные:
Длина записи файла ( LZ ) — 128 байт. Длина первичного ключа ( LK ) — 12 байт. Количество записей в файле ( KZ ) — 100000. Размер блока ( LB ) — 1024 байт.
Рассчитаем размер индексной записи. Для представления целого числа в пределах 100000 нам потребуется 3 байта, можем считать, что у нас допустима только четная адресация, поэтому нам надо отвести 4 байта для хранения номера записи, тогда длина индексной записи будет равна сумме размера ключа и ссылки на номер записи, то есть:
LI = LK + 4 = I2 + 4 = 16 байт .
Определим количество индексных блоков, которое требуется для обеспечения ссылок на заданное количество записей. Для этого сначала определим, сколько индексных записей может храниться в одном блоке:
KIZB = LB/LI = 1024/16 = 64 индексных записи в одном блоке .
Теперь определим необходимое количество индексных блоков:
KIB = KZ/KZIB = 100000/64 = 1563 блока .
Мы округлили в большую сторону, потому что пространство выделяется целыми блоками, и последний блок у нас будет заполнен не полностью.
А теперь мы уже можем вычислить максимальное количество обращений к диску при поиске произвольной записи:
Tпоиска = log2KIB + 1 = log21563 + 1 = 11 + 1 = 12 обращений к диску .
Логарифм мы тоже округляем, так как считаем количество обращений, а оно должно быть целым числом.
Следовательно, для поиска произвольной записи по первичному ключу при организации плотного индекса потребуется не более 12 обращений к диску. А теперь оценим, какой выигрыш мы получаем, ведь организация индекса связана с дополнительными накладными расходами на его поддержку, поэтому такая организация может быть оправдана только в том случае, когда она действительно дает значительный выигрыш. Если бы мы не создавали индексное пространство, то при произвольном хранении записей в основной области нам бы в худшем случае было необходимо просмотреть все блоки, в которых хранится файл, временем просмотра записей внутри блока мы пренебрегаем, так как этот процесс происходит в оперативной памяти.
Количество блоков, которое необходимо для хранения всех 100 000 записей, мы определим по следующей формуле:
KBO = KZ/(LB/LZ) = 100000/(1024/128) = 12500 блоков .
И это означает, что максимальное время доступа равно 12500 обращений к диску. Да, действительно, выигрыш существенный.
Рассмотрим, как осуществляются операции добавления и удаления новых записей.
При операции добавления осуществляется запись в конец основной области. В индексной области необходимо произвести занесение информации в конкретное место, чтобы не нарушать упорядоченности. Поэтому вся индексная область файла разбивается на блоки и при начальном заполнении в каждом блоке остается свободная область (процент расширения) (рис. 9.7):
После определения блока, в который должен быть занесен индекс, этот блок копируется в оперативную память, там он модифицируется путем вставки в нужное место новой записи (благо в оперативной памяти это делается на несколько порядков быстрее, чем на диске) и, измененный, записывается обратно на диск.
Определим максимальное количество обращений к диску, которое требуется при добавлении записи, — это количество обращений, необходимое для поиска записи плюс одно обращение для занесения измененного индексного блока и плюс одно обращение для занесения записи в основную область.
T добавления = log2N + 1 + 1 + 1 .
Естественно, в процессе добавления новых записей процент расширения постоянно уменьшается. Когда исчезает свободная область, возникает переполнение индексной области. В этом случае возможны два решения: либо перестроить заново индексную область, либо организовать область переполнения для индексной области, в которой будут храниться не поместившиеся в основную область записи. Однако первый способ потребует дополнительного времени на перестройку индексной области, а второй увеличит время на доступ к произвольной записи и потребует организации дополнительных ссылок в блоках на область переполнения.
Именно поэтому при проектировании физической базы данных так важно заранее как можно точнее определить объемы хранимой информации, спрогнозировать ее рост и предусмотреть соответствующее расширение области хранения.
При удалении записи возникает следующая последовательность действий: запись в основной области помечается как удаленная (отсутствующая), в индексной области соответствующий индекс уничтожается физически, то есть записи, следующие за удаленной записью, перемещаются на ее место и блок, в котором хранился данный индекс, заново записывается на диск. При этом количество обращений к диску для этой операции такое же, как и при добавлении новой записи.
При этой стратегии файловое пространство не разделяется на области, но для каждой записи добавляется 2 указателя: указатель на предыдущую запись в цепочке синонимов и указатель на следующую запись в цепочке синонимов. Отсутствие соответствующей ссылки обозначается специальным символом, например нулем. Для каждой новой записи вычисляется значение хэш-функции, и если данный адрес свободен, то запись попадает на заданное место и становится первой в цепочке синонимов. Если адрес, соответствующий полученному значению хэш-функции, занят, то по наличию ссылок определяется, является ли запись, расположенная по указанному адресу, первой в цепочке синонимов. Если да, то новая запись располагается на первом свободном месте и для нее устанавливаются соответствующие ссылки: она становится второй в цепочке синонимов, на нее ссылается первая запись, а она ссылается на следующую, если таковая есть.
Если запись, которая занимает требуемое место, не является первой записью в цепочке синонимов, значит, она занимает данное место "незаконно" и при появлении "законного владельца" должна быть "выселена", то есть перемещена на новое место. Механизм перемещения аналогичен занесению новой записи, которая уже имеет синоним, занесенный в файл. Для этой записи ищется первое свободное место и корректируются соответствующие ссылки: в записи, которая является предыдущей в цепочке синонимов для перемещаемой записи, заносится указатель на новое место перемещаемой записи, указатели же в самой перемещаемой записи остаются прежние.
После перемещения "незаконной" записи вновь вносимая запись занимает свое законное место и становится первой записью в новой цепочке синонимов.
Механизмы удаления записей во многом аналогичны механизмам удаления в стратегии с областью переполнения. Однако еще раз кратко опишем их.
Если удаляемая запись является первой записью в цепочке синонимов, то после удаления на ее место перемещается следующая (вторая) запись из цепочки синонимов и проводится соответствующая корректировка указателя третьей записи в цепочке синонимов, если таковая существует.
Если же удаляется запись, которая находится в середине цепочки синонимов, то производится только корректировка указателей: в предшествующей записи указатель на удаляемую запись заменяется указателем на следующую за удаляемой запись, а в записи, следующей за удаляемой, указатель на предыдущую запись заменяется на указатель на запись, предшествующую удаляемой.
Вопросы для самостоятельной работы
- Сравнить обе стратегии и определить, какая из них будет наиболее перспективной и в каких случаях.
- Разработать алгоритмы удаления записей для первой и второй стратегий. Показать, как определяются ссылки.
Читайте также: