Файлы с плотным индексом или индексно-прямые файлы - Проблема организации и хранения данных
В этих файлах основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, а структура индексной записи в них имеет следующий вид:
Значение ключа |
Номер записи |
Здесь значение ключа -- это значение первичного ключа, а номер записи - это порядковый номер записи в основной области, которая имеет данное значение первичного ключа.
Наиболее эффективным алгоритмом поиска на упорядоченном массиве является логарифмический, или бинарный, поиск. В теории вероятности его называют методом половинного деления. Максимальное число шагов поиска определяется двоичным логарифмом от общего числа элементов (целей) в искомом пространстве поиска:
Где N - число элементов.
При поиске записей существенным является только число обращений к диску по заданному значению первичного ключа. Сначала производится поиск в индексной области, где применяется двоичный алгоритм поиска индексной записи, а затем путем прямой адресации в основной области производится поиск по номеру записи. Для того чтобы оценить максимальное время доступа к записи, необходимо определить число обращений к диску в процecce поиска.
В соответствии с формулой число обращений к диску при поиске записи определится следующим образом:
Где - число индексных блоков, в которых размещаются все записи.
Учитывая что после поиска записи в индексном блоке нужно еще раз обратиться к основной области, в формуле, добавилась единица (+1).
В табл. 1 представлена схема организации такого файла на дисковом пространстве (фоном выделены свободные зоны).
Таблица 1. Схема организации файла с плотным индексом
Блок |
Ключи |
Ссылки на № записи |
Свободная зона |
Области |
Блок 1 |
01-10/01 |
3 |
Индексная область | |
02-20/02 |
4 | |||
03-20/00 |
5 | |||
Блок 2 |
06-40/00 |
7 | ||
07-50/01 |
8 | |||
08-30/01 |
9 | |||
Блок 3 |
10-44/01 |
1 | ||
11-44/02 |
2 | |||
09-35/01 |
6 | |||
Блок 4 |
17-20/03 | |||
18-40/02 | ||||
20-35/02 | ||||
Номер записи |
Ключ |
Содержание |
Основная область | |
1 |
10-44/01 |
Математика | ||
2 |
11-44/02 |
Физика | ||
3 |
01-10/01 |
Информатика | ||
4 |
02-20/02 |
Теория информации | ||
5 |
03-20/00 |
Базы данных | ||
6 |
09-35/01 |
Интерфейс АСОиУ | ||
7 |
06-40/00 |
Защита информации | ||
8 |
07-50/01 |
АСТПП и САПР | ||
9 |
08-30/01 |
Языки программирования | ||
10 |
17-20/03 |
Операционные системы | ||
11 |
18-40/02 |
Цифровые сети интегрального обслуживания | ||
12 |
20-35/02 |
Технологии программирования |
Из табл. 1 видно, что файл организован в виде двух областей -- основной и индексной. В основной области хранятся значения ключевых полей, номера и содержание записей. В индексной области хранятся значения ключевых полей и ссылки на номер записи в основной области.
При операции добавления осуществляется запись данных в конец основной области. При этом в индексную область необходимо добавить значения соответствующего ключевого поля и ссылку на номер записи, причем добавить информацию необходимо таким образом, чтобы не нарушить порядок записей.
Такой прием организации индексной области позволяет без нарушения системы вводить новые типы изделий и присваивать им соответствующие буквенно-цифровые коды.
Именно поэтому при проектировании физической модели хранения данных необходимо как можно точнее определить объемы хранимой информации, спрогнозировать ее рост и соответственно предусмотреть соответствующее расширение области хранения.
При организации хранения данных в виде файлов с плотным индексом число обращений к диску при добавлении новой записи определится по формуле
ТN = log2 NИнд. Обл. + 1 + 1 + 1.
Смысл формулы заключается в следующем: число обращений определяется числом обращений к индексной области плюс одно обращение к основному блоку, плюс одно обращение для изменения индексного блока и плюс одно обращение для занесения записи в основную область.
Таким образом, в файлах с плотным индексом при обработке одной записи требуется дополнительно два обращения к дисковому пространству компьютера.
Следовательно, способы организации файлов баз данных и соответствующие им физические модели должны быть направлены на сокращение времени обращения к дисковому пространству при ее поиске и сокращению времени на добавление и корректировку содержания баз данных. На это и направлен метод организации файлов с неплотным индексом.
Похожие статьи
-
Структура записей данных в таких файлах имеет вид, представленный на рис. 4. Рис. 4 Структура записей данных в файлах с неплотным индексном При такой...
-
При этой стратегии файловое пространство не разделяется на области, но для каждой записи добавляются два указателя: указатель на предыдущую запись в...
-
Назначение и функции программной системы Разработанная база данных "Библиотека" предназначена для использования в учреждениях библиотек. Основной...
-
Организация кэш-памяти - Проблема организации и хранения данных
Концепция кэш-памяти возникла раньше, чем архитектура IBM/360. Сегодня кэш-память имеется практически в любом классе компьютеров, а в некоторых...
-
Разрешение коллизии с помощью области переполнения - Проблема организации и хранения данных
При выборе этой стратегии область хранения разбивается на две части: основную область и область переполнения. Для каждой новой записи вычисляется...
-
Физические модели хранения данных определяют методы размещения данных в памяти компьютера или на соответствующих носителях информации, а также способы...
-
Сегментация памяти - Проблема организации и хранения данных
В системах с сегментацией памяти каждое слово в адресном пространстве пользователя определяется виртуальным адресом, состоящим из двух частей: старшие...
-
Введение - Проблема организации и хранения данных
В деловой и личной сфере часто приходится работать с данными из разных источников, каждый из которых связан с определенным видом деятельности. Для...
-
Организация основной памяти - Проблема организации и хранения данных
Основная память в современных компьютерах представляет собой следующий уровень иерархии памяти. Основная память удовлетворяет запросы кэш-памяти и служит...
-
Виртуальная память как средство организации защиты данных - Проблема организации и хранения данных
Общепринятая в настоящее время концепция виртуальной памяти появилась достаточно давно. Она позволила решить целый ряд актуальных вопросов организации...
-
Страничная организация памяти - Проблема организации и хранения данных
В системах со страничной организацией основная и внешняя память (главным образом дисковое пространство) делятся на блоки, или страницы, фиксированной...
-
Заключение, Список использованной литературы - Проблема организации и хранения данных
Таким образом, в процессе проектирования базы данных, можно прийти к выводу, что правильная организация хранения и представления данных является...
-
Отчеты, Макросы - Проблема организации и хранения данных
Отчеты используются для отображения данных таблицы или запроса в удобном для пользователя формате (с заголовками и номерами страниц). Больше всего...
-
Формы - Проблема организации и хранения данных
Работа с данными в режиме таблицы имеет существенный недостаток: если полей слишком много, они не умещаются на экране и приходится прибегать к различным...
-
Запросы - Проблема организации и хранения данных
Запрос представляет собой специальную функцию, позволяющую выводить необходимые поля из таблицы, а также производить операции с данными полями в режиме...
-
В основе реализации организации памяти современных компьютеров лежат два принципа: принцип локальности обращений и соотношение...
-
Физические модели БД - Банки и базы данных. Системы управления базами данных
Под физической моделью БД понимается способ размещения данных на устройствах внешней памяти и способ доступа к этим данным. Каждая СУБД по-разному...
-
Основная часть, Физические модели таблиц базы данных - Проблема организации и хранения данных
Физические модели таблиц базы данных Физическая модели таблицы базы данных предполагает описание свойств каждого поля таблицы. Для описания свойств полей...
-
Ожидается, что предлагаемая библиотека даст большой прирост в производительности операций чтения, заполнив собственную нишу среди решений проблем...
-
Схема каскадирования. Организация запоминающих устройств. Для запоминания информации в цифровых схемах используется либо триггер, либо конденсатор. В...
-
Хранение, кодирование и пpеобpазование данных - Единицы измерения информации в памяти ПК
Хранение информации в памяти ЭВМ - одна из основных функций компьютера. Любая информация хранится с использованием особой символьной формы, которая...
-
1. НА 7 ПК ИСПОЛЬЗУЕТСЯ microsoft Windows xp sp2. 2. на 1 используется Altlinux 5 3. Программы офисного назначения: A) Microsoft Office Excel 2003 B)...
-
Записи, множества, файлы - Структуры данных
Обобщением массива является комбинированный тип данных - запись, являющаяся неоднородной упорядоченной статической структурой прямого доступа. Запись...
-
Структура SQL - Банки и базы данных. Системы управления базами данных
Широкое развитие информационных систем и связанная с этим унифицированность информационного пространства привело к необходимости создания стандартного...
-
Основные термины теории баз данных - БД (База данных) - совокупность специальным образом организованных данных, хранимых в памяти вычислительной системы...
-
Самым традиционным и широко известным из структурированных типов данных является массив (иначе называемый регулярным типом) - однородная упорядоченная...
-
Целостность БД - Банки и базы данных. Системы управления базами данных
Банк база данный case технология Понятие целостности является одним из основополагающих в теории БД. Любая БД содержит в себе информацию об объектах...
-
Модели информационных процессов передачи, обработки, накопления данных Обобщенная схема технологического процесса обработки информации При производстве...
-
Актуальность и постановка задачи информационной поддержки добровольческого движения Как было показано в главе 2, важная роль в формировании гражданского...
-
Файловая организация данных и ее недостатки - Технология создания и управления баз данных
В первые годы автоматизированной обработки информации, в 50-х -- начале 60-х годов, использовалась файловая организация данных. Данные хранились в файлах...
-
Организация парольной защиты - Проектирование и разработка базы данных "Прокат автомобилей"
По мере того как деятельность организаций все больше зависит от компьютерных информационных технологий, проблемы защиты баз данных становятся все более...
-
Рисунок 1. Пример сложной схемы БД Пример проблемной ситуации, которую этот проект должен разрешить представлен на рис. 1. Организатор проводит события...
-
В этом разделе описаны запросы, выполняемых всеми компонентами, а также типы данных, используемые при описании запросов. Стандарт типов данных При...
-
После обмена данными с АЦП происходит преобразование считанных данных в одно целое число, характеризующее уровень сигнала на входе АЦП. Т. к. АЦП имеет...
-
Теоретические предпосылки исследования Системы поддержки принятия решений Системы поддержки принятия решений (СППР), представляют собой приложения узкого...
-
Этапы проектирования и создания БД - Система управления базами данных
При разработке БД можно выделить следующие этапы работы. I этап. Постановка задачи. На этом этапе формируется задание по созданию БД. В нем подробно...
-
ПОСТАНОВКА ЗАДАЧИ - Структуры и алгоритмы обработки данных
Хранящуюся в файле базу данных загрузить в оперативную память компьютера и построить индексный массив, упорядочивающий данные По дням рождения и ФИО ,...
-
Сетевая модель данных, Реляционная модель данных - Система управления базами данных
Отличие сетевой структуры от иерархической заключается в том, что каждый элемент в сетевой структуре может быть связан с любым другим элементом (рис. 8)....
-
Уровни и типы моделей БД - Банки и базы данных. Системы управления базами данных
Любая БД отражает информацию об определенной предметной области. В зависимости от уровня абстракции, на котором представляется предметная область,...
-
Каждая СУБД имеет особенности в представлении структуры таблиц, связей, определении типов данных и т. д. которую необходимо учитывать при проектировании....
Файлы с плотным индексом или индексно-прямые файлы - Проблема организации и хранения данных