Механизмы поиска в БД Структуры индексов. Основные виды индексов Простые индексы для упорядоченных файлов Вторичные индексы для неупорядоченных файлов.

Презентация:



Advertisements
Похожие презентации
Механизмы поиска в БД Структуры индексов. Основные виды индексов Простые индексы для упорядоченных файлов Вторичные индексы для неупорядоченных файлов.
Advertisements

Древовидные структуры для многомерных данных 1)Индексы с несколькими ключами 2)Kd-деревья 3)Деревья квадрантов 4)R-деревья.
Хранение таблиц По строкам По столбцам Строки нескольких таблиц группируются по общему атрибуту.
Индексные файлы. Структура индексного файла Индексные файлы можно представить как файлы, состоящие из двух частей: индексная область, основная область,
Физические модели баз данных Файловые структуры, используемые для хранения информации в базах данных.
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ ЭЛЕКТРОНИКИ И МАТЕМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ) КАФЕДРА ИКТ Дипломный проект на тему: Студент: Руководитель проекта:
1 Лекция 5 Абстрактные структуры данных. 2 Таблицы Таблица – это набор элементов, содержащих ключ – отличительный признак для поиска элементов, и тело.
Ассоциативные списки Поиск данных происходит не по индексу или положению объекта, а по его ассоциативной связи: public interface Map { // Доступ к объектам.
1 Массивы 2 Опр. Массивом называется совокупность однотипных данных, связанных общим именем. Основные характеристики массива: 1. Имя массива 2. Тип компонентов.
Коллекции классов Лекция 12. С помощью коллекций вместо создания структур данных программист использует готовые структуры данных, не заботясь об их реализации.
БАЗЫ ДАННЫХ. Тест.. БАЗЫ ДАННЫХ. 1. База данных - это: А. совокупность данных, организованных по определенным правилам; Б. совокупность программ для хранения.
Внутренние структуры хранения. Организация доступа к данным Наличие двух уровней системы для организации доступа к данным Поддержка отношений-каталогов.
АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ Лекции для студентов-заочников 2 курса, специальность (Прикладная информатика)
8. ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ 8.1. Общие сведения Форма хранения данных в ЭВМ часто существенно отличается от представления пользователя и программиста.
Поиск данных. Постановка задачи поиска данных Первый атрибут: набор данных –совокупность данных, среди которых осуществляется поиск; –Элементы набора.
Технология хранения, поиска и сортировки информации в базах данных
Лекция 21 Лекция 21 Логическая и физическая схема организации пространства в документальных БД. Примеры моделей хранения и организации доступа.
LOGO Основные методы организации БД Дисциплина: «Проектирование баз данных» Специальность: «Прикладная информатика (в экономике)» Институт информатики,
в редакторе MS Word Работа с таблицами Создание таблицы Добавление строк Добавление столбцов Изменение ширины столбцов и высоты строк Создание сложных.
Лекция 6. Геоинформационные структуры данных Харитонов А. Ю. Министерство образования и науки Украины Донецкий национальный технический университет Кафедра.
Транксрипт:

Механизмы поиска в БД Структуры индексов

Основные виды индексов Простые индексы для упорядоченных файлов Вторичные индексы для неупорядоченных файлов B-деревья (B+-деревья) Хэш-таблицы

Индексы для последовательных файлов Плотный индекс - Размер файла индекса значительно меньше - Возможность бинарного поиска - Есть вероятность загрузки индекса в память Разреженный индекс

Более сложные варианты Многоуровневый индекс Индексы для файлов с дубликатами ключей –Плотный с дублированием –Плотный –Разреженный с наименьшими значениями –Разреженный с наименьшими новыми значениями

Операции с индексами Удаление –Может быть модифицировано путем добавления мертвых записей, остающихся на месте удаленных Вставка –Может быть модифицирована путем использования блоков переполнения

Вторичные индексы Плотный вторичный индекс Двухуровневый плотный индекс Многоуровневые

В-деревья Классическое B-дерево порядка 2

Поиск в B-дереве 1.Если в считанной странице обнаруживается пара ключей ki и k(i+1) такая, что ki < K < k(i+1), то поиск продолжается на странице pi. 2.Если обнаруживается, что K > km, то поиск продолжается на странице pm. 3.Если обнаруживается, что K < k1, то поиск продолжается на странице p0.

Вставка в B-дерево Пытаемся вставить: Вставка путем расщепления страницы A

Исключение из B-дерева До удаления После удаления 25

Исключение с переливанием ключей До удаления После удаления 38

Исключение со слиянием страниц До удаления После удаления 29

B+ деревья 1). Не листовые вершины содержат только ключи и ссылки на дочерние страницы. 2). Листовые вершины содержат все множество ключей отношения, сами указатели на записи, плюс указатель на следующий по порядку лист. 3). Ключи в листовых вершинах отсортированы по возрастанию.

Эффективность B+ деревьев Возьмем значение блока равным 4096 байт (что часто встречается на практике). Пусть указатель занимает 8 байт, а ключ 4. Тогда блок вмещает максимум 340 индексов. Кол-во индексов в блоке в среднем = 255. Тогда дерево глубиной в 3 уровня может адресовать записей ( ).

Хэш-таблицы Хэш-функция вычисляет по ключу номер сегмента, где должна быть размещена запись. Особенности хэш-функций для внешней памяти: 1)В роли сегментов выступают блоки 2)Каждый сегмент содержит возможность для создания блока переполнения

Динамические хэш-таблицы Расширяемые хэш-таблицы Линейные хэш-таблицы