Индексирование

Пример: Поставщики

Номер	Фамилия	Скидка	Город
	Иванов		Ростов
	Петров		Таганрог
	Сидоров		Таганрог
	Федоров		Ростов
	Агафонов		Азов

При наличии индекса, имеется несколько стратегий доступа к данным из файла поставщики. Пример: найти поставщиков из города Ростов. 1я стратегия: прочитать (scan) файл поставщиков и выбрать те строки, у которых город = Ростов. 2я стратегия: чтение файла городов (scan). Для строк, у которых город = Ростов извлекаются записи из файла поставщики согласно RID указателям.

Если доля поставщиков из Ростова, по отношению к их количеству достаточно мала, то 2я стратегия будет эффективней 1й. Это связано с тем, что в силу упорядоченности записей в файле города, поиск будет прекращен с следующего за ростовом названия города, во вторых, если придется просмотреть файл городов полностью, то при этом потребуется значительно меньше операций ввода вывода. Поскольку файл городов имеет размер меньший чем файл поставщиков.

В просматриваемом примере файл городов называется индексным файлом или просто индексом по отношению к файлу поставщиков. Индексный файл это файл, который содержит данные из другого файла, который называется индексированным (в примере файл поставщики) и вид указателя фактические данные (файл поставщики). RID указатель служит для связывания записи индексного файла с записью индексируемого файла.

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

Индексы так же могут использоваться для проверки наличия некоторого значения. Например для ответа на вопрос, если поставщики из города Батайск, достаточно будет просмотреть только индексный файл. Файл может иметь несколько индексов, которые могут использоваться совместно. Кроме того индексы могут быть составными, которые эффективно могут использоваться при поиске значений в первом столбце или в первом втором, третьем.

Индексы часто называют инвертированными списками. Файл с индексами по каждому полю называется полностью инвертированным.

Плотное и неплотное индексирование

Плотный индекс имеет вход для каждой записи индексированного файла. В индексе используются RID указатели, хотя достаточно было бы только номеров страниц. Так как извлечение конкретной записи уже будет выполняться в ОП. То есть число дисковых операций ввода вывода не увеличится. Если физическая последовательность файл поставщиков соответствует логической последовательности (например по номер по номеру поставщика). Иначе говоря, в этом файле выполнена кластеризация по полю номера. Если проиндексировать файл по полю номер, то нет необходимости в таком индексе хранить указатели для каждой записи индексируемого файла. Достаточно хранить максимальный номер поставщика для каждой страницы и номер соответствующей страницы. Такой индекс называется неплотным. Преимущество использования неплотных индексов заключается в их малом размере поскольку просматриваться такие файлы будут с большой скоростью. Однако, с помощью одного такого индекса нельзя ответить на вопрос о наличии некоторого значения.

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

Структура типа B-tree

Дерево состоит из двух множеств: множество вершин и множество дуг. Корневой называется вершина не имеющая входящих в нее дуг. Дерево всегда имеет только 1 корень. Листом называется вершина, которая не имеется выходящих дуг. У листьев нет дочерних вершин, а у корня нет родителя. Каждая вершина кроме корня имеет только одну родительскую вершину. Дерево называют сбалансированным тогда и только тогда, когда каждый его лист имеет одинаковое число предков. B-tree является индексными последовательными файлами имеющими иерархические индексы. Подобные структуры используются практически во всех СУБД. Буква B означает сбалансированная, а не бинарная. В отличии от бинарных деревьев, которые юзаются в ОП и каждый узел имеет не более 2х потомков, узлы B дерева имеют множество потомков. Каждый узел сбалансированного дерева на диске фактически занимает полностью весь блок. В итоге в каждом блоке Б3 содержится сотня указателей на потомков. При поиске в B tree проверяется только 3 дисковых блока.

Необходимость создания структуры B tree заключается в желании заключается в желании в избежание просмотра всего содержимого индексного файла. Идея состоит в том, чтобы создать для индексного файла еще 1 индекс и так далее. При этом индекс на каждом из уровней будет не плотным по отношению к нижнему индексированному уровню. Такой многоуровневый индекс состоит из двух частей: набора последовательностей и набора индексов.

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

