Тема 6 методы ускорения доступа к данным - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Приводятся результаты численного эксперимента доступа к данным. 1 192.09kb.
Исследование операций. Тема Модели и критерии эффективности. 1 65.03kb.
Одномерное моделирование коллективного ускорения ионов(протонов) 1 75.06kb.
2. Кинематика точки 1 53.45kb.
Специализированные методы визуализации 2d и 3d изображениq в бортовых... 1 88.09kb.
Ооп основано на понятиях класса и экземпляра 1 171.08kb.
Физика часть 15 1 26.69kb.
Словарь Терминов по Безопасности и Криптографии 1 337.62kb.
Космофизические базы данных в ниияф мгу 1 62.09kb.
Контрольные задания 1 2 Вариант 29 1 46.41kb.
Способы, методы, приёмы, технологии подготовки к егэ. Способы и приёмы... 3 422.68kb.
Хэш-таблицы (hash tables) одно из величайших изобретений информатики. 1 70.45kb.
Направления изучения представлений о справедливости 1 202.17kb.

Тема 6 методы ускорения доступа к данным - страница №1/1




Тема 6 МЕТОДЫ УСКОРЕНИЯ ДОСТУПА К ДАННЫМ

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

Эти же методы необходимы при организации доступа к ин­формации по нескольким ключевым атрибутам одновременно.

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


6.1Адресная функция


Расстановка записей происходит в соответствии с так на­зываемой адресной функцией (другие общеупотребительные ее названия - "рандомизирующая функция" или"хэш-функция" от hashing – рассеянная память от глагола to hash – крошить рубить и делать из этого месиво ).

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

Рассмотрим знаменитый пример «парадокс дня рождения». Который обсуждался математиками в 30-е годы. Например, в компании из 23 человек более всего вероятно совпадение дней рождения у двух человек, чем то что у всех дни рождения окажутся различеиные. Иными словами, если выбрать случайную функции, отображающую 23 ключа в таблицу размером 365, вероятность, что никакие два ключа не будут отображены в одно и тоже место таблицы , составляет 0,4927, т.е. менее половины. Этот пример предупреждает нас, что вероятно найдутся различныеключи Pi  Pj при которых F(pi)=F(pj). Такое событие именуется коллизией. Для разрешения коллизий разработаны некоторые подходы.

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



Адресной функцией или хеш функцией называется зависимость

i= f(p),


где i— номер (адрес) записи;

р - значение ключевого атрибута в записи.

К функции f предъявляются следующие требования:

• она должна быть задана аналитически и вычисляться до­статочно быстро;

•ключевые атрибуты, подчиняющиеся произвольному рас­пределению, функция должна переработать в равномер­но распределенные номера записей; это условие обычно соблюдается приближенно;

• число записей-синонимов или коллизий должно составлять 10-20% от общего числа записей.


6.1.1Построение хеш-функции.


Предположим, что хеш-функция имеет не более М различных значений, причем для всех ключей Р

0 <=F(p) < М. (1)

Известно достаточно много адресных функций, хорошо соответствующих этим требованиям. Простейшая адресная функция имеет вид:



i=р-а, где а - константа.

Пусть известны минимальное значение ключевого атрибута в массиве р' и максимальное значение р " . Тогда а = р' - 1. Необходимый участок памяти для данных оценивается в р" - р' +1 запись. Записи-синонимы связываются в цепочки с помощью адресов связи, они занимают дополнительную (ре­зервную) память.

Пример размещения записей с ключами 13,11,14,11,15,18, 14,16 согласно адресной функции i = р - а показан на рис. 6.1

11




13

14

15

16




18
























11







14




































Рис. 6.1. Организация записей в соответствии с адресной функцией i = р - а

При доступе к записи с ключом q вычисляется i= f(q) и про­изводится обращение к i-й записи. При необходимости с по­мощью адресов связи извлекаются все синонимы.

