Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 7: 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 ®Ó l-u 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 l-u gi÷ trong bé nhí chÝnh. Nh-ng trong nhiÒu ¸p dông, sè c¸c d÷

liÖu cÇn ®-îc l-u 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 l-u 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 tr-ng 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 ®Ó l-u 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 l-u 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 ®Ó l-u 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 ®Ó l-u 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 ®ã

0

3. Lo¹i bá : lo¹i bá khái file tÊt c¶ 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.

4. Söa ®æi : söa tÊt c¶ 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 b»ng c¸ch ®Æt l¹i gi¸ trÞ trªn c¸c tr-êng ®-îc chØ ®Þnh bëi c¸c

gi¸ trÞ míi ®· cho.

VÝ dô : gi¶ sö chóng ta cã file víi c¸c b¶n ghi chøa c¸c tr-êng (tªn s¶n

phÈm, n¬i s¶n xuÊt, gi¸). Ta c¸c cã thÓ cÇn t×m tÊt c¶ c¸c b¶n ghi víi tªn s¶n

phÈm = bãng ®Ìn 60W; thªm vµo file b¶n ghi (qu¹t bµn, nhµ m¸y ®iÖn c¬,

69.000); lo¹i bá tÊt c¶ c¸c b¶n ghi víi n¬i s¶n xuÊt = nhµ m¸y X; söa tÊt c¶ c¸c

b¶n ghi víi n¬i s¶n xuÊt = nhµ m¸y Z b»ng c¸ch thay gi¸ cò bëi gi¸ míi.

HÖ ®iÒu hµnh chia bé nhí ngoµi thµnh c¸c khèi vËt lý (physical block)

cã cì nh- nhau, ta gäi t¾t lµ c¸c khèi. Cì cña c¸c khèi thay ®æi tuú theo hÖ

®iÒu hµnh, th«ng th-êng lµ tõ 2⁹byte ®Õn 2¹²byte. Mçi khèi cã ®Þa chØ, ®ã lµ

®Þa chØ tuyÖt ®èi cña khèi ë trªn ®Üa, tøc lµ byte ®Çu tiªn cña khèi.

File ®-îc l-u gi÷ trong mét sè khèi, mçi khèi cã thÓ l-u gi÷ mét sè b¶n

ghi cña file. Trong mét khèi cã thÓ cßn mét sè byte ch-a ®-îc sö dông ®Õn.

Mçi b¶n ghi cã ®Þa chØ, ®Þa chØ cña b¶nghi lµ cÆp (k, s), trong ®ã k lµ ®Þa chØ

cña khèi chøa b¶n ghi, cßn s lµ sè byte trong khèi ®øng tr-íc byte b¾t ®Çu b¶n

ghi (s ®-îc gäi lµ offset). sau nµy khi nãi ®Õn con trá tíi khèi (tíi b¶n ghi) th×

ta hiÓu ®ã lµ ®Þa chØ khèi (b¶n ghi).

File cã thÓ ®-îc l-u gi÷ trong mét danh s¸ch liªn kÕt c¸c khèi. §iÓn

h×nh h¬n, file cã thÓ ®-îc l-u gi÷ trong c¸c khèi tæ chøc d-íi d¹ng c©y. C¸c

khèi kh«ng lµ l¸ cña c©y chøa c¸c con trá tíi mét sè khèi trong c©y.

Trong mçi khèi cã thÓ giµnh ra mét sè byte (phÇn nµy ®-îc gäi lµ ®Çu

khèi) ®Ó chøa c¸c th«ng tin cÇn thiÕt vÒ khèi, ch¼ng h¹n ®Ó ghi sè b¶n ghi

trong khèi.

Trong mét khèi, kh«ng gian ®Ó l-u tr÷ mét b¶n ghi ®-îc gäi lµ khèi con.

CÇn phÇn biÖt khèi con ®Çy vµ rçng. Khèi con ®Çy lµ khèi con cã chøa b¶n ghi,

ng-îc l¹i lµ khèi con rçng. §Ó chØ mét khèi con lµ ®Çy hoÆc rçng, trong ®Çu

khèi ta giµnh cho mçi khèi con mét bit (gäi lµ bit ®Çy), bit nhËn gi¸ trÞ 1 (0)

nÕu khèi con t-¬ng øng lµ ®Çy (rçng). Mét c¸ch kh¸c, trong mçi khèi con ta

giµnh ra mét bit (bit xo¸), bit nhËn gi¸ trÞ 1 cã nghÜa lµ b¶n ghi ®· bÞ xo¸.

§¸nh gi¸ thêi gian thùc hiÖn c¸c phÐp to¸n trªn file

C¸c phÐp to¸n trªn file (t×m kiÕm, xen vµo, lo¹i bá, söa ®æi) ®-îc thùc

hiÖn th«ng qua phÐp to¸n c¬ b¶n, ®äc mét khèi d÷ liÖu ë bé nhí ngoµi vµo

vïng ®Öm trong bé nhí chÝnh hoÆc viÕt c¸c d÷ liÖu ë vïng ®Öm trong bé nhí

chÝnh vµo mét khèi ë bé nhí ngoµi. Ta gäi phÐp to¸n nµy lµ phÐp to¸n truy cËp

khèi (block access). CÇn chó ý r»ng, viÖc chuyÓn mét khèi d÷ liÖu ë bé nhí

ngoµi vµo bé nhí chÝnh ®ßi hái nhiÒu thêi gian h¬n viÖc t×m kiÕm ®÷ liÖu trong

1

khèi khi nã ®· ë trong bé nhí chÝnh. Còng cÇn biÕt r»ng , c¸c d÷ liÖu cÇn ph¶i

cã ë bé nhí chÝnh tr-íc khi nã ®-îc sö dông b»ng c¸ch nµo ®ã. V× vËy khi

®¸nh gi¸ thêi gian thùc hiÖn mét thuËt to¸n thao t¸c víi c¸c d÷ liÖu ®-îc l-u

gi÷ trong file, chóng ta ph¶i tÝnh sè lÇn cÇn thiÕt ph¶i thùc hiÖn phÐp to¸n truy

cËp khèi. Sè lÇn thùc hiÖn phÐp to¸n truy cËp khèi ®-îc dïng ®Ó biÓu diÔn tÝnh

hiÖu qu¶ cña c¸c thuËt to¸n trªn c¸c file.

Tæ chøc file ®¬n gi¶n

Ph-¬ng ph¸p ®¬n gi¶n nhÊt, ®ång thêi còng kÐm hiÖu qu¶ nhÊt ®Ó l-u

gi÷ c¸c b¶n ghi cña file lµ, xÕp c¸c b¶n ghi cña file vµo mét sè khèi cÇn thiÕt

theo mét trËt tù tuú ý. C¸c khèi cã thÓ liªn kÕt víi nhau bëi c¸c con trá t¹o

thµnh mét danh s¸ch liªn kÕt c¸c khèi. Mét c¸ch kh¸c, ta còng cã thÓ sö dông

mét b¶ng ®Ó l-u gi÷ ®Þa chØ cña c¸c khèi.

PhÐp to¸n t×m kiÕm c¸c b¶n ghi theo c¸c gi¸ trÞ ®· biÕt trªn mét sè

tr-êng ®-îc thùc hiÖn b»ng c¸ch ®äc lÇn l-ît c¸c b¶n ghi trong c¸c khèi. ViÖc

xen vµo file mét b¶n ghi míi ®-îc thùc hiÖn b»ng c¸ch xen nã vµo khèi cuèi

cïng cña file nÕu trong ®ã cßn chç, nÕu kh«ng th× thªm vµo file mét khèi míi

vµ ®Æt b¶n ghi cÇn xen vµo ®ã. Muèn lo¹i bá c¸c b¶n ghi, tr-íc hÕt ta cÇn ®Þnh

vÞ ®-îc c¸c b¶n ghi cÇn lo¹i bá, sau ®ã ta sÏ tiÕn hµnh xo¸ bá. ViÖc xo¸ bá mét

b¶n ghi cã thÓ thùc hiÖn b»ng nhiÒu c¸ch. Ch¼ng h¹n cã thÓ ®Æt l¹i gi¸ trÞ cña

bit xo¸ trong b¶n ghi. Trong tr-êng hîp nµy viÖc sö dông l¹i kh«ng gian cña

b¶n ghi nµy ®Ó l-u gi÷ b¶n ghi míi cÇn ph¶i thËn träng. NÕu trong hÖ c¬ së d÷

liÖu cã sö dông con trá trá tíi b¶n ghi (tr-êng hîp nµy, b¶n ghi ®-îc xem lµ bÞ

®ãng chÆt), th× ta kh«ng ®-îc sö dông kh«ng gian cña nã ®Ó l-u gi÷ b¶n ghi

míi nµy.

Víi c¸ch tæ chøc file tuÇn tù nh- trªn, c¸c phÐp to¸n trªn file sÏ chËm,

v× chóng ®ßi hái ph¶i xem xÐt toµn bé c¸c b¶n ghi trong file. Trong c¸c môc

sau nµy chóng ta sÏ tr×nh bµy c¸c tæ chøc file -u viÖt h¬n, cho phÐp ta mçi lÇn

cÇn truy cËp ®Õn mét b¶n ghi, chØ cÇn ®äc vµo bé nhí chÝnh mét phÇn nhá cña

file.

Chóng ta kh«ng thÓ viÕt b»ng Pascal hoÆc b»ng mét ng«n ng÷ kh¸c c¸c

thñ tôc cã ®Ò cËp ®Õn c¸c d÷ liÖu ë møc khèi vËt lý vµ c¸c ®Þa chØ khèi. Do ®ã

trong c¸c ph-¬ng ph¸p tæ chøc file ®-îc tr×nh bµy sau ®©y, ta sÏ m« t¶ mét

