Collected by The_Wall (11/10/2005)
Giáo trình môn Phân tích Gii Thut – I C CN TH........................................................................Trang 67
1. Mc tiêu
2. Kin thc c bn cn có  hc chng này
3. Tài liu tham kho có liên quan n chng
4. Ni dung:
IV.1 - Mô hình x lý ngoài.
IV.2 - ánh giá các gii thut x lý ngoài.
IV.3 - Sp xp ngoài.
IV.4 - Lu tr thông tin trong tp tin.
Trong chng này chúng ta s nghiên cu hai vn  chính là sp xp d liu c l
u trong
 nh ngoài và k thut lu tr tp tin. Trong k thut lu tr tp tin chúng ta s s dng các cu trúc
 liu tun t, bng bm, tp tin ch mc và cu trúc B-cây.
IV.1- MÔ HÌNH X LÝ NGOÀI
Trong các gii thut mà chúng ta ã  cp t trc ti nay, chúng ta ã gi s rng s lng
các d liu vào là khá nh có th cha ht  b nh trong (main memory). Nhng u gì s xy ra
u ta mun x lý phiu u tra dân s toàn quc hay thông tin v qun lý t ai c nc chng hn?
Trong các bài toán nh vy, s lng d liu vt quá kh nng lu tr ca b nh trong.  có th
gii quyt các bài toán ó chúng ta phi dùng b nh ngoài  lu tr và x lý. Các thit b lu tr
ngoài nh bng t, a tu có kh nng lu tr ln nhng c m truy nhp hoàn toàn khác vi b
nh trong. Chúng ta cn tìm các cu trúc d liu và gii thut thích hp cho vic x lý d liu lu tr
trên b nh ngoài.
Kiu d liu tp tin là kiu thích hp nht cho vic biu din d liu c lu trong b nh
ngoài. Hu hành chia b nh ngoài thành các khi (block) có kích thc bng nhau, kích thc này
thay i tùy thuc vào hu hành nhng nói chung là t 512 bytes n 4096 bytes.
Trong quá trình x lý, vic chuyn giao d liu gia b nh trong và b nh ngoài c tin
hành thông qua vùng nhm (buffer). Bm là mt vùng dành riêng ca b nh trong mà kích
thc bng vi kích thc ca mt khi ca b nh ngoài.
Có th xem mt tp tin bao gm nhiu mu tin c lu trong các khi . Mi khi lu mt s
nguyên vn các mu tin, không có mu tin nào b chia ct  lu trên hai khi khác nhau.

ng  dài k là mt tp hp k mu tin ã oc sp th t theo khoá tc là, nu các mu tin
r
1
, r
2
, ..., r
k
có khoá ln lt là k
1
, k
2
, ..., k
k
to thành mt ng thì k
1
 k
2
 ...  k
k
.
Cho tp tin cha các mu tin r
1
, r
2
, ..., r
n
, ta nói tp tin c t chc thành ng có  dài k
u ta chia tp tin thành các n k mu tin liên tip và mi n là mt ng, n cui có th
không có  k mu tin, trong trng hp này ta gi n y là uôi (tail).
Ví d 4-1: Tp tin gm 14 mu tin có khóa là các s nguyên c t chc thành 4 ng 

trong hai tp tin G1, G2:
G1: 28 31 93 96 54 85 30 39 8 10 8 10 F1
G2: 3 5 10 40 9 65 13 90 69 77 22 F2
Bc 2: i vai trò ca F1 và G1, F2 và G2 cho nhau. Trn các ng  dài 2 trong hai tp
tin F1 và F2 c các ng  dài 4 ri ghi luân phiên vào trong hai tp tin G1 và G2:
G1: 3 5 28 31 9 54 65 85 8 10 69 77 F1
G2: 10 40 93 96 13 30 39 90 8 10 22 F2
Collected by The_Wall (11/10/2005)
Giáo trình môn Phân tích Gii Thut – I C CN TH........................................................................Trang 70
Bc 3: i vai trò ca F1 và G1, F2 và G2 cho nhau. Trn các ng  dài 4 trong hai tp
tin F1 và F2 c các ng  dài 8 ri ghi luân phiên vào trong hai tp tin G1 và G2:
G1: 3 5 10 28 31 40 93 96 8 8 10 10 22 69 77 F1
G2: 9 13 30 39 54 65 85 90 F2
Bc 4: i vai trò ca F1 và G1, F2 và G2 cho nhau. Trn các ng  dài 8 trong hai tp
tin F1 và F2 c các ng  dài 16 ri ghi luân phiên vào trong 2 tp tin G1 và G2.
G1: 3 5 9 10 13 28 30 31 39 40 54 65 85 90 93 96 F1
G2: 8 8 10 10 22 69 77 F2
Bc 5: i vai trò ca F1 và G1, F2 và G2 cho nhau. Trn các ng  dài 16 trong hai tp
tin F1 và F2 c 1 ng  dài 23 ri ghi vào trong tp tin G1.
G1: 3 5 8 8 9 10 10 10 13 22 28 30 31 39 40 54 65 77 85 90 93 96
Tp tin G1 cha các mu tin ã c sp còn tp tin G2 rng.
Chng trình
procedure Merge(k:integer; f1,f2,g1,g2: File of RecordType);
{Th tc này trn các ng  dài k và trong hai tp tin f1 và f2 thành các ng  dài 2k và
ghi luân phiên vào trong hai tp tin g1 và g2}
var
OutSwithh : boolean; {Nu OutSwitch = TRUE thì ghi vào tp tin g1, ngc li ghi vào g2}
Winner: integer; { chnh mu tin hin hành nào trong hai tp tin f1 và f2 sc ghi ra tp
tin g1 hoc g2}
Used: array[1..2] of integer; { Used[ij] ghi s mu tin ã c c trong ng hin ti ca tp

{ Chn Winner }
if Fin[1] then Winner := 2
else if Fin[2] then Winner := 1
else if current[1].key < Current[2].key then
Winner := 1
else Winner := 2;
if OutSwitch then Write(g1, Current[winner] )
else Write(g2, current[winner] );
GetRecord(Winner);
end;
OutSwitch := Not OutSwitch;
end;
end;
IV.3.2.Ci tin sp xp trn
Ta thy quá trình sp xp trn nói trên bt u t các ng  dài 1 cho nên phi sau logn
c gii thut mi kt thúc. Chúng ta có th tit kim thi gian bng cách chn mt s k thích hp
sao cho k mu tin có th cha trong b nh trong. Mi ln c vào b nh trong k mu tin, dùng
p xp trong (chng hn dùng QuickSort)  sp xp k mu tin này và ghi luân phiên vào hai tp tin
F1 và F2. Nh vy chúng ta bt u sp xp trn vi các tp tin c t chc thành các ng  dài
k.
Sau i bc thì  dài mi ng là k2
i
. Gii thut s kt thúc khi k2
i
 n hay i  log . Do ó
 phép truy xut khi s là . D thy c là ta tng c tc  sp xp trn.
Ví d 4-3: Ly tp tin F có 23 mu tin vi khóa là các s nguyên nh trong ví d 4-2
F: 28 31 3 5 93 96 10 40 54 85 65 9 30 39 90 13 10 8 69 77 8 10 22
Ta gi s b nh trong có th cha c 3 mu tin, ta c ln lt 3 mu tin ca F vào b nh
trong , dùng mt sp xp trong  sp xp chúng và ghi phiên vào 2 tp tin F1 và F2.

và ghi luân phiên vào trong h tp tin F[h+1], F[h+2], ... , F[m]. i vai trò ca F[i] và F[h+i]] cho
nhau (vi 1  i  h).