IIUJ Metody Programowania strona: 1
Wykład 14.
Sortowanie zewnętrzne
(sortowanie plików)
Sortowanie zewnętrzne, sortowanie plików (ang. external sort)  to rodzaj
metod sortowania, które są stosowane, kiedy z pewnych względów nie jest możliwe
jednoczesne umieszczenie wszystkich elementów zbioru sortowanego w pamięci
operacyjnej, przy zachowaniu wymogu sekwencyjnego dostępu do pliku.
Zakładamy, że pamięć zewnętrzna jest podzielona na bloki, a każdy blok jest
identyfikowany przez swój adres. Plik jest listą n rekordów (o tym samym formacie).
Ponadto zakładamy, że każdy plik zajmuje pewną liczbę bloków, a każdy blok mieści k
rekordów.
Za operację dominującą przyjmujemy przesłanie jednego bloku między pamięcią
operacyjną a pamięcią zewnętrzną.
W plikach nieuporządkowanych rekordy są ułożone w dowolnej kolejności.
Wykonanie operacji search() wymaga n/k przesłań bloków, a wykonanie operacji
insert() i delete() potrzebuje 1+n/k przesłań.
Podstawową wadą jest w tym przypadku długi czas działania operacji gdyż
rekordy: a , . . . , a pliku sÄ… przetwarzane sekwencyjnie , tzn.:
1 n
- aby odczytać a należy bezpośrednio przedtem odczytać a , . . . ,a ,
k 1 k-1
- aby zapisać nową wartość a należy zapisać bezpośrednio przedtem
k
a , . . . , a .
1 k-1
Jedną z najważniejszych metod sortowania plików jest sortowanie przez łączenie.
A
ączenie (lub scalanie) oznacza wiązanie dwóch (lub więcej) ciągów rekordów
uporzÄ…dkowanych w jeden ciÄ…g uporzÄ…dkowany.
1. Metoda zrównoważona (von Neumann)
·ð ð p1, p2, p3, p4  pliki (fizycznie, na ogół, odrÄ™bne urzÄ…dzenia)
·ð ð dane wejÅ›ciowe: n rekordów o kluczach a , . . . . ,a , na pliku p4
1 n
·ð ð pamięć RAM mieÅ›ci m rekordów
 IIUJ Metody Programowania strona: 2
Krok 1:
(sortowanie wstępne i rozdzielanie). Wczytuj po m kolejnych rekordów do
pamięci operacyjnej, sortuj i zapisuj posortowane ciągi długości m na pliki p1 i
p2 na przemian.
Krok 2:
(scalanie i rozdzielanie). Scalaj po jednym posortowanym ciÄ…gu z p1 i p2 i zapisuj
na przemian na pliki p3 i p4 (długość posortowanych ciągów podwaja się).
Iteracja:
Powtarzaj krok 2 zamieniając rolami p1, p2 z p3, p4 aż do osiągnięcia sytuacji
gdy pozostaje jeden plik posortowany zawierający cały ciąg.
Algorytm scalania posortowanych ciągów: taki jak dla tablic posortowanych (zamiast
dwóch tablic wejściowych są dwa ciągi posortowane: jeden z jednego, drugi z drugiego
pliku).
Przykład.
Po kroku 1 mamy 16 ciągów rosnących długości m rozdzielonych na p1
i p2, przy czym - oznacza k - ty ciąg w kolejności utworzenia:
p1: <1> <3> <5> <7> <9> <11> <13> <15>
p2: <2> <4> <6> <8> <10> <12> <14> <16>
po kroku 2:
p3: (<1>*<2>) (<5>*<6>) (<9>*<10>) (<13>*<14>)
p4: (<3>*<4>) (<7>*<8>) (<11>*<12>) (<15>*<16>)
(*) - oznacza ciąg powstały ze scalenia posortowanych
ciągów oraz
następna iteracja kroku 2 daje:
p1: ((<1>*<2>)*(<3>*<4>)) ( (<9>*<10>)*(<11>*<12>))
p2: ((<5>*<6>)*(<7>*<8>)) ((<13>*<14>)*(<15>*<16>))
(ciągi posortowane są już 4*m  elementowe)
 IIUJ Metody Programowania strona: 3