c¸ch kh«ng h×nh thøc c¸c thuËt to¸n thùc hiÖn c¸c phÐp to¸n trªn c¸c file.

7.2. File b¨m :

CÊu tróc cña file b¨m hoµn toµn t-¬ng tù nh- cÊu tróc b¶ng b¨m më ë

bé nhí trong ®· ®-îc chóng ta ®Ò cËp ®Õn trong ch-¬ng 5. T- t-ëng cña tæ

chøc file b¨m lµ nh- sau : ta chia tËp hîp c¸c b¶n ghi cña file thµnh K líp. Víi

mçi líp, t¹o ra mét danh s¸ch liªn kÕt c¸c khèi, c¸c khèi nµy chøa c¸c b¶n ghi

cña líp. Ta sö dông mét b¶ng gåm K con trá, (b¶ng chØ dÉn) mçi con trá trá

tíi khèi ®Çu tiªn trong danh s¸ch liªn kÕt c¸c khèi cña mét líp.

2

H×nh 7.1 biÓu diÔn cÊu tróc cña mét file b¨m.

0

i

K-1

H×nh 7.1 CÊu tróc file b¨m

ViÖc ph©n phèi c¸c b¶n ghi cña file vµo c¸c líp ®-îc thùc hiÖn bëi hµm

b¨m h. §ã lµ hµm x¸c ®Þnh trªn tËp c¸c gi¸ trÞ kho¸ cña c¸c b¶n ghi vµ nhËn

c¸c gi¸ trÞ nguyªn tõ 0 ®Õn K-1. NÕu x lµ mét gi¸ trÞ kho¸ vµ h(x) = i, 0  i 

K-1, th× b¶n ghi víi kho¸ x thuéc líp thø i.

§Ó t×m kiÕm b¶n ghi víi kho¸ x cho tr-íc, ®Çu tiªn ta tÝnh h(x), con trá

chøa ë thµnh phÇn thø i = h(x) trong b¶ng chØ dÉn ta t×m ®Õn c¸c khèi cña líp

i. lÇn l-ît ®äc c¸c khèi, ta sÏ t×m ra b¶n ghi víi kho¸ x, hoÆc ®äc hÕt c¸c khèi

mµ kh«ng thÊy cã nghÜa lµ b¶n ghi kh«ng cã ë trong file.

Muèn xen vµo file b¶n ghi víi kho¸ x, ta cÇn kiÓm tra xem nã cã ë trong

file hay ch-a. NÕu ch-a ta cã thÓ xen nã vµo khèi ®Çu tiªn trong danh s¸ch c¸c

khèi cña h (x), nÕu t¹i ®ã cßn ®ñ chç cho b¶n ghi. NÕu tÊt c¶ c¸c khèi cña líp

h(x) ®Òu ®Çy, ta thªm vµo danh s¸ch c¸c khèi cña líp h(x) mét khèi míi vµ ®Æt

b¶n ghi vµo ®ã.

§Ó lo¹i bá b¶n ghi víi kho¸ x, tr-íc hÕt ta cÇn x¸c ®Þnh vÞ trÝ cña b¶n

ghi trong file b»ng c¸ch ¸p dông thñ tôc t×m kiÕm. Sau ®ã cã thÓ xo¸ bá b¶n

ghi nµy b»ng c¸ch, ch¼ng h¹n cho bit xo¸ nhËn gi¸ trÞ 1.

CÊu tróc file b¨m lµ cÊu tróc rÊt cã hiÖu qu¶ nÕu c¸c phÐp to¸n trªn file

chØ ®ßi hái ®Õn viÖc truy cËp c¸c b¶n ghi theo kho¸. Gi¶ sö file cã n b¶n ghi,

nÕu hµm b¨m ®-îc thiÕt kÕ tèt, th× trung b×nh mçi líp chøa n/k b¶n ghi. Gi¶ sö

mçi khèi chøa ®-îc m b¶n ghi. Nh- vËy mçi líp gåm kho¶ng n/mk khèi. Tøc

lµ c¸c phÐp to¸n trªn file b¨m sÏ k lÇn nhanh h¬n so víi tæ chøc file tuÇn tù.

7.3. File cã chØ sè ( indexed file)

CÊu tróc file b¨m ®-îc t¹o ra dùa trªn kho¸ cña b¶n ghi. Trong môc nµy

chóng ta tr×nh bµy mét ph-¬ng ph¸p tæ chøc file kh¸c còng dùa vµo kho¸ cña

3

b¶n ghi b»ng c¸ch s¾p xÕp c¸c b¶n ghi theo thø tù t¨ng dÇn cña c¸c gi¸ trÞ

kho¸.

CÊu tróc file cã chØ sè ®-îc h×nh thµnh nh- sau :

Ta s¾p xÕp c¸c b¶n ghi cña file theo thø tù kho¸ t¨ng dÇn vµo mét sè

khèi cÇn thiÕt. Ta cã thÓ s¾p xÕp c¸c b¶n ghi vµo mét khèi cho tíi khi khèi

