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

Содержание

Слайд 2

Организация файлов Основные способы организации файлов: файлы с последовательной организацией; файлы

Организация файлов

Основные способы организации файлов:
файлы с последовательной организацией;
файлы с прямым доступом;
индексированные

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

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

Индексированные файлы

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

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

Индексированные файлы: простейший пример индексации

Индексированные файлы: простейший пример индексации

Слайд 5

Индексированные файлы: многоуровневые индексы

Индексированные файлы: многоуровневые индексы

Слайд 6

Индексированные файлы: поиск и обработка данных Индексы позволяют ускорить поиск данных

Индексированные файлы: поиск и обработка данных

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

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

Индексированные файлы: динамические индексы Динамический индекс строится в оперативной памяти по

Индексированные файлы: динамические индексы

Динамический индекс строится в оперативной памяти по специальной команде

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

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Слайд 9

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Слайд 10

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Слайд 11

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Слайд 12

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Слайд 13

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Слайд 14

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Слайд 15

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Слайд 16

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Слайд 17

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Слайд 18

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Слайд 19

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память Поиск записи с ключом «Носкова»

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Поиск записи с ключом

«Носкова»
Слайд 20

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Слайд 21

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Слайд 22

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Слайд 23

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Слайд 24

Бинарные деревья: использование для индексации Ссылка на корень индекса Оперативная память

Бинарные деревья: использование для индексации

Ссылка на корень индекса

Оперативная память

Слайд 25

Бинарные деревья: использование для индексации Проблемы при работе с внешней памятью:

Бинарные деревья: использование для индексации

Проблемы при работе с внешней памятью:
Число уровней

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

Понятие B-дерева Базовым «древовидным» аппаратом для поиска данных во внешней памяти

Понятие B-дерева

Базовым «древовидным» аппаратом для поиска данных во внешней памяти являются

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

Понятие B-дерева: классические B-деревья B-дерево порядка n представляет собой совокупность иерархически

Понятие B-дерева: классические B-деревья

B-дерево порядка n представляет собой совокупность иерархически связанных страниц

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

Пример B-дерева степени 2 глубины 3

Пример B-дерева степени 2 глубины 3

Слайд 29

Пример B-дерева степени 2 глубины 3 Добавляем: 15, 27, 36, 39, …

Пример B-дерева степени 2 глубины 3

Добавляем:
15, 27, 36, 39, …

Слайд 30

Пример B-дерева степени 2 глубины 3 Добавляем: 15, 27, 36, 39, …

Пример B-дерева степени 2 глубины 3

Добавляем:
15, 27, 36, 39, …

Слайд 31

Пример B-дерева степени 2 глубины 3 Добавляем: 15, 27, 36, 39, …

Пример B-дерева степени 2 глубины 3

Добавляем:
15, 27, 36, 39, …

Слайд 32

Пример B-дерева степени 2 глубины 3 Добавляем: 15, 27, 36, 39, …

Пример B-дерева степени 2 глубины 3

Добавляем:
15, 27, 36, 39, …

Слайд 33

Пример B-дерева степени 2 глубины 3 Добавляем: 15, 27, 36, 39, … Необходимо расщепление страницы

Пример B-дерева степени 2 глубины 3

Добавляем:
15, 27, 36, 39, …

Необходимо

расщепление страницы
Слайд 34

Пример B-дерева степени 2 глубины 3 Добавляем: 15, 27, 36, 39,

Пример B-дерева степени 2 глубины 3

Добавляем:
15, 27, 36, 39, …

Необходимо

расщепление страницы:
32 33 35 36 37
Слайд 35

Пример B-дерева степени 2 глубины 3 Добавляем: 15, 27, 36, 39, …

Пример B-дерева степени 2 глубины 3

Добавляем:
15, 27, 36, 39, …

Слайд 36

Пример B-дерева степени 2 глубины 3 Добавляем: 15, 27, 36, 39, …

Пример B-дерева степени 2 глубины 3

Добавляем:
15, 27, 36, 39, …

Слайд 37

Пример B-дерева степени 2 глубины 3

Пример B-дерева степени 2 глубины 3

Слайд 38

Пример B-дерева степени 2 глубины 3

Пример B-дерева степени 2 глубины 3

Слайд 39

Пример B-дерева степени 2 глубины 3 Добавляем 68

Пример B-дерева степени 2 глубины 3

Добавляем 68

Слайд 40

Пример B-дерева степени 2 глубины 3 Добавляем 68

Пример B-дерева степени 2 глубины 3

Добавляем 68

Слайд 41

Пример B-дерева степени 2 глубины 3 Удаляем 25 Выполняется переливание

Пример B-дерева степени 2 глубины 3

Удаляем 25

Выполняется переливание

Слайд 42

Пример B-дерева степени 2 глубины 3 Удаляем 25

Пример B-дерева степени 2 глубины 3

Удаляем 25

Слайд 43

«Комбинированные» методы Для ускорения поиска используются «усовершенствованные» деревья (B+-деревья, R-деревья, имеющие

«Комбинированные» методы

Для ускорения поиска используются
«усовершенствованные» деревья (B+-деревья, R-деревья, имеющие различную

структуру листовых вершин и внутренних узлов,…);
сочетание хэширования и деревьев: в памяти строится дерево, в которое записываются не ключи, а результаты хэширования;
…
- Предыдущая
Понятие, предмет и методы финансового права
Следующая -
Сигналы качества» в маркетинге

Похожие презентации

Droga krzyżowa
Сравнительный анализ фазы отталкивания в различных способах прыжка в высоту с разбега у женщин
Производство суспензий и эмульсий
Понятие, цели и этапы деловой оценки персонала
Рынок и отрасль
Методы расчета статически определимых систем на постоянную нагрузку
Гипергенные процессы
Личные права супругов по состоянию на данный момент
Международное публичное право. ООН: история, структура, цели и задачи
Автономный инвертор напряжения с синусоидальным выходным напряжением
Запорожье. Бердянск вчера и сегодня. - презентация
Поймай рыбку - презентация для начальной школы
ПОЛОЖИТЕЛЬНЫЙ СТОЛБ ТЛЕЮЩЕГО РАЗРЯДА
Простейшие конструкции языка Pascal
Белаз 7519
Программирование на языке С++
Шаблон_ПРЕДПРИЯТИЯ
Кроссфит
Конденсаторы и катушки индуктивности
Короли госзаказа
Реализация проекта «Аэродинамический комплекс»
«Виды и методы контроля знаний учащихся при изучении истории и обществознания»
Разветвляющиеся алгоритмы
7 класс
Wyrusz z Chrystusem na drogę krzyżową
СПИД
Общие положения исполнения наказания
Отношения Украины и России
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть