Диплом К

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

Время чтения считается аналогично времени добавления, но вместо времени за-

писи будет фигурировать время считывания одной страницы - tс, которое подчиняется тем же закономерностям и отличается от него только величиной (почти для всех ком-

пьютеров меньше в 2-3 раза). Мы сразу запишем конечное выражение для расчета вре-

мени чтения:

Мы видим, что время чтения линейно зависит и от длины записи (точнее, числа страниц,

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

ющее: при усреднении времен чтения и добавления по достаточно большому числу за-

писей, значение среднего время чтения будет меньше среднего значения времени до-

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

4.1.3. Влияние кэширования на скорость работы файла данных.

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

ния числа операции ввода-вывода). Кэш может выделяется как в основной, так и в до-

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

происходит выталкивание некоторой страницы непосредственно в файл данных. Влия-

ние кэша на времена выполнения операций добавления, удаления и чтения легко оце-

нить.

При добавлении новые страницы не записываются в файл данных (не происходит операции ввода-вывода), а размещаются в кэше. Таким образом время добавления Tд

перестает зависеть от местоположения новой записи в файле данных, а константа tз

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

например, когда часть записи попала в кэш, а часть не влезла и попала сразу в файл.

При чтении картина сложнее – время первого чтения записи в сеансе работы оста-

нется таким же, но при повторном чтении этой же записи время чтения перестанет зави-

сеть от местоположения читаемой записи, а значение tс уменьшится на несколько по-

рядков.

На времени удаления наличие кэша сказывается аналогично операции добавления

– константа tз уменьшается на несколько порядков, а k = 0 (поскольку реального пози-

ционирования по диску не происходит).

4.1.4. Влияние сжатия на объем и скорость работы файла данных.

Единица данных для сжатия - запись. Если при создании файла данных была зада-

на необходимость сжатия информации, то все добавляемые записи будут сжиматься, а

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

вается на 70%, время чтения увеличивается на 25%. Для эксперимента формировали сжатый и не сжатый файлы с одинаковым размером страницы, помещая в них одинако-

вое множество записей.

4.2. Исследование реализации файла индексов

Исследовались характеристики компактности размещения индексной информа-

ции в виде пар ключ–значение и временные параметры основных операций с ключами.

4.2.1. Анализ компактности хранения ключей и значений в индексе.

Для хранения индексной информации в виде пар ключ–значение разработана реа-

лизация индекса в виде В+дерева, с уникальными особенностями:

значения хранятся непосредственно в индексе;

блоки нижнего уровня связаны ссылками по образу двусвязного списка;

для хранения всех блоков В+дерева используется файл данных страничной орга-

низации.

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

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

Так как основное предназначение индекса – быстрый поиск по заданному ключу,

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

ВВ+дереве, по определению, все множество ключей (а у нас и значений) хранится

вблоках данных. Кроме того в В+дереве при добавлении новых ключей возможны опе-

рации разбиения блоков, в результате чего большинство блоков заполнены не полно-

стью. Таким образом в индексе мы имеем служебную информацию трех видов:

для отдельных блоков данных - размер заголовка блока и длина незаполненной области;

для индекса в целом - суммарная длина всех управляющих блоков;

служебная информация файла данных, хранящего блоки индекса.

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

матическая модель очень сильно усложняется.

Введем обозначения для исходных величин: pд - длина заголовка блока данных, pу

- длина заголовка управляющего блока, Lк - длина ключа (средняя, если ключ перемен-

ного размера) вместе с длиной префикса при нем, Lз - длина значения при ключе, Lб -

длина блока индекса (длины блоков данных и управления одинаковы), N - число ключей в индексе.

Выведем формулы для расчета объема служебной информации в блоках данных индекса. Сразу можем записать максимальное число пар ключ–значение на одном блоке данных:

тогда суммарное число блоков данных:

ных индекса.

Теперь приступим к расчету суммарной длины управляющих блоков индекса. По принципу построения В+дерева число элементов на i-ом уровне равно числу блоков на

(i-1)-ом уровне. Число блоков данных - kд мы можем рассчитать по формулам (17) и

(20), это и будет число пар ключ–значение на первом уровне В+дерева. Тогда мини-

мальное и максимальное число блоков на 1-м уровне индекса:

и для i-го уровня получаем рекуррентные соотношения:

Как только мы получим при каком-то i значение ki равное 1, мы можем сказать, что В+дерево при заданных параметрах и числе ключей будет иметь высоту i. Суммарная длина всех управляющих блоков:

r

S2 ki L 6 , (30)

i 1

где r - число уровней В+дерева.

Зададимся числом пар ключ–значение, хранящихся в индексе - 100000; пусть ин-

декс хранит слова русского языка, тогда Lк= 13 байт, Lз= 4 байта, длина ссылки в теку-

щей реализации Lс= 3 байта. Проведем конкретные расчеты - сначала рассчитаем мини-

мальный размер управляющих блоков:

В максимальном варианте индекс будет иметь высоту в 4 уровня. (39)

Накладные расходы файла данных, хранящего блоки индекса мы уже знаем - это нижняя граница для длины служебной информации в файле данных. По формуле (8) она равна 2.3%. Мы берем нижнюю границу, так как подобрали длину блоков индекса так,

чтобы минимизировать длину служебной информации для файла данных в соответ-

ствии с формулой (5).

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

Подставим в формулы (40) и (41) ранее полученные значения:

Подведем итог: выбранные структуры хранения пар ключ:значение в разработан-

ной реализации индексов обеспечивают долю служебной информации от 2.9% до

52.9%.

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

что доля служебной информации с ростом объема индекса стабилизируется на значении

30%. Это вполне приемлимый результат. Результаты эксперимента графически пред-

ставлены на рисунках 28, 29.

4.2.2. Анализ времени поиска ключа в индексе.

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

Напомним, как происходит поиск ключа в В+дереве. Поиск ведется сверху вниз,

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

Оценим число сравнений искомого ключа с ключами индекса для случая неуни-

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

ного числа сравнений при поиске ключа в индексе.

Введем обозначим для исходных величин: r - число уровней в индексе, n - число ключей на блоках данных индекса, k - число ключей на управляющих блоках индекса.