®Çy. Song th«ng th-êng, trong mçi khèi ng-êi ta ®Ó giµnh l¹i mét kh«ng gian

cho c¸c b¶n ghi ®-îc thªm vµo file sau nµy. Lý do lµ ®Ó phÐp to¸n xen vµo file

®-îc thùc hiÖn dÔ dµng h¬n. Ta sÏ gäi file gåm c¸c b¶n ghi chøa trong c¸c

khèi nµy lµ file chÝnh, ®Ó ph©n biÖt víi file chØ sè ®-îc t¹o ra sau ®©y.

ChØ sè cña mét khèi lµ cÆp (v, b), trong ®ã b lµ ®Þa chØ cña khèi, cßn v lµ

gi¸ trÞ kho¸ nhá nhÊt cña c¸c b¶n ghi trong khèi b. Tõ c¸c khèi cña file chÝnh,

ta sÏ t¹o ra file chØ sè (index file), file nµy gåm c¸c chØ sè khèi cña file chÝnh.

C¸c chØ sè khèi ®-îc s¾p xÕp theo thø tù t¨ng dÇn cña kho¸ vµo mét sè khèi

cÇn thiÕt. C¸c khèi nµy cã thÓ ®-îc mãc nèi víi nhau t¹o thµnh mét danh s¸ch

liªn kÕt. Trong tr-êng hîp nµy file chØ sè gåm mét danh s¸ch liªn kÕt c¸c khèi,

c¸c khèi chøa c¸c chØ sè khèi cña file chÝnh. Mét c¸ch kh¸c ta còng cã thÓ sö

dông mét b¶ng ®Ó l-u gi÷ ®Þa chØ cña c¸c khèi trong file chØ sè. H×nh 7.2 minh

ho¹ cÊu tróc cña file cã chØ sè.

file chØ sè

file chÝnh

H×nh 7.2. CÊu tróc file cã chØ sè

Sau ®©y chóng ta sÏ xÐt sù thùc hiÖn c¸c phÐp to¸n trªn file ®-îc tæ chøc

d-íi d¹ng file cã chØ sè

T×m kiÕm :

Gi¶ sö ta cÇn t×m b¶n ghi x víi kho¸ v cho tr-íc. Tr-íc hÕt ta cÇn t×m

trªn file chØ sè mét chØ sè (v₁, b₁) sao cho v₁lµ gi¸ trÞ kho¸ lín nhÊt trong file

chØ sè tho¶ m·n ®iÒu kiÖn v₁ v. Ta sÏ nãi v₁phñ v.

ViÖc t×m kiÕm trªn file chØ sè mét gi¸ trÞ kho¸ v₁phñ gi¸ trÞ kho¸ v cho

tr-íc cã thÓ thùc hiÖn b»ng c¸ch t×m kiÕm tuÇn tù hoÆc t×m kiÕm nhÞ ph©n.

Trong t×m kiÕm tuÇn tù, ta cÇn xem xÐt tÊt c¶ c¸c b¶n ghi cña file chØ sè

cho tíi khi t×m thÊy mét chØ sè (v₁, b₁) víi v₁phñ v. NÕu v nhá h¬n gi¸ trÞ kho¸

4

cña b¶n ghi ®Çu tiªn trong file chØ sè th× ®iÒu ®ã cã nghÜa lµ trong file chØ sè

kh«ng chøa gi¸ trÞ kho¸ phñ v.

Ph-¬ng ph¸p cã hiÖu qu¶ h¬n lµ t×m kiÕm nhÞ ph©n. Gi¶ sö c¸c b¶n ghi

cña file chØ sè ®-îc s¾p xÕp vµo c¸c khèi ®-îc ®¸nh sè tõ 1 ®Õn m. XÐt khèi

thø  m/2. Gi¶ sö (v₂, b₂) lµ b¶n ghi ®Çu tiªn trong khèi. So s¸nh gi¸ trÞ kho¸

cho tr-íc v víi gi¸ trÞ kho¸ v₂. NÕu v < v₂ta tiÕn hµnh t×m kiÕm trªn c¸c khèi

1,2, . . .,  m/2 - 1. Cßn nÕu v  v₂, ta tiÕn hµnh t×m kiÕm trªn c¸c khèi  m/2 ,

 m/2. + 1, . . . , m. Qu¸ tr×nh trªn ®-îc lÆp l¹i cho tíi khi ta chØ cÇn t×m

kiÕm trªn mét khèi. Lóc nµy ta chØ viÖc lÇn l-ît so s¸nh gi¸ trÞ kho¸ v cho

tr-íc víi gi¸ trÞ kho¸ chøa trong khèi nµy.

§Ó t×m ra b¶n ghi x víi kho¸ v cho tr-íc, tr-íc hÕt ta t×m trªn file chØ sè

mét chØ sè (v₁, b₁) víi v₁phñ v. Sau ®ã lÇn l-ît xÐt c¸c b¶n ghi trong khèi cã

®Þa chØ b₁®Ó ph¸t hiÖn ra b¶n ghi cã kho¸ v, hoÆc kh«ng nÕu trong khèi kh«ng

