Понедельник, 27.03.2023, 14:05

Вы вошли как Гость | Группа "Гости" | RSS
Главная Каталог статей
Меню сайта

Категории раздела
Администрирование информационных систем [44]
Операционные системы [0]
Архитектура [0]
Сети передачи данных [29]
ЭВМ [0]
Надежность информационных систем [0]
Безопасность [0]
Корпоративные информационные сети [6]

Liveinternet

Главная » Статьи » Информационные технологии » Сети передачи данных

Поисковые структуры в СУБД на ПК

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

Основнымисредствами физического моделирования в БнД являются:

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

2.поисковыеструктуры (чтобы сократить время поиска данных, в базе разрабатываютсяпоисковые структуры, они определяют быстрый способ нахождения записи в базе);

3.языкописания данных.

В СУБД на ПК чаще всего используют следующие типыпоисковых структур:

-  линейный список;

-  цепной список;

-  инвертированныефайлы;

-  индексные файлы.

В отличие от трех последующих типов поисковых структурлинейный список не требует создания дополнительных файлов. В соответствии сэтим способом файл БД рассматривается как последовательность невзаимосвязанныхзаписей. Поиск любой записи осуществляется путем вычисления адреса записи понекоторому алгоритму.

Достоинства: по критерию «min-памяти» он наиболее экономичный.

Недостаток: по быстродействию проигрывает остальнымспособам.

Цепной список представляет собой файл, записи которогоимеют ссылки на другие записи. Ссылками элементов являются указатели, которыевстраиваются в записи как дополнительные поля. Поле, которое выделяется подуказатель называется адресом связи. Чтобы войти в список надо указать адресначала списка (АНС).

Пример цепного списка приведем ниже:

ФС – фиксатор списка или заголовок

АС – адрес связи

 

 

АНС

 

 

 

 

 

 

 

 

 

 

          ФС

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

АС

 

 

 

АС

 

 

АС

 

АС

 

Иванов

 

 

 

Петров

 

 

Сидоров

 

 

Ястин

 

 

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

Достоинства: обеспечивает самый быстрый поиск данныхпо не ключевому полю.

Недостаток: происходит чрезмерно большое дублированиеинформации, то есть перерасход памяти.

Инвертированный по полю «год»

 

Фамилия

Год

Телефон

Должность

001

Квитко

1969

792-55-66

Техник

002

Сейфулин

1969

599-99-99

Инженер

Целесообразно создавать файлы, которые содержат вместозаписей БД адреса этих данных.

Индексный файл содержит два поля: поле, по которомуупорядочивают и поле адресов.

Год

Адрес

1969

002

 1969

003

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

БД={ФБД, [ИФ1,ИФ2,…, ИФп]}

 
Категория: Сети передачи данных | Добавил: Admin (02.10.2010)
Просмотров: 1242 | Рейтинг: 5.0/1
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Форма входа

Поиск

Поиск Google

Copyright MyCorp © 2023 Бесплатный конструктор сайтов - uCoz