następna:
p3: (((<1>* <2>)*( <3>* <4>))*(( <5>* <6>)*( <7>* <8>)))
p4: (((<9>*<10>)*(<11>*<12>))*((<13>*<14>)*(<15>*<16>)))
(po jednym ciągu długości n/2 na każdym pliku)
i ostatnia daje cały ciąg posortowany na pliku p1.
Jeśli n nie jest potęgą dwójki to pojawiają się ciągi 'bez pary'  które się przepisuje.
Złożoność mierzy się liczbą
·ð ð faz (czyli iteracji kroku 2) - jest ich: éðlog (n/m)Å‚ð
·ð ð odczytów i zapisów rekordów na pliki - w każdej fazie jest n odczytów, n zapisów,
oraz nie wiÄ™cej niż n porównaÅ„ kluczy, w sumie zatem: Qð( n log (n/m)) operacji.
·ð ð dodatkowo: sortowanie wstÄ™pne fragmentów m-elementowych, zakÅ‚adajÄ…c
sortowanie szybkie: Qð( n/m * m log m) = Qð( n log m) porównaÅ„
Uwagi.
1. Im większa pamięć RAM (parametr m) tym szybsze sortowanie
2. Mając 2*k plików, k>2, można wykonywać scalanie równocześnie nie dwóch lecz
k ciągów (scalanie k - kierunkowe). Liczba faz maleje do log (n/m).
k
3. Jeśli k jest duże to można kolejne elementy przy scalaniu wyłaniać utrzymując
kopiec (kolejkę priorytetową) długości k zawierający klucz aktualnie czytany z
każdego wejściowego pliku. Wówczas kolejny element zapisywany na wyjście
otrzymywany jest w wyniku operacji Extract_min, a "doczytywany" z tego
samego pliku wejściowego element na miejsce usuniętego wstawiany jest
operacją Insert (można obie operacje połączyć w jedną "Replace_min").
 IIUJ Metody Programowania strona: 4
2. Sortowanie wielofazowe (czasami  polifazowe , pod wpływem ang. polyphase
sort) algorytm wynaleziony przez R. L. Gilstada
Dysponując k+1 plikami można rozdzielić początkowe ciągi tak, aby potem we
wszystkich etapach móc stosować scalanie k - kierunkowe.
Dla k=2 schemat rozdziału ciągów wg wartości liczb Fibonacciego, np. liczba
podciągów n/m = 13, rozdzielone na 8 i 5 podciągów:
p1: <1> <2> <3> <4> <5> <6> <7> <8>
p2: <9> <10> <11> <12> <13>
p3: pusty
Scalanie podciągów parami, z dwóch niepustych plików na aktualnie pusty plik, aż jeden
ze scalanych plików będzie pusty.
po fazie 1:
p1: <6> <7> <8>
p2: pusty
p3: (<1>*<9>)( <2>*<10>)( <3>*<11>)( <4>*<12>)( <5>*<13>)
po fazie 2:
p1: pusty
p2: (<6>*<1>*<9>) ( <7>*<2>*<10>) ( <8>*<3>*<11>)
p3: (<4>*<12>)( <5>*<13>)
po fazie 3:
p1: (<4>*<12>*<6>*<1>*<9>) ( <5>*<13>*<7>*<2>*<10>)
p2: ( <8>*<3>*<11>)
p3: pusty
po fazie 4:
p1: (<5>*<13>*<7>*<2>*<10>)
p2: pusty
p3: (<8>*<3>*<11>*<4>*<12>*<6>*<1>*<9>)
po fazie 5:
p1: pusty
p2: (<5>*<13>*<7>*<2>*<10>*<8>*<3>*<11>*<4>*<12>* <6>*<1>*<9>) // cały ciąg
p3: pusty
Metoda daje się uogólnić na dowolną wartość parametru k.
 IIUJ Metody Programowania strona: 5
