Я изучаю базы данных из книги Основы систем баз данных , от авторов Elmasri и Navathe, 5-е издание, и они кратко объясняют внешнюю сортировку с помощью сортировки слиянием почти в начале главы 15. Они разделяюталгоритм в два этапа:
1) Сортировка : они используют следующие обозначения:
- b = Количество блоков файла данных, которые мы хотим отсортировать.
- nb = Количество буферов (блоков) в памяти, доступных для сортировки.
- nr = Количество порций.
На этом этапе мы помещаем вПамять как можно больше блоков файла данных, мы сортируем их, используя любой внутренний алгоритм сортировки, и записываем их как временный отсортированный подфайл.Мы повторяем это с остальными блоками файла, чтобы получить больше отсортированных подфайлов.Это те подфайлы, которые они называют «порциями», и их число:
nr = ⌈ b / nb *.
Символы ⌉ ⌉ обозначают функцию потолка.Стоимость ввода / вывода на этом этапе составляет 2b , потому что нам нужно прочитать каждый блок один раз (доступ b).Затем, чтобы сохранить все части, мы также должны сделать b доступ.
2) Слияние : Они говорят что-то похожее на это (я переписал это, используя мою интерпретацию, чтобы сделать это более понятным):
Полученные части (упорядоченные подфайлы) смешиваются за один или несколько проходов .Для каждого прохода выходной блок резервируется в памяти для размещения результата смесей, а остальные используются в качестве входных блоков, которые могут быть до nb-1, и в которых один блок размещается одновременно для каждого изупорядоченные порции, с целью их смешивания.Если входных блоков меньше, чем порций, требуется более одного прохода.Кроме того, поскольку каждая часть может иметь более одного блока, каждый проход подразделяется на итераций , в каждой из которых размещается блок каждой части.
- дм = градуссмешивания, то есть количество порций, которые можно смешивать за каждый проход.
Число dm должно быть равно минимуму между (nb - 1) и nr.Если мы поместим основание логарифма между () и его аргумент между 〖〗, число проходов будет:
⌈ log (дм) 〖nr〗 ⌉.
Часть, с которой меня связывают , состоит в том, что они говорят, что стоимость этого этапа составляет
2b * ⌈ log (дм) 〖nr〗 ⌉,
, поэтому они в основном подразумевают, чтоза каждый проход нам нужно прочитать каждый блок только один раз и записать его один раз, но я не уверен, что это правильно.Я подозреваю, что может потребоваться больше обращений.
Таким образом, общая стоимость алгоритма составляет 2b + 2b * ⌈log (dm) 〖nr〗 ⌉
= 2b (1 + ⌈log(dm) 〖nr〗 ⌉)
На самом деле, они так не говорят, но: "В общем случае логарифм берется в базе dm, а выражение указывает число блоков.Доступ осуществляется следующим образом: "
(2 * b) + (2 * (b * (log (dm) 〖nr〗))),
, что в основном то же самое.
Например, предположим, что у нас есть файл из 10 блоков с 3 записями на блок.Доступное пространство в памяти (буферный пул) имеет размер 4 блока.Разделим блоки файла с помощью ||
29,11,27 ||22,1,20 ||7,30,26 ||9,8,21 ||13,24,15 ||23,4,28 ||17,12,10 ||5,3,6 ||16,19,2 ||25,14,18
Количество порций 'nr', которые приводят к фазе сортировки, составляет ⌈10 / 4⌉ = 3.
p1 = 1,7,8 ||9,11,20 ||21,22,26 ||27,29,30
p2 = 3,4,5 ||6,10,12 ||13,15,17 ||23,24,28
p3 = 2,14,16 ||18,19,25
В фазе мегаммирования dm = минимум {nb-1, nr} = минимум {4-1,3} = 3. Тогда число проходов равно log (3) 〖3〗 = 1. Согласно формуле, мы должны сделать 20 операций ввода / вывода на этом этапе.
Итерация 1: Мы поместим эти блоки в память:
1, 7,8 ||3,4,5 ||2,14,16
и они превращаются в это (по одному блоку за раз, который сохраняется на диске):
1,2,3 ||4,5,7 ||8,14,16
6 доступ к диску.
Итерация 2:
9,11,20 ||6,10,12 ||18,19,25
и они превращаются в это:
6,9,10 ||11,12,18 ||19,20,25
6 доступ к диску (уже накоплено 12).
Что я делаю не так, и как мне продолжить?