cã b¶n ghi nµo víi kho¸ lµ v. NÕu trªn file chØ sè kh«ng chøa gi¸ trÞ kho¸ v₁

phñ v, th× file chÝnh kh«ng chøa b¶n ghi cã kho¸ v.

Xen vµo :

Gi¶ sö ta cÇn thªm vµo file b¶n ghi r víi gi¸ trÞ kho¸ v.

Gi¶ sö file chÝnh ®-îc chøa trong c¸c khèi B₁, B₂, . . . , B _kvµ c¸c gi¸ trÞ

kho¸ cña c¸c b¶n ghi trong khèi B_inhá h¬n c¸c gi¸ trÞ kho¸ trong khèi B _{i +1}.

Tr-íc hÕt ta cÇn t×m ra khèi B_icÇn ph¶i xÕp b¶n ghi r vµo ®ã. Muèn vËy

ta ¸p dông thñ tôc t×m kiÕm trªn file chØ sè ®Ó t×m ra chØ sè (v₁, b₁) víi v₁phñ

v. NÕu t×m thÊy th× B _ilµ khèi cã ®Þa chØ b ₁, ng-îc l¹i B _ilµ khèi B ₁.

Trong tr-êng hîp B _ich-a ®Çy vµ r cßn ch-a cã ë trong khèi B _ith× ta

xÕp b¶n ghi r vµo ®óng vÞ trÝ cña nã, tøc lµ ph¶i ®¶m b¶o trËt tù t¨ng dÇn theo

kho¸.

NÕu B_ilµ B₁th× sau khi thªm vµo b¶n ghi r, nã trë thµnh b¶n ghi ®Çu tiªn

trong khèi B₁, do ®ã ta cÇn ph¶i tiÕn hµnh söa ®æi chØ sè cña khèi B₁trong file

chØ sè.

Trong tr-êng hîp B _i®· ®Çy, ta tiÕn hµnh xÕp b¶n ghi r vµo ®óng vÞ trÝ

cña nã trong B _i, khi ®ã cßn thõa ra mét b¶n ghi. T×m ®Õn khèi B _{i + 1}(ta biÕt

®-îc ®Þa chØ cña khèi B _{i + 1}b»ng c¸ch t×m trong chØ sè). NÕu B _{i + 1}ch-a ®Çy

th× ta xÕp b¶n ghi thõa ra cña B _ivµo vÞ trÝ ®Çu tiªn trong khèi B _{i + 1}®ång thêi

söa l¹i chØ sè cña B _{i + 1}trong file chØ sè. NÕu khèi còng ®Çy hoÆc kh«ng tån

t¹i khi B _ilµ B _kth× ta thªm vµo file chÝnh mét khèi míi vµ xÕp b¶n ghi r vµo

khèi míi nµy. ChØ sè cña khèi míi thªm vµo cÇn ph¶i ®-îc xen vµo file chØ sè.

Lo¹i bá :

§Ó lo¹i bá b¶n ghi r víi kho¸ v, ta cÇn ¸p dông thñ tôc t×m kiÕm ®Ó ®Þnh

vÞ b¶n ghi trong file. Sau ®ã sÏ tiÕn hµnh xo¸ bá r b»ng nhiÒu c¸ch kh¸c nhau,

5

ch¼ng h¹n cã thÓ ®Æt l¹i gi¸ trÞ cña bit ®Çy/rçng t-¬ng øng víi b¶n ghi cÇn xo¸

ë ®Çu khèi.

Söa ®æi :

Gi¶ sö ta cÇn söa ®æi b¶n ghi víi kho¸ v. NÕu c¸c gi¸ trÞ cÇn söa kh«ng

lµ gi¸ trÞ cña c¸c tr-êng thuéc kho¸, th× ta chØ cÇn ¸p dông thñ tôc t×m kiÕm ®Ó

t×m ra b¶n ghi vµ tiÕn hµnh c¸c söa ®æi cÇn thiÕt. NÕu c¸c gi¸ trÞ cÇn söa thuéc

kho¸ th× viÖc söa ®æi ®-îc thùc hiÖn b»ng c¸ch lo¹i bá b¶n ghi cò, xen vµo b¶n

ghi míi.

7.4. B - c©y.

Môc ®Ých cña chóng ta lµ nghiªn cøu c¸c cÊu tróc d÷ liÖu biÓu diÔn file

sao cho c¸c phÐp to¸n trªn file ®-îc thùc hiÖn hiÖu qu¶, tøc lµ víi sè lÇn thùc

hiÖn phÐp to¸n truy cËp khèi Ýt nhÊt cã thÓ ®-îc, khi cÇn ph¶i t×m kiÕm, xen

vµo, lo¹i bá hoÆc söa ®æi c¸c b¶n ghi trªn file. B - c©y lµ mét cÊu tróc d÷ liÖu

®Æc biÖt thÝch hîp ®Ó biÓu diÔn file. Trong môc nµy chóng ta sÏ tr×nh bµy B -