3. B-drzewa1
B-drzewa są szczególnie użyteczne przy organizacji danych w pamięci
zewnętrznej. Pierwszą propozycję zastosowania B-drzew jako struktur danych dla
pamięci zewnętrznej przedstawili R. Bayer i E. Mcreight w 1972 roku.
Jak wspomniano wcześniej aby zapewnić wydajność operacji dostępu do pamięci
zewnętrznej dane są odczytywane i zapisywane blokami (stronami).
B-drzewa rzedu m to drzewa, których węzłami są bloki pamięci zewnętrznej
zawierające klucze w postaci uporządkowanej oraz odsyłacze, przy czym jeden blok
zawiera od m do 2m kluczy (wyjątkiem jest korzeń, który może zawierać od 1 do 2m)
i dlatego bloki są zawsze przynajmniej na wpół wypełnione kluczami. Blok posiadający k
kluczy zawsze zawiera k+1 wskaz
ników (potomków - dzieci). Liczba m (np. 1024) jest
kluczowa w wydajności B-drzew, ponieważ wysokość drzewa dla ogromnej ilości
węzłów liczonej w milionach lub miliardach będzie bardzo mała. Np. dla m=1024 w B-
drzewie o wysokości 2 można umieścić około miliona bloków.
Definicja
B-drzewo rzędu m to drzewo, w którym :
- klucze w bloku sÄ… uporzÄ…dkowane niemalejÄ…co,
- każdy blok zajmuje pamięć dla 2m kluczy i 2m+1 odsyłaczy,
- każdy blok (nie korzeń) zawiera k kluczy, przy czym m d" k d" 2m.
- blok-korzeń zawiera k kluczy, przy czym 1 d" k d" 2m.
- każdy blok-liść o k kluczach ma 0 następników
- każdy blok-nie-liść o k kluczach ma k+1 następników
- wszystkie bloki-liście są na jednym poziomie.
Fakt.
Jeśli w bloku są klucze i odsyłacze:
NEXT[0] INFO[1] NEXT[1] INFO[2] NEXT[2] & NEXT[k-1] INFO[k] NEXT[k+1]
to wszystkie klucze poddrzewa wskazywanego przez NEXT[i] mają wartości z
przedziału ( INFO[i] , INFO[i+1] ); przy czym INFO[0]= -" , INFO[ostatni+1] = +"
1
Na podstawie wykładu pana dr Jacka Lembasa  ASD: B-drzewa
 IIUJ Metody Programowania strona: 6
Przykład: B-drzewo rzędu 2. ( maksymalna pojemność bloku = 4)
M * * *
| |______________________________________
|____ |
^ ^
E J * * Q T W *
| | |______________________ | | | |______________________________
| |_____________ | | | |______________________ |
|____ | | | |______________ | |
| | | |____ | | |
^ ^ ^ ^ ^ ^ ^
A B C D F G H I K L * * N O P * R S * * U V * * X Y Z *
Operacja Search(x)
Wyszukiwanie poszukiwanego klucza x w B-drzewie zaczyna siÄ™ od korzenia. Klucze
w blokach sÄ… uporzÄ…dkowane niemalejÄ…co. PrzeglÄ…da siÄ™ je liniowo:
1. jeśli znajdzie się poszukiwany element w aktualnym bloku taki, że INFO[k]=x, to x
jest w B-drzewie.
2. w przeciwnym przypadku, jeśli INFO[k] < x < INFO[k+1] to określa się wskaz
nik
NEXT[k] i przeszukiwane jest wskazane poddrzewo.
3. jeśli przeszukano już liść, więc poddrzewo=null to elementu x nie ma w całym B-
drzewie.
Operacja Insert(x)
Operacja wstawienia zaczyna się od znalezienia bloku liścia do którego pasuje
wstawiany element, załóżmy, że znaleziony blok zawiera k kluczy.
1. Jeśli k<2m to wstawia się element porządkując blok.
2. Inaczej k=2m (za ciasno) wstaw porządkując 2m+1 kluczy i równo rozdziel blok,
następnie wstaw środkowy element na poziom wyżej
np. wstawiajÄ…c D: BCDEF Ä…ð .---D---.
BC** EF**
Dalej rekurencyjne wstawianie na kolejny poziom.
UWAGA.
Wysokość B-drzewa zwiększa się gdy rozdziela się korzeń.
 IIUJ Metody Programowania strona: 7
