Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Блочный поиск

Способы адресации данных.

 

Адресацией данных называется алгоритм, позволяющий по описанию набора данных, найти физический адрес записи. Описание элемента данных называется ключом поиска. Ключ поиска может быть простым или составным, например, книгу в библиотеке, можно найти по различным ее описания, типа, Ф.И.О. автора, название, издательство, ISBN-номер и т.д. Ключ поиска может быть уникальным, либо описывать группу записей, удовлетворяющих этому описанию (например, номенклатура деталей, относящаяся к шасси автомобиля). Если таблица БД сортирована по ключу поиска, то такой ключ называется первичным. Например, если данные о сотрудниках сортированы по фамилиям, а ищется запись, содержащая данные об Иванове П.И.

Рассмотрим различные способы адресации данных:

 

1. Последовательное сканирование файла.

Наиболее простым способом поиска является последовательный просмотр всего файла с проверкой ключа каждой записи. Этот способ требует, однако, много времени, и не применим в большинстве случаев.

 

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

Пусть N количество записей в БД, а x – количество блоков. Тогда, каждый блок должен содержать y=N/x записей. Для локализации нужной записи требуется, в среднем, просмотреть x/2 блоков для нахождения номера блока, затем в ходе последовательно сканирования просмотреть y/2 записей. Поэтому, общее число элементарных операций равно . Вычислив производную этой функции и приравняв ее к нулю, получим, что минимум этой функции достигается при x=√N (квадратный корень из N). Таким образом, размер блока при общем количестве записей, равном 10 000, должен быть равен 100.

 

<== предыдущая лекция | следующая лекция ==>
Нормализация баз данных. Алгоритм приведения к 3-й нормальной форме с помощью кольцевых зависимостей | Поиск в индексно-последовательном файле
Поделиться с друзьями:


Дата добавления: 2014-01-11; Просмотров: 1014; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.017 сек.