Индексация данных

Сентябрь 3, 2022

Главная
Алгебра
Индексация данных

Содержание

2. Введение Цель применения индексации состоит в быстром поиске местоположения в большой структуре хранения, как при поиске
3. Принцип работы Для того чтобы найти определенный блок информации, сначала необходимо отыскать в индексе его ключ,
4. Любой бинарный алгоритм поиска в упорядоченном файле БД можно представить с помощью соответствующего бинарного дерева .Это
5. Неплотный индекс Пусть основной файл F упорядочен по полю ключа К. Построим дополнительный файл FD по
6. Плотный индекс .Он строится почти так же, как и неплотный индекс. Различие заключается в том, что
7. Поиск вначале выполняется в индексе для нахождения адреса блока основного файла, а за тем этот блок
8. Полученная структура называется В-деревом порядка т, где т – количество записей в блоке индекса. Такое дерево
9. Иногда удобно сконструировать индекс так, чтобы он указывал приблизительное, а не точное местоположение нужной информации. Например,
11. Скачать презентацию

Слайд 2

Введение
Цель применения индексации состоит в быстром поиске местоположения в большой структуре

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

Слайд 3

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

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

Слайд 4

Любой бинарный алгоритм поиска в упорядоченном файле БД можно представить с

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

Слайд 5

Неплотный индекс Пусть основной файл F упорядочен по полю ключа К.

Построим дополнительный файл FD по правилу 1) записи файла FD имеют формат FD(K, Р), где К – поле, принимающее значение ключа первой записи блока основного файла F; Р – указатель на этот блок; 2) записи файла FD упорядочены по полю К.

Полученный файл FD называется неплотным индексом. Количество записей файла FD равно количеству блоков основного файла F. Для организации файла FD требуется дополнительная внешняя память.

Слайд 6

Плотный индекс .Он строится почти так же, как и неплотный индекс.

Различие заключается в том, что для каждого значения ключа К в файле FD имеется отдельная запись, а в неполном индексе - только для значения ключа первой записи блока. Над плотным индексом можно также построить В-дерево.

Слайд 7

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

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

Слайд 8

Полученная структура называется В-деревом порядка т, где т – количество записей

в блоке индекса. Такое дерево должно иметь в каждом узле не менее т / 2 зависимых узлов и все листья должны располагаться на одном уровне. Для осуществления последовательного поиска блоки первого уровня могут быть связаны в цепь по возрастанию значения ключа.

Слайд 9

Иногда удобно сконструировать индекс так, чтобы он указывал приблизительное, а не

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