Przykład.
Wstawianie danych do B-drzewa rzędu 2.
1. Wstawiając kolejno: F L D P otrzymamy pełny korzeń: D F L P
2. Wstawiając E - mamy blok pełny, dzielimy go na dwie części, środkowy element
dodajemy do bloku na wyższym poziomie D E F L P :
F * * *
| |_____________
|___ |
^ ^
D E * * L P * *
3. Wstawiając następne: N I B A otrzymamy
F * * *
| |_____________
|___ |
^ ^
A B D E I L N P
4. WstawiajÄ…c G mamy
F L * *
| | |_______________________
| |_____________ |
|___ | |
^ ^ ^
A B D E G I * * N P * *
5. Wstawiając następne: Q R M C J K otrzymamy
C F L P
| | | | |___________________________________________
| | | |_________________________________ |
| | |_______________________ | |
| |_____________ | | |
|___ | | | |
^ ^ ^ ^ ^
A B * * D E * * G I J K M N * * Q R * *
 IIUJ Metody Programowania strona: 8
6. WstawiajÄ…c H mamy
C F L P
| | | | |___________________________________________
| | | |_________________________________ |
| | |_______________________ | |
| |_____________ | | |
|___ | | | |
^ ^ ^ ^ ^
A B * * D E * * G H I J K M N * * Q R * *
Następnie
C F I L P
| | | | | |_____________________________________________
| | | | |________________________________________ |
| | | |______________________________ | |
| | |_______________________ | | |
| |_____________ | | | |
|___ | | | | |
^ ^ ^ ^ ^ ^
A B * * D E * * G H * * J K * * M N * * Q R * *
Dalej
I * * *
| |_____________
|___ |
^ ^
C F * * L P * *
| | | | | |_________________________________________
| | | | |_________________________________ |
| | | |_________________________ | |
| | |_______________________ | | |
| |_____________ | | | |
|___ | | | | |
^ ^ ^ ^ ^ ^
A B * * D E * * G H * * J K * * M N * * Q R * *
 IIUJ Metody Programowania strona: 9
7. WstawiajÄ…c S T otrzymamy
I * * *
| |_____________
|___ |
^ ^
C F * * L P * *
| | | | | |________________________________________
| | | | |________________________________ |
| | | |______________________ | |
| | |_____________________ | | |
| |_____________ | | | |
|___ | | | | |
^ ^ ^ ^ ^ ^
A B * * D E * * G H * * J K * * M N * * Q R S T
Operacja Delete()
Usuwając klucz z B-drzewa możemy rozróżnić dwa przypadki:
(A). Usuwanie klucza z bloku wewnętrznego (nie-liścia), wtedy zamienia się go z
jednym z dwu najbliższych leksykograficznie kluczy, które znajdują w liściach
i mogą być łatwo usunięte:
np. po wyrzuceniu G zastąpić należy przez F lub H, które znajdują się w liściach
CDEF** lub HIJK**.
AB.G.L** AB.F.L** AB.H.L**
.---| |---. .---| |---. .---| |---.
CDEF** HIJK** CDE?** HIJK** CDEF** ?IJK**
(B). Usuwanie klucza z bloku-liścia, który ma k kluczy.
Jeśli k>m to po wyrzuceniu nadal ke"m, zatem koniec operacji
inaczej po wyrzuceniu blok ma m-1 kluczy i wówczas mogą zajść dwa przypadki:
1. Jeśli jeden z sąsiednich bloków ma p>m kluczy, to m-1+(1)+p>2m , (przy czym
(1)- klucz nadrzędny) czyli blok z sąsiadem można zrównoważyć:
np. usuwajÄ…c I mamy
.---G---. .---E---.
ABCDEF HIJ*** ABCD** FGHJ**
 IIUJ Metody Programowania strona: 10
