данных

Главное отличие индексно-прямой организации от индексно-последовательной заключается в том, что в первом случае для одних и тех же данных

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

Дополнительный уровень индекса позволяет определять адрес конкретной записи.

Во первом случае не предъявляется требований

к упорядоченности данных: записи помещаются в первое свободное пространство памяти в области данных.

Область переполнения не используется.

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

эффективно, однако она требует значительно больших затрат на память для хранения индекса по сравнению с индексно-последовательной

2. Организация индексов

данных. Методы поиска в

индексе

Роль индексов настолько важна, что часто объем памяти, занимаемый индексами, превосходит объем хранимых данных.

Индекс представляет собой таблицу (древовидную структуру), позволяющую

сократить время поиска данных.

Поиск в индексе осуществляется по значению поискового ключа, на основании которого построен индекс.

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

2.Организация индексов

данных. Методы поиска в

индексе

При этом результатом поиска

является:

1.адрес конкретной записи (при индексно-прямой организации данных);

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

3. относительный адрес записи =>

23

2.Организация индексов данных.

Методы поиска в индексе

Допустим, в i-м файле последовательно хранятся данные о студентах.

Объем памяти, занимаемый сведениями об отдельном студенте, составляет N байт.

После получения относительного адреса записи K физический адрес записи Азп

вычисляется следующим образом:

Азп = А0 + N*K,

где А0 – адрес 0-й записи;

24

2.Организация индексов данных.

Методы поиска в индексе

4. символический адрес записи.

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

данных используется несколько индексов, так

как каждый из них может потребовать перестройки. При

этом первичный индекс (индекс по

первичному ключу) выдает физический адрес конкретной записи, а все остальные

индексы – символический адрес, т.е.

значение первичного ключа, а не физический

адрес записи.

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

2.Организация индексов данных.

Методы поиска в индексе

Методы поиска в индексе:

последовательный поиск;

блочный поиск;

двоичный поиск;

поиск по двоичному дереву;

поиск по двоичному сбалансированному дереву;

хэширование

26

	2.Организация индексов данных.
	Методы поиска в индексе
Двоичное дерево:
1.	у каждого узла не	17	26
	может быть более
	двух потомков
2.	для конкретного
	узла и его
	потомков
	выполняется
	условие:
	Кл < Кр < Кп,
где Кл (Кп) –
значение ключа левого
(правого) потомка;
Кр – значение узла			27
родителя

2.Организация индексов данных.

Методы поиска в индексе

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

Наиболее эффективен поиск в случае сбалансированного дерева, в котором глубина

левой и правой ветвей отличается не более

чем на единицу.

Существуют алгоритмы, позволяющие перестроить дерево для обеспечения его сбалансированности, поэтому данный

вид поиска, по результативности сравнимый с

двоичным, используется достаточно часто, особенно в условиях динамично изменяющихся данных в БД.

28

3. Алгоритмы

хэширования

Три этапа процедуры преобразования

ключа Kлi в адрес блока Aблi:

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

записи Kлi в числовую форму ni.

Если ключ Kлi является числом, необходимость

в данном действии отпадает и допускается, что Kлi= ni. В противном случае производится

преобразование Kлi → ni различными

способами.

Самый простой - использование значения Kлi в
двоичном виде.	29

3. Алгоритмы

хэширования

Например, если ключом является

строка «Kim», то оно воспринимается как число 4942189

(4B696D – в шестнадцатеричном виде);

Код символа (англ.) "K" равен числу

49 (4B 16), код "i" – 42 (6916), код

"m" – 189 (6D16).

30