Эдвард Сьоре - Проектирование и реализация систем управления базами данных

них.

14.4. Определение неОбхОдимОгО кОличеСтва буферОв
Многобуферные алгоритмы, представленные выше, используют k буферов, но
не определяют точного значения k. Правильное значение k определяется количеством доступных буферов, размером входных таблиц и конкретным оператором. Для сортировки k определяется как корень некоторой степени из размера входной таблицы; для прямого произведения k определяется как частное
от деления размера таблицы на количество фрагментов.
Цель состоит в том, чтобы выбрать для k наибольший корень (или частное),
который меньше количества доступных буферов. В SimpleDB методы для вычисления этих значений помещены в класс BufferNeeds, определение которого
представлено в листинге 14.1.
Листинг 14.1. Определение класса BufferNeeds в SimpleDB
public class BufferNeeds {
public static int bestRoot(int available, int size) {
int avail = available - 2; // зарезервировать пару буферов
if (avail avail) {
i++;
k = (int)Math.ceil(Math.pow(size, 1/i));
}
return k;
}

14.5. Реализация многобуферной сортировки  407
public static int bestFactor(int available, int size) {
int avail = available - 2; // зарезервировать пару буферов
if (avail avail) {
i++;
k = (int)Math.ceil(size / i);
}
return k;
}
}

Класс содержит общедоступные статические методы bestRoot и bestFactor.
Эти два метода практически идентичны. Оба принимают количество доступных буферов и размер таблицы в блоках, и оба вычисляют оптимальное количество буферов как наибольший корень или как наибольшее частное, которое меньше количества доступных буферов. Метод bestRoot инициализирует
переменную k значением MAX_VALUE, чтобы заставить цикл выполниться хотя бы
один раз (чтобы k не могло быть больше √B).
Обратите внимание, что методы в классе BufferNeeds не резервируют буферы
в диспетчере буферов – они просто получают количество доступных буферов
как параметр и выбирают значение k меньше этого числа. Когда многобуферные алгоритмы будут пытаться закрепить эти k блоков, некоторые буферы могут оказаться недоступными. В этом случае алгоритмы будут ждать, пока вновь
не станет доступно необходимое количество буферов.

14.5. реализация мнОгОбуфернОй СОртирОвки
Методы splitIntoRuns и doAMergeIteration класса SortPlan в SimpleDB определяют
количество используемых буферов. Текущая реализация splitIntoRuns создает
серии поочередно, используя один буфер, связанный с временной таблицей,
а doAMergeIteration использует три буфера (два для входных серий и один – для
выходных). В этом разделе рассматривается, как следует изменить эти методы
для реализации многобуферной сортировки.
Рассмотрим splitIntoRuns. Этот метод не знает, насколько большой получится отсортированная таблица, потому что она еще не создана. Однако он может
использовать метод blocksAccessed, чтобы получить оценку этого числа. В частности, splitIntoRuns может выполнить такой код:
int size = blocksAccessed();
int available = tx.availableBuffs();
int numbuffs = BufferNeeds.bestRoot(available, size);

Затем закрепить numbuffs буферов, заполнить их входными записями, применить к ним алгоритм внутренней сортировки и записать во временную таблицу, согласно алгоритму 14.1.
Теперь рассмотрим метод doAMergeIteration. Лучшая стратегия для метода –
изымать из списка серий сразу k временных таблиц, где k – корень из числа
начальных серий:

408



Эффективное использование буферов

int available = tx.availableBuffs();
int numbuffs = BufferNeeds.bestRoot(available, runs.size());
List runsToMerge = new ArrayList();
for (int i=0; i --">