2. Jeśli w sąsiednich blokach jest m kluczy, czyli m-1+(1)+m=2m , to blok z
sąsiadem i wspólnym kluczem nadrzędnym można połączyć:
np. usuwajÄ…c F
.---D---. ---------
ABC*** EFG*** ABCDEG
Dalej rekurencyjne usuwanie D ze bloku nadrzędnego.
Uwaga
Wysokość B-drzewa zmniejsza się gdy łączy się jedyny klucz korzenia z jego
dwoma potomkami.
Przykład. Usuwanie danych z B-Drzewa rzędu 2
I * * *
| |_____________
|___ |
^ ^
C F * * L P * *
| | | | | |________________________________________
| | | | |________________________________ |
| | | |______________________ | |
| | |_____________________ | | |
| |_____________ | | | |
|___ | | | | |
^ ^ ^ ^ ^ ^
A B * * D E * * G H * * J K * * M N * * Q R S T
1. Usuwając M mamy - równoważenie bloków .--P--.
Razem z nadrzędnym mają > 2m kluczy -N** QRST
I * * *
| |_____________
|___ |
^ ^
C F * * L Q * *
| | | | | |_____________________________________
| | | | |________________________________ |
| | | |_________________________ | |
| | |_____________________ | | |
| |_____________ | | | |
|___ | | | | |
^ ^ ^ ^ ^ ^
A B * * D E * * G H * * J K * * N P * * R S T *
 IIUJ Metody Programowania strona: 11
2. Usuwamy A - nie da się zrównoważyć z sąsiadem, ponieważ razem z
nadrzędnym mają 2m kluczy, zatem pozostaje - łączenie bloków
.--C--.
*B** DE**
I * * *
| |_____________
|___ |
^ ^
* F * * L Q * *
| | | | |___________________________________
| | | |____________________________ |
| | |____________________ | |
| |______________________ | | |
|____________ | | | |
| | | | |
^ ^ ^ ^ ^
B C D E G H * * J K * * N P * * R S T * -
konieczne ponowne Å‚Ä…czenie: .--I--.
*F** LQ**
F I L Q
| | | | |_____________________________________________
| | | |_________________________________ |
| | |______________________ | |
| |_____________ | | |
|__ | | | |
| | | | |
^ ^ ^ ^ ^
B C D E G H * * J K * * N P * * R S T *
3. UsuwajÄ…c L , zastÄ…pimy go najpierw przez N otrzymujÄ…c
F I N Q
| | | | |_____________________________________________
| | | |_________________________________ |
| | |______________________ | |
| |_____________ | | |
|__ | | | |
| | | | |
^ ^ ^ ^ ^
B C D E G H * * J K * * P * * * R S T *
następnie tworzymy połączony blok z bloków J K * * i P * * * oraz N i trzymamy
B-drzewo postaci:
 IIUJ Metody Programowania strona: 12
F I Q
| | | |
| | | |_________________________________
| | |______________________ |
| |_____________ | |
|__ | | |
| | | |
^ ^ ^ ^
B C D E G H * * J K N P R S T *
Minimalna i maksymalna liczba bloków i kluczy B-drzewa rzędu m na kolejnych
poziomach:
Poziom liczba bloków liczba kluczy (wartości)
[min, max] [min, max]
P-0: [ 1 ] [ 1 , 2m ]
P-1: [ 2 , 2m+1 ] [ 2m , 2m(2m+1) ]
P-2: [ 2(m+1), (2m+1)2 ] [ 2m(m+1), 2m(2m+1)2 ]
P-3: [ 2(m+1)2, (2m+1)3 ] [ 2m(m+1)2, 2m(2m+1)3 ]
...
P-h: [ 2(m+1)h-1, (2m+1)h ] [ 2m(m+1)h-1, 2m(2m+1)h ]
Stąd liczba n kluczy w B-drzewie rzędu m, wysokości h spełnia nierówności:
2(m+1)h -1 d" n d" (2m+1)h+1 -1 ,
czyli
(log (n+1)) 1 d" h d" log ((n+1)/2) .
(2m+1) (m+1)
Przyjmuje się mniej dokładne oszacowanie: log n d" h d"log n .
2m m
Przykład:
m=64=26, n=1000000000=109H"230 Ä…ð h d" 5 .