3. Индексная организация

Записи размещаются в отведенной области произвольно, для указания местоположения и логической последовательности записей используется индекс – дополнительный линейный список. При простейшей организации индекс представляет собой фактически последовательно упорядоченный набор указателей, перемещенных из отдельных записей в единое место хранения.

Линейный связанный список с индексом

4. Хэшированная организация

Записи размещаются в отведенной области по вычисляемым адресам. Адрес хранения записи расчитывается по значениям ключа хэширования (поля или набора полей) для данной записи. Выборка записи выполняется из адреса, вычисленного для требуемого значения ключа хэширования. Таким образом, вместо поискового перебора записей выполняется прямое обращение к нужному адресу памяти. Проблемой хэшированной организации являются возможные конфликты наложения записей.

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

17. Методы поиска в бд

Производительность программной системы во многом зависит от методов доступа к данным. Поэтому, если есть возможность выбора СУБД, знание используемых в ней алгоритмов работы с данными может быть полезным.

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

Рассмотрим методы поиска подходящей записи в БД по информации, содержащейся в некотором поле записи (поиск по ключу). Типичными являются следующие методы поиска:

1. Последовательный поиск:

Записи просматриваются последовательно, начиная с первой. Для каждой записи значение поля поиска сравнивается со значением ключа поиска. Окончание поиска – по соответствию значения поля искомому значению.

В целом, последовательный поиск имеет очень низкое быстродействие и применим только для небольших таблиц. К достоинствам поиска относятся простота выполнения и универсальность, основывающаяся на отсутствии необходимости в поддержке служебных данных, упорядочиваний и т.д.

Для ускорения поиска можно использовать упорядочивание по значению записей. Выигрыш - если при просмотре запись не нашлась, то часть таблицы, которая ниже нужной, не просматривается. Но при этом проигрываем в том, что необходимо поддерживать упорядоченность.

Можно упорядочить по важности информации. И если чаще нужна наиболее важная информация, то чаще всего поиск будет заканчиваться на наиболее важной информации.

Последовательный поиск используется в последовательной и списковой организации. Метод не применяется там, где необходим быстрый доступ к данным большого объема. Но его можно использовать в тех случаях, когда по характеру задачи следует выбирать записи последовательно (например, полное копирование данных), а также при очень небольших объемах данных в силу простоты алгоритма доступа.