Набор индексов

Обеспечивает быстрый непосредственный доступ к наборам последовательностей (последовательным данным). Фактически набор индексов является индексным файлом со структурой B-tree. Комбинация набора индексов и набора последовательностей называется структурой типа B+tree.

Одним из недостатков иерархических структур является несбалансированность их работы после удаления или вставки некоторых элементов. В результате элементы с реальными данными могут оказаться на разных расстояниях от корневого элемента. Продолжительность поиска в несбалансированной структуре может оказаться непредсказуемой. Преимуществом структуры типа B tree является возможность сбалансированной вставки или удаление значений. Для вставки нового значения V в структуру типа B-tree порядка n. Пусть V = 41. Например, может быть использован следующий алгоритм:

1) на самом низком уровне набора индексов следует найти элемент содержащий 2m индексных записей. Нам нужно отложит элемент N содержащий 2m индексных записей. Если элемент N содержит свободное пространство, то значение вставляется в него и на этом процесс завершается.

2) в противном случае (если свободного пространства нет) элемент N разделяем на два элемента N1 и N2. Обозначим символом S множество 2m+1 значений, в котором 2m несходных значений и 42. Первые m значений этой логической последовательности и среднее между ними значение W необходимо поместить в элемент N1. А последние m в элемент N2. Значение W необходимо поместить в родительский элемент P на более высоком структурном уровне. В последствии при осуществлении поиска некоторого значения U, достижения элемента P, поиск будет перенаправлен в сторону элемента N1 (если U<=W), либо в сторону элемента N (если U> W).

Далее этот процесс следует повторить для вставки среднего значения W в родительский элемент P на более высоком структурном уровне. В худшем случае процесс разделения элемента структуры может продлиться вплоть до корневого элемента с образованием нового иерархического уровня. Для удаления элемента следует применить аналогичный алгоритм в обратном порядке.

Кэширование

Стилем и порядком дерева называется максимально допустимое количество дочерних узлов для каждого родительского узла. Большие степени обычно используются для создания более широких и менее глубоких деревьев. На практике каждый узел в дереве является страницей и потому в нем может храниться значительно больше 3х указателей и 2х ключевых значений как в рассмотренном примере. Пример: страница имеет размер 4096 байт, указатель 4 байта, размер индексируемого поля тоже 4 байта, указатель на узел того же уровня тоже 4 байта, и того: на одной странице можно хранить (4096-4)/(4+4)=511 записей. Таким образом порядок B-tree+ равен 512. То есть корень дерева должен содержать до 511 записей и иметь до 512 дочерних узлов. Каждый дочерний узел также может содержать до 511 записей и 512 для его дочерних узлов. Кэшированием, кэш адресацией или хэш - индексированием называется технология быстрого прямого доступа к записи на основе заданного значения некоторого поля. При этом: 1) каждая запись помещается по адресу (reed указатель или номер страницы), который вычисляется при помощи специальной хэш функции на основе значения некоторого поля данной записи, которая называется хэш полем иди хэш ключом. Вычисленный адрес называется хэш адресом. 2) для сохранения записи сначала вычисляется хэш адрес новой записи, а затем диспетчер файлов помещает эту запись по вычисленному адресу. 3) для извлечения записи по заданному значению хэш поля сначала вычисляется хэш адрес а затем запись извлекается по этому адресу.

Для выбора «хорошей» функции хэширования необходимо знать, во первых примерное число записей в файле и во вторых сколько записей может поместиться в блок. Эта информация нужна для вычисления количества блоков в файле и соответственно диапазона значений функции хэширования. Если для файла будет выделено слишком мало блоков, то эффективность доступа будет уменьшаться по мере их переполнения. Если наоборот, для размещения файла будет предусмотрено слишком много блоков, то доступ будет осуществляться быстро, но значительная часть памяти в этом случае останется незанятой данными. Обычно считается нормальным, когда занято данными две трети блока.

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