c©y vµ c¸c kü thuËt ®Ó thùc hiÖn c¸c phÐp to¸n t×m kiÕm, xen vµo vµ lo¹i bá

trªn B - c©y.

C©y t×m kiÕm ®a nh¸nh ( Multiway Search Trees)

C©y t×m kiÕm m nh¸nh lµ sù tæng qu¸t ho¸ cña c©y t×m kiÕm nhÞ ph©n,

trong ®ã mçi ®Ønh cña c©y cã nhiÒu nhÊt m con. C¸c ®Ønh cña c©y ®-îc g¾n víi

c¸c gi¸ trÞ kho¸ cña c¸c b¶n ghi. NÕu ®Ønh a cã r con ( r  m) th× nã chøa ®óng

r - 1 kho¸ ( k₁, k₂, . . . , k_r-1), trong ®ã k₁< k₂< . . . < k_r-1(Chóng ta gi¶ thiÕt

r»ng c¸c gi¸ trÞ kho¸ ®-îc s¾p xÕp thø tù tuyÕn tÝnh). Tæng qu¸t ho¸ tÝnh chÊt

vÒ kho¸ g¾n víi c¸c ®Ønh cña c©y t×m kiÕm nhÞ ph©n, c©y t×m kiÕm m nh¸nh

ph¶i tho¶ m·n tÝnh chÊt sau ®©y. NÕu ®Ønh a cã r con vµ chøa c¸c kho¸ ( k₁, k₂,

. . . , k_r-1) th× c¸c kho¸ chøa trong c¸c ®Ønh cña c©y con thø nhÊt cña ®Ønh a nhá

h¬n k₁, cßn c¸c kho¸ chøa trong c¸c ®Ønh cña c©y con thø i ( i = 2, . . . , r-1)

ph¶i lín h¬n hoÆc b»ng k _{i - 1}vµ nhá h¬n k _i, c¸c kho¸ chøa trong c¸c ®Ønh cña

c©y con thø r ph¶i lín h¬n hoÆc b»ng k . Mçi l¸ cña c©y chøa mét sè kho¸,

r-1

tèi ®a lµ s.

C¸c phÐp to¸n t×m kiÕm, xen vµo vµ lo¹i bá trªn c©y t×m kiÕm m nh¸nh

®-îc thùc hiÖn b»ng c¸c kü thuËt t-¬ng tù nh- ®èi víi c©y t×m kiÕm nhÞ ph©n.

B - c©y ( B - Trees)

B - c©y lµ mét lo¹i ®Æc biÖt cña c©y t×m kiÕm m nh¸nh c©n b»ng (xem l¹i

kh¸i niÖm c©y c©n b»ng trong môc 7, ch-¬ng 4). Cô thÓ, B - c©y ®-îc ®Þnh

nghÜa nh- sau :

B - c©y cÊp m lµ c©y t×m kiÕm m nh¸nh tho¶ m·n c¸c tÝnh chÊt sau ®©y

6

1. NÕu c©y kh«ng ph¶i lµ c©y chØ gåm cã gèc th× gèc cã Ýt nhÊt hai con vµ

nhiÒu nhÊt m con.

2. Mçi ®Ønh trong cña c©y, trõ gèc, cã Ýt nhÊt  m/2 con vµ nhiÒu nhÊt m con.

3. TÊt c¶ c¸c l¸ cña c©y trªn cïng mét møc. (Nãi c¸ch kh¸c, tÊt c¶ c¸c ®-êng

®i tõ gèc tíi l¸ c©y cã cïng ®é dµi).

T- t-ëng cña viÖc tæ chøc file d-íi d¹ng B - c©y lµ nh- sau. Ta s¾p xÕp

c¸c b¶n ghi cña file (file chÝnh) vµo mét sè khèi cÇn thiÕt. Mçi khèi nµy sÏ lµ

l¸ cña B - c©y. Trong mçi khèi c¸c b¶n ghi ®-îc s¾p xÕp theo thø tù t¨ng dÇn

cña kho¸. C¸c chØ sè cña c¸c khèi nµy (c¸c l¸) l¹i ®-îc s¾p xÕp vµo mét sè

khèi míi. Trong mçi khèi nµy, c¸c chØ sè ®-îc s¾p xÕp theo thø tù t¨ng dÇn

cña kho¸. Trong B - c©y, c¸c khèi nµy sÏ lµ c¸c ®Ønh ë møc trªn cña møc c¸c

l¸. Ta l¹i lÊy chØ sè cña c¸c khèi võa t¹o ra s¾p xÕp vµo mét sè khèi míi. C¸c

khèi nµy l¹i lµ c¸c ®Ønh ë møc trªn cña møc tõ ®ã ®-îc t¹o ra. Qu¸ tr×nh trªn

sÏ tiÕp tôc cho tíi khi c¸c chØ sè cã thÓ xÕp gän vµo mét khèi. Khèi nµy lµ ®Ønh

cña c©y B - c©y.

