Geum.ru

1. 2 Системы управления базами данных. Основные функции

Вид материалаДокументы
4.1 Хешированные индексы
Подобный материал:
1   2   3   4   5   6   7   8   9   10

4.1 Хешированные индексы


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

В качестве примера такого разбиения можно привести группировку сотрудников по первой букве фамилии. К первой группе будут относится сотрудники, с фамилией, начинающейса с буквы ``А'', ко второй - с фамилией, начинающейся с буквы ``Б'' и т.д. Каждую группу можно представить списком слов, которые начинаются с соотвествующей буквы. Все группы могут быть организованы в массив, содержащий 33 элемента, так, что по номеру группы в этом массиве можно определить указатель на начало соотвествующего списка. Если задана некоторая фамилия, то зная порядковый номер ее первой буквы в алфавите можно быстро определить группу фамилий. Затем последовательно просматривая эту группу найти нужную запись.

Однако такое простое правило определения группы обладает существенным недостатком. В русском языке фамилии распределены по буквам алфавита весьма неравномерно. Поэтому группы при таком распределении будут сильно отличаться по количеству фамилий (например, группа, начинающаяся на букву ``А'', будет содержать, скорее всего больше фамилий, чем группа, начинающаяся на букву ``Э'', тогда как группа для буквы ``Ы'' вероятнее всего будет пустой). Следовательно возникает крайне не желательная ситуация, когда поиск наиболее часто встречающихся фамилий будет требовать больше времени, чем поиск редких. Таким образом необходимо правило распределения, которое более равномерно распределяло бы фамилии по группам.

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

Существуют различные способы вычисления хеш-функций. В качестве примера можно привести стратегию, которая оказывается подходящей во многих случаях14:
  1. Значение ключа рассматривается как последовательность битов. Если ключ состоит из нескольких полей, то все они могут быть объеденены в одну последовательность битов.
  2. Последовательность битов делиться на группы, равные (или кратные) машинному слову.
  3. Группы битов складываются как целые числа.
  4. Полученная сумма делиться на количество групп ключей и остаток от деления используется как номер группы ключей.

Возможная организация хешированного индекса показана на рис. 9. Файл хешированного индекса состоит из двух частей: каталога групп, и области записей. Каталог групп представляет собой массив указателей на списки групп, изанимает требуемое количество последовательных виртуальных блоков файла в начале. Каждый список групп представляет собой список виртуальных блоков, которые отведены под записи группы. В каталоге групп хранится указатель на первый блок группы и каждый блок содержит указатель на следующий блок. Каждый блок содержит несколько записей фиксированной длины с полями под значение ключа, указатель на запись основного файла и флаг использования. Флаг использования говорит о том, содержит ли запись актальные значения или является свободным пространством15.Каталог групп имеет относительно небольшой размер и потому во многих случаях может храниться в ОП.

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

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

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

Удаление записи индекса состоит в следующем:
  1. Осуществляется поиск записи с данным ключем. Если поиск неудачен, то это считается ошибкой.
  2. Найденная запись помечается как свободное пространство (сбрасывается флаг использования).

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

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

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