Недостаток адресной функции вида i = р - а - большой объем неиспользуемой памяти, если р "- р 'много больше, чем количество записей М.

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

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

Рассмотрим, например, десятизначные ключи на десятичном компьютере. Положить, М = 1000 в качестве f(p) используем три цифры, выбранные около средины двадцати-значного произведения Р х Р. Этот метод должен давать довольно равномерное распределение значений между 000 и 999 с низкой вероятностью коллизий; однако эксперименты с реальными данными показывают, что такой метод “середины квадратов" неплох при условии, что ключи не имеют большого количества нулей слева или справа.

Многочисленные тесты показали хорошую работу двух основных типов хеш функций, один из которых основан на делении, а другой — на умножении.

Метод деления весьма прост; мы просто используем остаток от деления на М

i= ОСТ (р/m). (2)

Здесь m - целое число; ОСТ - остаток от деления р на m.

Вычисление i производится с помощью специального оператора, например i = p mod m . (язык Паскаль)

Значение m принимается равным простому числу, которое непосредственно больше либо непосредственно меньше числа записей М.

В этом случае очевидно, что, при четном М значение F{p) будет чет­ным при четном p и нечетным — при нечетном, что приведет к значительному смещению данных во многих файлах. Еще хуже обстоят дела, если М представля­ет собой степень основания счисления компьютера, поскольку при этом p mod М представляет собой несколько цифр числа p, расположенных справа, и не зависит от остальных цифр. Точно так же можно показать, что М не должно быть кратно трем поскольку при буквенных ключах два из них, отличающиеся только перестановкой букв, могут давать числовые значения с разностью, кратной 3 (это происходит, поскольку 22n mod 3 = 1 и 10n mod 3 =1). В целом, следует избегать значений М, делящих rk ± а, где k и а — небольшие числа, а г — "основание системы счисления" набора используемых алфавитно-цифровых символов (обычно r = 64, 256 или 100), так как остаток от деления по модулю на такие значения М зачастую представляет простую суперпозицию цифр ключа. Приведенные рассуждения при­водят к мысли, что лучше всего использовать в качестве М простое число, такое, что rk  ±а (по модулю М) при небольших k и а. В большинстве случаев подобный выбор вполне удовлетворителен.

Рассмотрим работу данной функции на примере. Как уже говорилось, значение m принимается равным простому числу.

Выделяются 2 зоны памяти - основная и резервная. Основ­ная зона содержит m записей. Резервная зона предназначена для размещения записей синонимов.

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

Например, для массива ключей со значениями 17, 9, 4, 14, 25, 21, 20, 11 необходимо выбрать m=7, поскольку М=8 (возможно также m=19). Содержимое основной и резервной зон иллюстриру­ет рисунок 3.10. Резервная зона заполняется последовательно. При по­иске значения, например р=11, вычисляется i = ОСТ(11/7)=4, и да­лее последовательно сравниваются 4 и 11, 25 и 11 и т.д. В рассмат­риваемом примере число записей-синонимов составляет 3/8.



Мультипликативная схема хеширования также просто реализуется, однако сло­жнее описывается, поскольку мы работаем с дробями, а не с целыми числами. Пусть w размер машинного слова1. Целое число А можно рассматривать как дробь A/w, если представить, что разделяющая точка (точка, разделяющая целую и дробную части числа в различных системах счисления, например десятичная точка) расположена слева от числа. Метод состоит в выборе некоторой целой константы А, взаимно простой с w, после чего можно положить

F(p) = [M((A/p)mod 1) ] . (3)

В этом случае обычно на двоичном компьютере в качестве М используется степень двойки, так что F(p) состоит из старших битов правой половины произведения A*Р

Вычисленное значение F(p) помещается в регистр А. На многих компьютерах умножение выполняется значи­тельно быстрее деления.