Nh- vËy, mçi ®Ønh cña B - c©y lµ mét khèi. Mçi ®Ønh trong cña B - c©y

cã d¹ng

(p₀, v₁, p₁, v₂, p₂, . . . , v_n, p_n)

trong ®ã v₁< v₂< . . . < vµ ( v_i, p_i), 0  i  n, lµ chØ sè cña mét khèi, tøc lµ v_ilµ

gi¸ trÞ kho¸ nhá nhÊt trong mét khèi, cßn p_ilµ con trá trá tíi khèi chøa kho¸

nhá nhÊt v_i, tøc lµ con trá trá tíi ®Ønh con thø i cña ®Ønh trong ®ang nãi tíi.

CÇn l-u ý r»ng, gi¸ trÞ cña kho¸ v₀kh«ng ®-îc l-u gi÷ ë mçi ®Ønh trong, lý do

lµ ®Ó tiÕt kiÖm bé nhí.

11 khèi ®-îc ®¸nh sè B₁, B₂, . . . , B ₁₁. Mçi khèi lµ ®Ønh trong chøa ®-îc 3 chØ

sè nguyªn ®-îc l-u gi÷ ë c¸c khèi tõ B₅®Õn B₁₁.

7

B₁

B₂

B₅

B₃

B₄

B₆

B₇

B₈--

B₉

B₁₀

B₁₁

T×m kiÕm

Gi¶ sö chóng ta cÇn t×m b¶n ghi r cã kho¸ v cho tr-íc. Chóng ta cÇn

ghi r nÕu nã cã ë trong file.

Trong qu¸ tr×nh t×m kiÕm, gi¶ sö t¹i mét thêi ®iÓm nµo ®ã ta ®¹t tíi ®Ønh

B. NÕu khèi B lµ l¸, ta t×m trong khèi B xem nã cã chøa b¶n ghi r hay kh«ng.

Nhí l¹i r»ng c¸c b¶n ghi cña file ®-îc xÕp vµo c¸c khèi theo thø tù t¨ng dÇn

cña kho¸, do ®ã sù t×m kiÕm trong khèi B cã thÓ tiÕn hµnh b»ng kü thuËt t×m

NÕu B lµ mét ®Ønh trong chøa ( p₀, v₁, p₁, . . . , v_n, p_n) th× ta cÇn x¸c ®Þnh

vÞ trÝ cña gi¸ trÞ kho¸ v trong d·y gi¸ trÞ kho¸ v₁, v₂, . . . , v_n. NÕu v < v₁th× ta ®i

xuèng ®Ønh ®-îc trá bëi p_o. NÕu v_i v < v _{i + 1}th× ta ®i xuèng ®Ønh ®-îc trá bëi

p_i( i = 1, 2, . . . n - 1). Cßn nÕu v_n< v th× ®i xuèng ®Ønh ®-îc trá bëi p_n.

Xen vµo :

ta ¸p dông thñ tôc t×m kiÕm ®Ó t×m ra khèi B cÇn ph¶i xen b¶n ghi r vµo ®ã.

NÕu khèi B cßn ®ñ chç cho b¶n ghi r th× ta xÕp b¶n ghi r vµo khèi B sao

cho thø tù t¨ng dÇn cña kho¸ ®-îc b¶o tån. Chó ý r»ng, r kh«ng thÓ lµ b¶n ghi

®Çu tiªn cña khèi B, trõ khi B lµ l¸ ngoµi cïng bªn tr¸i. NÕu B lµ l¸ ngoµi cïng

bªn tr¸i th× gi¸ trÞ kho¸ nhá nhÊt trong khèi B kh«ng cã mÆt trong c¸c ®Ønh lµ

NÕu khèi B kh«ng cßn ®ñ kh«ng gian ®Ó l-u gi÷ b¶n ghi r th× ta thªm

8

sang khèi B'. Sau ®ã xÕp b¶n ghi r vµo khèi B hoÆc khèi B' sao cho vÉn ®¶m

b¶o ®-îc tÝnh t¨ng dÇn cña c¸c gi¸ trÞ kho¸. Gi¶ sö Q lµ cha cña B, ta cã thÓ

biÕt ®-îc Q nÕu trong qu¸ tr×nh t×m kiÕm, ta l-u l¹i vÕt cña ®-êng ®i tõ gèc tíi

B. Gi¶ sö chØ sè cña khèi B' lµ (v', p'), trong ®ã v' lµ gi¸ trÞ kho¸ nhá nhÊt trong

B', cßn p' lµ ®Þa chØ cña khèi B'. ¸p dông thñ tôc trªn ®Ó xen _v', p') vµo khèi

mét ®Ønh míi Q', nã lµ em liÒn kÒ cña Q. Sau ®ã l¹i ph¶i t×m ®Õn cha cña ®Ønh

Q ®Ó ®-a vµo chØ sè cña khèi míi Q'. Qu¸ tr×nh cã thÓ tiÕp diÔn vµ dÉn ®Õn

