Các cấu trúc dữ liệu ở bộ nhớ ngoài

Ch ¬ng 7

C¸c cÊu tróc d÷ liÖu ë bé nhí ngoµi

Ch¬ng nµy giµnh ®Ó tr×nh bµy m« h×nh tæ chøc d÷ liÖu ë bé nhí ngoµi,

c¸c cÊu tróc d÷ liÖu ®Ó lu gi÷ vµ t×m kiÕm th«ng tin ë bé nhí ngoµi : file b¨m,

file cã chØ sè, B c©y. Víi mçi ph¬ng ph¸p tæ chøc file, chóng ta sÏ tr×nh bµy

c¸c thuËt to¸n ®Ó thùc hiÖn c¸c phÐp to¸n t×m kiÕm, xen vµo, lo¹i bá vµ söa ®æi

trªn file.

7.1. M« h×nh tæ chøc d÷ liÖu ë bé nhí ngoµi :

C¸c cÊu tróc d÷ liÖu (CTDL) mµ chóng ta xÐt tõ ®Çu tíi nay ®Òu lµ c¸c

CTDL ®îc lu gi÷ trong bé nhí chÝnh. Nhng trong nhiÒu ¸p dông, sè c¸c d÷ liÖu

cÇn ®îc lu gi÷ vît qu¸ kh¶ n¨ng cña bé nhí chÝnh. C¸c m¸y tÝnh hiÖn nay ®Òu

®îc trang bÞ c¸c thiÕt bÞ bé nhí ngoµi, th«ng thêng lµ ®Üa. Nã cã kh¶ n¨ng lu

gi÷ mét khèi lîng rÊt lín c¸c d÷ liÖu. Tuy nhiªn c¸c thiÕt bÞ nhí ngoµi cã

nh÷ng ®Æc trng truy cËp hoµn toµn kh¸c bé nhí chÝnh. Sau ®©y chóng ta sÏ

tr×nh bµy m« h×nh tæng qu¸t mµ c¸c hÖ ®iÒu hµnh hiÖn ®¹i sö dông ®Ó qu¶n lý

d÷ liÖu ë bé nhí ngoµi. Trong c¸c môc sau chóng ta sÏ xÐt c¸c CTDL ®Ó lu gi÷

file sao cho c¸c phÐp to¸n trªn file ®îc thùc hiÖn mét c¸ch hiÖu qu¶. §ã lµ file

b¨m, file cã chØ sè, B - c©y.

C¸c hÖ ®iÒu hµnh hiÖn ®¹i ®Òu cho chóng ta kh¶ n¨ng tæ chøc d÷ liÖu ë

bé nhí ngoµi díi d¹ng c¸c file.

Chóng ta cã thÓ quan niÖm file nh lµ mét tËp hîp nµo ®ã c¸c d÷ liÖu (c¸c

b¶n ghi) ®îc lu gi÷ ë bé nhí ngoµi. C¸c b¶n ghi trong file cã thÓ cã ®é dµi cè

®Þnh (sè c¸c trêng cña b¶n ghi lµ cè ®Þnh) hoÆc cã thÓ cã ®é dµi thay ®æi. C¸c

file víi c¸c b¶n ghi cã ®é dµi cè ®Þnh ®îc sö dông nhiÒu trong c¸c hÖ qu¶n trÞ

c¬ së d÷ liÖu. C¸c file víi c¸c b¶n ghi cã ®é dµi thay ®æi hay ®îc sö dông ®Ó lu

gi÷ c¸c th«ng tin v¨n b¶n. Chóng ta sÏ chØ xÐt c¸c file víi c¸c b¶n ghi cã ®é

dµi cè ®Þnh. C¸c kü thuËt mµ chóng ta sÏ tr×nh bµy ®Ó lu gi÷ vµ thao t¸c víi c¸c

file nµy cã thÓ söa ®æi ®Ó ¸p dông cho c¸c file víi c¸c b¶n ghi cã ®é dµi thay

®æi.

Trong ch¬ng nµy chóng ta sÏ hiÓu kho¸ cña b¶n ghi lµ mét tËp hîp nµo

®ã c¸c trêng cña b¶n ghi hoµn toµn x¸c ®Þnh b¶n ghi, tøc lµ hai b¶n ghi kh¸c

nhau ph¶i cã c¸c gi¸ trÞ kh¸c nhau trªn Ýt nhÊt mét trêng thuéc kho¸.

Trªn file chóng ta cÇn thùc hiÖn c¸c phÐp to¸n sau ®©y :

1. T×m kiÕm : t×m trong file c¸c b¶n ghi víi c¸c gi¸ trÞ cho tríc trªn mét nhãm

nµo ®ã c¸c trêng cña b¶n ghi.

2. Xen vµo : xen vµo file mét b¶n ghi nµo ®ã

172