Непригодность файлов с хэш адресацией к групповой обработке

Прямой доступ имеет место, когда требуется найти одно значение ключа. В процессе групповой обработки требуется получить несколько значений (или говорят ответов). Назовем коэффициентов активности отношение числа ответов к числу записей в файле. Коэффициент активности близок к единице, когда требуется получить почти все записи из файла (например платежная ведомость). Прямой доступ имеет место, когда коэффициент активности близок к нулю. То есть нужно найти одну запись. При групповой обработке использовать последовательный файл бывает выгодней чем файл с хэш адресацией. Для того чтобы правильно выбрать организацию файла, необходимо хотя бы приблизительно знать коэффициент активности файла.

Цепочки указателей

Для выполнения запроса типа “найти поставщиков из города N” можно применить способ хранения данных с использованием цепочек указателей (смотри рисунок). В данном случае этот способ будет более эффективным чем индексирование. Из файла поставщиков извлекается атрибут город, который формирует родительскую структуру городов. Файл поставщиков по отношению к этому родительскому файлу называется дочерним. При выполнении запроса в такой дочерней структуре в файле городов находится нужный город, а затем по цепочке указателей извлекаются записи поставщиков из данного города. При таком способе не будет выполняться чтение записей поставщиков из других городов. Другим преимуществом данной структуры является более простое выполнение вставки и удаления записей по сравнению с индексной структурой. Кроме того эта структура занимает меньше места на диске, поскольку нет повторения названия городов.

Недостатки структуры

1) Для доступа к Nму поставщику требуется перебрать все предыдущие записи поставщиков. В худшем случае, для каждого доступа может потребоваться отдельная дисковая операция чтения.

2) Структура весьма неэффективна для обратного запроса: «найти город данного поставщика». Дело в том, что для поиска названия города приходится просматривать всю цепочку. В итоге часто совместно с цепочкой указателей приходится использовать другие структуры.

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

Меры по улучшению структуры

1) Указатели можно задать также и в обратном направлении. При этом существенно упрощается процесс согласования указателей при удалении дочерней записи.

2) В записи дочерней структуры можно добавить указатель на родительскую запись.

3) Можно не удалять атрибут город из дочерней структуры.

В данном файле можно задать как любое количество индексов так и любое количество цепочек указателей.

Управление данными расположенными в оперативной памяти

Возможность размещать базу данных целиком в оперативной памяти появилась в связи с резким снижением цен на модули памяти и широким распространением 64х разрядных операционных систем. При простом перемещении данных «дисковой» СУБД в оперативную память, ожидаемого повышения производительности не произойдет. Дело в том, что реляционная база данных функционирует исходя из предположения, что обрабатываемые данные в основном находятся на диске. Алгоритмы оптимизации, управление буферным пулом и технология извлечения данных на основе индексов – все это существенным образом ориентировано на дисковое хранение данных. Оптимизация запросов также выполняется исходя из предположения о хранении данных на диске. При работе с данными резидентно находящимися в ОП, надобность в буферном пуле отпадает.

В традиционной СУБД узел B-tree представляет собой страницу диска и содержит максимально возможное число указателей на дочерние узлы. В результате дерево имеет малую глубину и большую ширину. Такая структура позволяет уменьшить число операций ввода-вывода. Если данные находятся в ОП, то эта структура будет работать хуже бинарных деревьев, так как вычислительная мощь процессора растрачивается на сравнение значений индекса в B-tree, а так же на управление буферами, которые содержат данные и индексы.

В Times Ten используется индекс типа T-tree оптимизированный для доступа к ОП. Для навигации по дереву используется указатели <= и >, представляющие собой непосредственно ссылки на адрес памяти, а не на дисковую страницу.

В Times Ten используются технологии индексирования двух типов: Хэш-индексы и T-tree. Хэш индексы используются, когда требуется найти точные совпадения с образцом, а T-tree более подходит для поиска значений в диапазоне. Хэшированные индексы создаются автоматически, когда в данных задается первичный ключ, а T-tree создаются при помощи команды.

Дата добавления: 2015-05-10