По сути, предложенный метод представляет собой обобщение метода (2), по­скольку можно, например, в качестве А использовать приближение w/M; умно­жение на обратную величину зачастую происходит быстрее деления. Технология (3) практически совпадает с методом середины квадрата, но с одним важным отличием: в дальнейшем мы увидим, что умножение на подходящую константу имеет много полезных свойств.

Одна из привлекательных черт мультипликативной схемы заключается в от­сутствии потери информации в (3); мы в состоянии восстановить значение p по содержимому регистра по окончании работы (3). Дело в том, что А и w взаимно просты и при помощи алгоритма Евклида можно найти константу А', такую, что АА' mod w = 1; отсюда следует, что p = (A'(A.pmod w)) mod w. Другими словами, если обозначить через F(p) содержимое регистра Х непосредственно перед выполнением командой сдвига , то для

Р1Р2 повлечет h(Р1)  h(Р2) (4)

Конечно, h(p) принимает значения в диапазоне от 0 до w-1, поэтому ее нельзя счи­тать сколь-нибудь хорошей хеш-функцией. Однако она может быть весьма полезной в качестве рассеивающей функции (scrambling function), т. е. функции, удовлетворя­ющей (4) и обычно рандомизирующей ключи. Такая функция может эффективно использоваться и в связи с алгоритмами поиска по дереву (если порядок ключей не имеет значения), поскольку она предотвращает возможность построения вырожденного дерева в случае поступления ключей в порядке возра­стания. Рассеивающая функция может быть применена и для цифрового поиска по дереву

Другое аспект мультипликативного хеш-метода в том, что он хорошо работает с неслучайными файлами. Например, часто множества ключей представляют собой арифметические прогрессии, когда в файле содержатся ключи {Р, Р+d, Р+2d,..., Р+td}. Например, рассмотрим имена типа {PART1, PART2, PART3} или {TYPEA, TYPEB, TYPEC}. Мультипликативный хеш-метод преоб­разует арифметическую прогрессию в приближенно арифметическую прогрессию

f(K), f(K + d), f(K + 2d), ... различных хеш-значений, уменьшая число коллизий. По сравнению со случайной ситуацией. Метод деления обладает тем же свойством.

На рис. 37 проиллюстрировано мультипликативное хеширование в частном случае. Предположим, что A/w приближенно равно золотому сечению  -1 = (5- l)/2 0.6180339887; при этом последовательность значений



f(P), f(P + 1), f(P +2), ... ведет себя точно так же, как последовательность хеш-значений f(0), f(l), f(2), ..., так что естественным становится следующий эксперимент: на отрезке [0..1] последовательно отмечаем точки {-1},{2-2}, {3-3}, .... где {х} означает дробную часть числа х (т.е.х - х или ж mod 1) Как показано на рис.37, эти точки достаточно хорошо отделены одна от другой каждая вновь добавляемая точка попадает в один из наибольших оставшихся интервалов и делит его в соответствии с золотым сечением!

Это замечательное свойство золотого сечения в действительности является част ным случаем более общей теоремы, предложенной Хьюго Штейнгаузом (Hugo Stein haus) и впервые доказанной Верой Туран Шош (Vera Turan Sos)



Теорема S. Пусть — произвольное иррациональное число. При размещена точек { }, {2 }, ..., {п } на отрезке [0..1] длины n + 1 образовавшихся отрезков имеют не более трех различных значений. Кроме того, очередная точка {(п+1)  } попадет в один из наибольших уже полученных отрезков.

Таким образом, точки { }, {2 }, ..., {п } расположены между 0 и 1 достаточно равномерно. Если - рациональное число, то теорема остается верна (при подходящей интерпретации отрезков нулевой длины, которые образуются при n, большем или равном знаменателю ). Доказательство теоремы S2

Рассмотренная теория подводит нас к хешированию Фибоначчи, при котором в качестве А берется ближайшее к -1w целое число, взаимно простое с w. Например, если компьютер десятичный можно воспользоваться множеством

(7)

Он хорошо рассеивает алфавитные ключи типа LIST1, LIST2, LIST3. Но при изменения ключей в четвертой позиции - например, SUMl_ , SUM2_ ,SUM3_ - получим, что рассеяние происходит так же, как если бы теорема S использовалась с = {100А/w} =.80339887 вместо =.6180339887 = A/w. В результате данное рассеяние оказывается несколько хуже, чем при=-1, хотя и остается достаточно хорошим. Однако в случае изменения во второй позиции ключа –Al___ A2___, A3___ - эффективное значение равно 0.9887, что, пожалуй, слишкс близко к 1.

Поэтому можно было бы работать с множителем

вместо множителя (7); такой множитель будет хорошо разделять последовательности ключей, отличающиеся в любой позиции. К сожалению, подобный выбор приводит к новой проблеме, аналогичной возникающей при делении на rk±1.•. ключи типа XY и YX попадут при хешировании в одно и то же место! Для обхода возникающией ситуации воспользуемся теоремыой S. Для коротких последовательностей ключей важны лишь несколько первых частичных отношений представлений виде цепной дроби. Маленькие частичные отношения соответствуют "хорошим” свойствам распределения. Поэтому можно показать, что наилучшие значения лежат в интервалах



Значение А можно составить так, что каждый из его байтов будет находиться в "хорошем" интервале и будет не слишком близок к значениям других байтов (или их дополнениям), например

Такой множитель может быть смело рекомендован к использованию. (Изложенн в этом разделе идеи по мультипликативному хешированию в основном принадлемжат - В. Флойду (R. W. Floyd).)

Хорошая хеш-функция должна удовлетворять двум требованиям.



  1. Ее вычисление должно выполняться очень быстро.

  2. Она должна минимизировать количество коллизий.

Свойство (а) зависит от особенностей компьютера, а свойство (b) — от особенностей данных. Если бы все ключи были действительно случайными, можно было бы использовать несколько битов из них и с их помощью получить хеш-функцю; однако на практике для удовлетворения (b) требуется функция, зависящая от всех битов ключа.

6.1.2Ключи состоящие из нескольких слов, ключи переменной длины


С ключами из нескольких слов, и с ключами переменной длины можно работать как

  • с числами с многократной точностью и применять к ним все рассмотренные методы.

  • комбинируя слова в одно и выполненяя единственную операцию умножения или деления, как описано выше. Эта комбинация мож быть осуществлена путем сложения по модулю w или выполнения операции "исключающее или" бинарного компьютера.

Обе операции используют все биты обоих аргументов; но "исключающее или", предпочтительнее, поскольку позволяет избежать арифметического переполнения. Основной недостаток такого метода заключается в том, что указанные операции коммутативны, а значит, хеш-адреса (X, Y} и (Y, X) будут совпадать. Чтобы устранить этот недостаток, Г. Д. Кнотт (G. D. Knotty предложил выполнять перед арифметической операцией циклический сдвиг.

Еще лучший путь хеширования состоящих из L символов (или L слов) ключей P = х1 х2... xi заключается в вычислении



f(p) = (f11) + f22) + • • • + fi(xi)) mod M, (9)