Trong tr-êng hîp nµy, ta ph¶i t¹o ra mét gèc míi cã ®óng hai con, mét con lµ

gèc cò, mét con lµ ®Ønh míi ®-a vµo.

Tr-íc hÕt ta ph¶i t×m khèi cÇn ph¶i ®-a b¶n ghi nµy vµo. B¾t ®Çu tõ gèc B₁, v×

21 < 32 < 143, ta ®i xuèng B₃. T¹i B₃, 32 < 58, ta ®i xuèng B₇. B₇lµ l¸, vËy

cÇn ph¶i ®-a b¶n ghi víi kho¸ 32 vµo B7. Nh-ng khèi B₇®· ®Çy. Ta thªm vµo

khèi míi B₁₂vµ xÕp c¸c b¶n ghi víi kho¸ 21, 32 vµo khèi B₇, xÕp c¸c b¶n ghi

víi kho¸ 36, 49 vµo khèi B₁₂. ChØ sè cña khèi B₁₂chøa gi¸ trÞ kho¸ 36. CÇn

ph¶i xÕp chØ sè B₁₂vµo cha cña B₇lµ B₃. Nh-ng B₃còng ®Çy. Thªm vµo khèi

míi B₁₃. Sau ®ã c¸c chØ sè cña c¸c khèi B₇, B₁₂®-îc xÕp vµo B₃cßn c¸c chØ sè

chØ cña khèi B₁₃cÇn ®-îc xÕp vµo khèi B1. Nh-ng B₁còng ®Çy thªm vµo B -

B₁₄. V× B₁lµ gèc, ta ph¶i thªm vµo gèc míi, khèi B₁₅vµ xÕp c¸c chØ sè cña B₁

B₁₅

B1

B14

B2

B3

B₁₃

B₄

--

B5

B6

B7

B12

B8

B9

B10

b¶n ghi víi gi¸ trÞ kho¸ 32

Lo¹i bá

9

thñ tôc t×m kiÕm ®Ó t×m ra l¸ B chøa b¶n ghi r. Sau ®ã lo¹i bá b¶n ghi r trong

khèi B.

Gi¶ sö sau khi lo¹i bá B kh«ng rçng. Trong tr-êng hîp nµy, nÕu r kh«ng

ph¶i lµ b¶n ghi ®Çu tiªn trong B, ta kh«ng ph¶i lµm g× thªm. NÕu r lµ b¶n ghi

®Çu tiªn trong B, th× sau khi xo¸ r, chØ sè cña B ®· thay ®æi. Do ®ã ta cÇn t×m

®Õn ®Ønh Q lµ cha cña B. NÕu B lµ con tr-ëng cña Q th× gi¸ trÞ kho¸ v' trong chØ

sè (v', p') cña B kh«ng cã trong Q. Trong tr-êng hîp nµy ta cÇn t×m ®Õn tiÒn

trÞ kho¸ nhá nhÊt trong B ®-îc chøa trong A'. Do ®ã trong A', ta cÇn thay gi¸

trÞ kho¸ cò v bëi gi¸ trÞ míi v'.

Gi¶ sö sau khi lo¹i bá b¶n ghi r, B trë thµnh rçng. Lo¹i bá l¸ B khái B

NÕu sau khi lo¹i bá, sè c¸c con cña ®Ønh Q Ýt h¬n m/2 th× ta t×m ®Õn

®Ønh Q' lµ anh em liÒn kÒ cña ®Ønh Q. NÕu Q' cã nhiÒu h¬n  m/2 con th× ta

con. Khi ®ã c¸c chØ sè cña Q hoÆc Q' cã thÓ thay ®æi. Ta l¹i ph¶i t×m ®Õn c¸c

NÕu Q' cã ®óng  m/2 con, th× ta kÕt hîp hai ®Ønh Q vµ Q' thµnh mét

chuyÓn sang ®Ønh cßn l¹i. §iÒu nµy dÉn ®Õn cÇn lo¹i bá chØ sè cña ®Ønh bÞ lo¹i

ra khái cha cña Q. Sù lo¹i bá nµy ®-îc thùc hiÖn b»ng c¸ch ¸p dông thñ tôc

lo¹i bá ®· tr×nh bµy.

h×nh 7.4. §Çu tiªn t×m l¸ chøa kho¸ 58, ®ã lµ khèi B₈. Xo¸ b¶n ghi 58, khèi B₈

thµnh rçng. T×m ®Õn cha cña B₈lµ B₁₃. Lo¹i bá chØ sè cña B₈khái B₁₃, B₁₃chØ

®Õn em liÒn kÒ cña B₁₃lµ B₄, sè con cña B₄lµ hai. KÕt hîp hai ®Ønh nµy thµnh

mét ®Ønh B₁₃. CÇn ph¶i lo¹i bá chØ sè cña khèi B₄khái B₁₄. B₁₄trë thµnh chØ cã

mét con. T×m ®Õn anh liÒn kÒ cña B₁₄lµ B₁. Sè con cña B₁lµ hai. KÕt hîp B₁vµ

10