Организация и поиск данных во внешней памяти

бизнес-информатики
Кафедра информационных технологий в бизнесе
Пермь 2013
Лядова Л.Н.
Материалы курса «Теоретические основы

информатики»
Лекция 17

доступом;
индексированные файлы (индексно-последовательные, файлы с индексной организацией);
библиотеки.

Использование индексов ускоряет поиск

данных, но усложняет выполнение операций над ними.

файлов (таблиц), используемых для ускорения доступа, то говорят об индексной

организации файлов.
Файлы с индексной организацией (или индексированные файлы) имеют более сложную организацию: кроме основного файла, представляющего собой массив записей, строится вспомогательная таблица (индекс), содержащая ключевую информацию для поиска, а также данные о местоположении записи в основном файле (смещение соответствующей записи относительно начала файла); кроме того, если записи могут иметь переменную длину, в каждой строке (элементе, записи) индекса содержится и размер записи.
Если поиск выполняется по различным ключам, то для каждого из них строится отдельный индекс. В современных базах данных объем индексов превышает объем собственно данных.

внешних запоминающих устройствах: индексы отсортированы по ключам (по возрастанию или

убыванию), что позволяет организовать поиск, например, методом «деления пополам» (бинарный поиск).
Однако поддерживать нужный порядок записей в индексе при выполнении операций над данными в файле – трудоёмкая задача:
при добавлении новых записей в файл (данные добавляются в конец файла) необходимо в индекс внести соответствующие изменения – тоже добавить запись, содержащую ключ и информацию о местоположении новой записи в файле, не нарушая порядок сортировки индекса;
при удалении записи из файла необходимо удалить и соответствующую запись из индекса;
при изменении ключевых полей в записи необходимо изменить и соответствующую запись в индексе, при этом может потребоваться изменить порядок записей в нём для сохранения установленного порядка сортировки.

команде индексации файла и существует, пока в нём есть необходимость

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

ключом «Носкова»

уровней в обычном бинарном дереве может быть большим – требуется

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

Выход – использование для индексации другого типа деревьев – B-деревьев.

являются B-деревья:
за одно обращение к внешней памяти необходимо считать как

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

страниц внешней памяти (каждая вершина дерева – страница), обладающая следующими

свойствами:
Каждая страница содержит не более 2×n элементов (записей с ключом).
Каждая страница, кроме корневой, содержит не менее n элементов.
Если внутренняя (не листовая) вершина B-дерева содержит m ключей, то у нее имеется m+1 страниц-потомков.
Все листовые страницы находятся на одном уровне.

…

…

Необходимо расщепление страницы

…

Необходимо расщепление страницы:
32 33 35 36 37

различную структуру листовых вершин и внутренних узлов,…);
сочетание хэширования и деревьев:

в памяти строится дерево, в которое записываются не ключи, а результаты хэширования;
…

Миков А.И. Информатика. Введение в компьютерные науки. М.: Высшая школа.