где каждое fj представляет собой независимую хеш-функцию. Эта идея, предложенная Дж. Л. Картером (J. L. Carter) и M. Н. Вегманом (M. N. Wegman) в 1977 году, в особенности эффективна, когда каждый хj, представляет собой отдельный символ, поскольку в таком случае можно использовать предвычисленный массив для каждой функции fj. Такие массивы делают умножение ненужным. И если М представляет собой степень двойки, то в (9) можно избежать деления, используя "исключающее или" вместо сложения. Таким образом, (9), определенно, удовлетворяет свойству (а). Более того, Картер и Вегман доказали, что если fj выбирается случайным образом, то будет выполняться и свойство (b) независимо от входных данных

Было предложено и множество других методов хеширования, однако ни для одного из них не было доказано его преимущество перед простыми методами, описанными выше

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

Очень часто удобно использовать постоянную хеш-функцию h{K) = 0 в процессе отладки программы, так как все ключи будут храниться вместе; эффективная хеш-функция h(K) может быть подставлена позже.

6.1.3Разрешение коллизий методом "цепочек".


Мы уже говорили, что некоторые хеш-адреса могут быть одинаковыми для различных ключей. Вероятно, самый очевидный путь решения этой проблемы — поддержка М связных списков, по одному для каждого возможного значения хеш-кода. Поле LINK должно быть включено в каждую запись; кроме того, следует иметь М головных узлов списков, перенумерованных, скажем, от 1 до М. После хеширования ключа мы просто выполняем последовательный поиск в списке номер f(p) + 1

