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

Реферат Курсовая Конспект

Часть 2. Индексирование

Часть 2. Индексирование - Лекция, раздел Философия, Лекция 2 Реляционная модель данных Как Отмечалось Выше, Определение Ключа Для Таблицы Означает Авто­матическую С...

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

Для реализации этих функций в СУБД применяют индексирование.

Термин «индекс» тесно связан с понятием «ключ», хотя между ними есть и некоторое отличие.

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

Таблицу, для которой используется индекс, называют индексированной.

 

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

 

В некоторых системах, например, Paradox, индексы хранятся в индексных файлах, хранимых отдельно от таб­личных файлов.

Варианты решения проблемы организации физического доступа к инфор­мации зависят в основном от следующих факторов:

• вида содержимого в поле ключа записей индексного файла;

• типа используемых ссылок (указателей) на запись основной таблицы;

• метода поиска нужных записей.

 

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

Преимущество хранения хеш-кода вместо значения состоит в том, что длина свертки независимо от длины исходного значения ключевого поля всегда имеет некоторую постоянную и достаточно малую величину (например, 4 байта), что существенно снижает время поисковых опера­ций.

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

 

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

 

На практике чаще всего используются два метода поиска: последователь­ный и бинарный (основан на делении интервала поиска пополам).

Проиллюстрируем организацию индексирования таблиц двумя схемами: одноуровневой и двухуровневой. При этом примем ряд предположений, обыч­но выполняемых в современных вычислительных системах. Пусть ОС под­держивает прямую организацию данных на магнитных дисках, основные таб­лицы и индексные файлы хранятся в отдельных файлах. Информация файлов хранится в виде совокупности блоков фиксированного размера, например целого числа кластеров.

 
 

При одноуровневой схеме в индексном файле хранятся короткие запи­си, имеющие два поля: поле содержимого старшего ключа (хеш-кода клю­ча) адресуемого блока и поле адреса (физического адреса) начала этого блока (рис. 3).

 

Рис. 3. Одноуровневая схема индексации

 

 

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

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

1. Образование свертки значения ключевого поля искомой записи.

2. Поиск в индексном файле записи о блоке, значение первого поля кото­рого больше полученной свертки (это гарантирует нахождение искомой свертки в этом блоке).

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

 

Основным недостатком одноуровневой схемы является то, что ключи (свертки) записей хранятся вместе с записями. Это приводит к увеличению времени поиска записей из-за большой длины просмотра (значения данных в записях приходится пропускать).

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

 
 

Рис. 4. Двухуровневая схема индексации

 

В этой схеме индекс основной таблицы распределен по совокупности файлов: одному файлу главного индекса и множеству файлов с блоками ключей.

Ключевые поля таблицы во многих СУБД, как правило, индексируются автоматически. На практике для создания индекса для некоторой таблицы БД пользова­тель указывает поле таблицы, которое требует индексации.

Ин­дексные файлы, создаваемые по ключевым полям таблицы, часто называют­ся файлами первичных индексов.

Индексы, создаваемые пользователем для не ключевых полей, иногда на­зывают вторичными (пользовательскими) индексами.

 

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

Связь вторичного индекса с элементами данных базы может быть уста­новлена различными способами. Один из них - использование вторичного индекса как входа для получения первичного ключа, по которому затем с использованием первичного индекса производится поиск необходимых за­писей (рис. 5).

 
 

Рис. 5. Способ использования вторичных индексов

 

Некоторыми СУБД, например Access, деление индексов на первичные и вторичные не производится. В этом случае используются автоматически со­здаваемые индексы и индексы, определяемые пользователем по любому из не ключевых полей.

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

Ин­дексирование требует небольшого дополнительного места на диске и незна­чительных затрат процессора на изменение индексов в процессе работы. Индексы в общем случае могут изменяться перед выполнением запросов к БД, после выполнения запросов к БД, по специальным командам пользова­теля или программным вызовам приложений.

– Конец работы –

Эта тема принадлежит разделу:

Лекция 2 Реляционная модель данных

Реляционная модель данных... В лекции рассматривается наиболее распространенная реляционная мо дель... Часть Определение реляционной модели При создании информационной системы...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Часть 2. Индексирование

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Часть 1. Определение реляционной модели
Реляционная модель данных (РМД) некоторой предметной области пред­ставляет собой набор отношений, изменяющихся во времени. При создании информационной системы совокупность отношений

Часть 4. Контроль целостности связей
Из перечисленных видов связи чаще используется связь вида 1:М. Связь вида 1:1 можно считать частным случаем связи 1:М, когда одной записи глав­ной таблицы соответствует одна запись вспомогательной

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги