Cтраница 1
Расширяемое хеширование объели и нет свойства метол о в хеширование использования MHOi Oii опционных cric-jitpcuh Ctt и ИЕКЛСЖИ ТСЛ ОГО яострпа, Подобно методам леширояания, оакслнным в главе 14, расширненйс хсЕинронамл прслст: ии. [1]
Расширяемое хеширование объединяет свойства методов хеширования, использования многопозиционных trie - деревьев и последовательного доступа. Для простоты в этом разделе мы будем просто считать, что ключи являются случайными строками разрядов фиксированной длины. Подобно алгоритмам с применением В-деревьев, при использовании расширяемого хеширования элементы хранятся на страницах, которые разделяются на две части при заполнении. Подобно методам индексного последовательного доступа расширяемое хеширование поддерживает каталог, указывающий, где можно найти страницу, содержащую соответствующие искомому ключу элементы. Поскольку оно объединяет эти знакомые свойства в одном алгоритме, расширяемое хеширование как нельзя более подходит для завершения знакомства с алгоритмами поиска. [2]
Измените реализацию расширяемого хеширования, приведенную в программах 16.5 - 16.7, чтобы в ней использовался двухуровневый каталог, в каждом узле которого содержится не более Л / указателей. Обратите особое внимание на действия, предпринимаемые, когда каталог впервые разрастается с одноуровневого до двухуровневого. [3]
Разработайте версию расширяемого хеширования, которая разделяет страницы при разделении каталога, чтобы каждый указатель каталога указывал на уникальную страницу. [4]
Модифицируйте реализацию расширяемого хеширования, приведенную в разделе 16.4 ( программы 16.5 - 16.8), чтобы она работала в среде, в которой таблица размещается на внешнем устройстве хранения информации. [5]
Поиск в таблице расширяемого хеширования заключается всего лишь в использовании ведущих разрядов ключа для индексирования внутри каталога и выполнении на указанной странице последовательного поиска элемента, ключ которого равен искомому. Единственное выдвигаемое при этом требование - каждая запись каталога должна ссылаться на страницу, которая гарантированно содержит все элементы таблицы символов, начинающиеся с указанных разрядов. [6]
Подобно методам индексного последовательного доступа расширяемое хеширование nojuep iii ci кагд-лог, укд. [7]
Этот обманчиво простой код лежит в основе процесса расширяемого хеширования. У нас имеется связь t с узлом, содержащим элементы, первые k разрядов которых совпадают, которую требуется вставить в каталог. Если k меньше d, необходимо установить более одного указателя - в первом цикле for вычисляется количество указателей, которые необходимо установить ( 2d k), а во втором выполняется собственно установка. [8]
Этот обманчиво лросгой год лежит а основа процесса расширяемого хеширования. V нас имеется связь t с узлом, содержащим элементы, первые с разрядов которых совладают, которую треСуетсв вставить в каталог. В простейшем случд &, когда эна - d и k рааны. & е одного указателя - а персом цикле for вычисляется количество укэзат & яей, которые необходимо установить 2tf -) r a втором дыполняется собственно установка. [9]
В частности, структура данных, используемая для расширяемого хеширования, значительно проще использованной для В-деревьев. Значение d выбирается достаточно большим, чтобы на каждой странице гарантированно хранилось менее М элементов. [10]
Лемма 16.5 При использовании страниц, которые могут содержать М элементов, для реализации расширяемого хеширования для файла, содержащего N элементов, в среднем требуется около 1.44 ( / V / M) страниц. [11]
В статье Байера ( Bayer) и Мак-Крейта ( McCreight), опубликованной в 1972 г., рассматриваются В-деревья; алгоритм расширяемого хеширования, представленный в главе 16, взят из статьи Фагина ( Fagin), Нивергельта ( Nievergelt), Пиппенгера ( Pippenger) и Стронга ( Strong), опубликованной в 1979 г. Аналитические результаты в отношении расширяемого хеширования были получены Флажолетом в 1983 г. С этими статьями обязательно следует ознакомиться всем, кто желает получить более подробную информацию по методам внешнего поиска. Практическое применение этих методов обусловлено контекстом систем баз данных. [12]
Альтернатива В-деревьям, расширяющая применение алгоритмов поразрядного поиска на внешний поиск, была разработана Фагином ( Fagin), Нивергельтом ( Nievergelt), Пиппенгером ( Pippenger) и Стронгом ( Strong) в 1978 г. Их метод, названный расширяемым хешированием, приводит к реализации операции search, для которой в типичных приложениях требуется всего одно-два зондирования. Для соответствующей реализации операции insert также ( почти всегда) требуется всего одно-два зондирования. [13]
В статье Байера ( Bayer) и Мак-Крейта ( McCreight), опубликованной в 1972 г., рассматриваются В-деревья; алгоритм расширяемого хеширования, представленный в главе 16, взят из статьи Фагина ( Fagin), Нивергельта ( Nievergelt), Пиппенгера ( Pippenger) и Стронга ( Strong), опубликованной в 1979 г. Аналитические результаты в отношении расширяемого хеширования были получены Флажолетом в 1983 г. С этими статьями обязательно следует ознакомиться всем, кто желает получить более подробную информацию по методам внешнего поиска. Практическое применение этих методов обусловлено контекстом систем баз данных. [14]
Хотя рассмотренные фундаментальные алгоритмы обладают большими возможностями, разработка реализации файловой системы, основанной на использовании В-деревьев или расширяемого хеширования представляет собой сложную задачу. Во-первых, приведенные в этом разделе программы на C нельзя использовать непосредственно - они должны быть модифицированы для считывания и ссылки на дисковые файлы. Во-вторых, необходимо быть уверенным, что параметры алгоритма ( например, размеры страницы и каталога) подобраны в соответствии с характеристиками конкретного используемого аппаратного обеспечения. В-третьих, следует уделить внимание надежности и выявлению и исправлению ошибок. Например, необходимо иметь возможность убедиться в целостности структуры данных и принять решение о том, как исправлять любые из возможных ошибок. Подобные системные факторы являются критичными и выходят за рамки этой книги. [15]