На рис. 38 показана простая схема с цепочками при М = 9 для последовательности из ключей



К = EN, TO, TRE, FIRE, FEM, SEKS, SYV (11)

(представляющих числа от 1 до 7 на норвежском языке), имеющих хеш-коды

f(p)+1=3, 1. 4, 1, 5, 9, 2 (12)

соответственно. В первом списке содержится два элемента, три списка пусты.

В связи с тем, что цепочки коротки, рассматриваемый здесь метод являет весьма быстродействующим. Если 365 человек соберутся вместе в одной комнате, вероятно, окажется много пар, имеющих один и тот же день рождения, однако среднее количество людей с данным днем рождения равно только 1! В общ случае, если имеется N ключей и М списков, средний размер списка будет равN/M; значит, хеширование приводит к уменьшению среднего количества обращений по сравнению с последовательным поиском, примерно в М раз

6.2Индексы


Для ускорения поиска записей в массиве используется дополнительная информация, организованная в виде массива индексов.

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

Имеются три важные разновидности индексов:



  • информация о каждой записи основного массива попадает в индекс (сплошная индексация);

  • номера записей, информация о которых выносится в индекс, образуют арифметическую прогрессию с шагом d > 1. Основной массив, дополненный таким индексом, обычно называется индексно-последовательным;

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

Сплошной индекс связан с созданием инвертированного массива ключевых атрибутов к основному массиву. Этот случай рассмотрен в теме ИПС, инвертированные файлы.

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

В индекс выносится информация о записях, номера которых образуют арифметическую прогрессию с шагом d. На рис. 6.5 показаны ключевые атрибуты основного массива и состояние массива индексов для d=3
Рис. 6.5. Индексно-последовательная организация данных

Поиск значения q в индексно-последовательном массиве происходит в две стадии:



  • в массиве индексов (который отсортирован в силу упо­рядоченности основного массива);

  • среди записей основного массива, расположенных между двумя соседними индексами, найденными на первой стадии.

Применение индексов приводит к ускорению доступа, если основной массив располагается на внешнем запоминающем устройстве, а массив индекса может быть полностью разме­щен в оперативной памяти ЭВМ.

Если ключи записей, информация о которых выносится в индекс, приближенно образуют арифметическую прогрессию, мы получаем ситуацию с адресной функцией для индекса (ран­домизация индекса).

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

p (1)+z (n-1),

где z - константа (шаг арифметической прогрессии);

р (1) - значение ключа первой записи основного массива.

На рис. 6.4 показаны ключевые атрибуты основного массива (идентичные с предыдущим примером) и состояние мас­сива рандомизированных индексов для z = 10. Примечательно, что значения ключей в таком индексе хранить не нужно.

Рассмотрим поиск с использованием рандомизированных ин­дексов. На первой стадии номер требуемого далее индекса опреде­ляется по формуле





Результат деления округляется в меньшую сторону. Интервал записей основного массива на второй стадии поиска определяется адресами, указанными в n-м и (n+1)-м индексах.
Рис. 6.4. Рандомизация индекса

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

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



