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.
Nội dung trích xuất từ tài liệu:
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 ®Ó 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×mkiÕ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 ®Òulµ 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¸ytÝnh hiÖn nay ®Òu ®îc trang bÞ c¸c thiÕt bÞ bé nhí ngoµi, th«ng thênglµ ®Ü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ªnc¸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¸chÖ ®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¸cphÐ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øcd÷ 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 ghicã ®é 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îpnµ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¶nghi kh¸c nhau ph¶i cã c¸c gi¸ trÞ kh¸c nhau trªn Ýt nhÊt mét trêng thuéckho¸. 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. 1722. Xen vµo : xen vµo file mét b¶n ghi nµo ®ã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ªns¶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 ghiví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 thaygi¸ 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ý (physicalblock) 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õ 29 byte ®Õn 212 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 ®Çutiªn cña khèi. File ®îc lu gi÷ trong mét sè khèi, mçi khèi cã thÓ lu gi÷ mét sè b¶nghi cña file. Trong mét khèi cã thÓ cßn mét sè byte cha ®î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¶nghi). File cã thÓ ®îc lu gi÷ trong mét danh s¸ch liªn kÕt c¸c khèi. §iÓnh×nh h¬n, file cã thÓ ®îc lu gi÷ trong c¸c khèi tæ chøc díi d¹ng c©y. C¸ckhè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 ®Ó ghisè b¶n ghi trong khèi. Trong mét khèi, kh«ng gian ®Ó lu tr÷ mét b¶n ghi ®îc gäi lµ khèicon. 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µ ®ÇyhoÆ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étc¸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) ®îcthùc hiÖn th«ng qua phÐp to¸n c¬ b¶n, ®äc mét khèi d÷ liÖu ë ...