Пример

Рассмотрим записи с четырьмя атрибутами в порядке старшин­ства слева направо А 1, А2, АЗ, А4. Значения А1 упорядочены (для примера) по возрастанию. На каждом множестве записей, кото­рые соответствуют одинаковому значению А1, реализована упо­рядоченность по возрастанию значений А2 для записей, у кото­рых значение А1 одинаково. Далее, на каждом множестве записей с одинаковыми парами значений атрибутов А1 и А2 соблюдается

упорядоченность значений по атрибуту АЗ. И, наконец, на каж­дом множестве записей с одинаковыми значениями атрибутов А1, А2, АЗ должна соблюдаться упорядоченность по возрастанию для атрибута А4.

Последовательный массив с такой упорядоченностью может обеспечивать быстрый доступ к данным по следующим сочетани­ям ключевых атрибутов а1+а2+а3+а4, а1+а2+а3, а1+а2 и а1.

Количество сочетаний атрибутов, необходимых для реализа­ции максимально широкого круга запросов, в нашем примере со­ставляет 15. Хранение нескольких по-разному рассортированных дублей массива или систематическая сортировка единственного массива в соответствии с поступающими запросами не является хорошим решением проблемы.

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

а2+а3+а4.

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

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

Пример

В табл. 3.2 показаны 14 записей с ключевыми атрибутами Фа­милия и Профессия (остальные атрибуты в данном случае несуще­ственны). На пересечении строки с некоторой фамилией и столбца с некоторой профессией указан номер записи, которая содержит именно эти значения в качестве ключей.

В простейшем случае мультисписок будет содержать два спис­ка - с указателем Фамилия - (А(1), А(2), А(3), ... , А(13), А(14)) и суказателем Профессия- (А(3), А(6), А(12), А(1), А(7), А(10), А(13), А(2), А(4), А(8), А(14), А(5), А(9), А(11)).

Таблица 3.2. Мультисписок для двух клю-опы» ато-в-"—



Фамилия




Профессия




слесарь

токарь

штамповщик

электрик

Бардин Басов Батов

А(3)


А(6)

А(1)
А(7)

А(2)

А(4)

А(5)


Белов







А(8)

А(9)


Иванов Исаев

А(12)


А(10)

А(13)

А(14)


А(11)

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

Эффективная организация мультисписка предполагает выполнение следующих условий:

• число записей в каждом списке должно быть небольшим,

• адреса хранения записей должны монотонно возрастать. Для сокращения длины списков в мультисписке необходи­мо детализировать содержимое указателей. Например, указа-гель Фамилия = "Ба" определяет список (А(1), А(2), А(3), А(4), А(5), А(6), А(7)), указатель Фамилия = "Бе" - список (А(8), А(9)), указатель Фамилия = "И" - список (А(10), А(11), А(12), А(13), А(14)). Поскольку атрибут Профессия содержит четыре значения, возможно существование следующих четырех

списков: (А(3),А(6),А(12)); (А(1),А(7),А(10),А(13)); (А(2),А(4),А(8),А(14)); (А(5),А(9),А(11)).

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

Рассмотрим запрос с условием

Фамилия ="Иванов" и Профессия = "электрик"

Потребуются три обращения к памяти для выбора списка (А(10), А,(11), А(12)),А(13), А(14)) и четыре обращения для выбора списка (А(5),А(9), А(11)). В указателях хранится длина каждого списка. Вторая строка короче, поэтому она просматривается полностью до извлечения нужной записи А(11).



1 Д.Кнут принимает под размером машинного слова не количество содержащихся в нем бит, а максимальное количество представляемых им значений. Так размер 32 битного слова по Кнуту составляет 232 = 4294967296

2 Дональд Э.Кнут Искусство программмирования





Когда народ гол, на него надевают смирительную рубашку. Станислав Ежи Лец
ещё >>