Bài giảng Phân tích thiết kế giải thuật: Chương 4 - ĐH Bách khoa

Bài giảng Phân tích thiết kế giải thuật: Chương 4 - B-Cây bao gồm những nội dung về cấu trúc dữ liệu trong bộ nhớ ngoài; truy cập đĩa; các thao tác lên một đĩa; hệ số phân nhánh; định nghĩa của B-cây; các thao tác lên một B-cây và một số nội dung khác.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế giải thuật: Chương 4 - ĐH Bách khoa BCây23.2.2004 Ch.4:BTrees 1 Cấutrúcdữliệutrongbộnhớngoài° Bcâytổngquáthoácâytìmkiếmnhịphân. – “Hệsốphânnhánh”(branchingfactor)° Bcâylàcâytìmkiếmcânbằngđượcthiếtkếđểlàmviệchữuhiệu trongbộnhớngoài(đĩacứng). – Bộnhớchính(mainmemory) – Bộnhớngoài(secondarystorage) ° Disk – Track – Page° Thờigianchạygồm – sốcáctruycậpvàođĩa – thờigianCPU23.2.2004 Ch.4:BTrees 2 Truycậpđĩa° MộtnútcủaBcâythườngchiếmnguyêncảmộtdiskpage.° Hệsốphânnhánhtùythuộcvàotỉlệgiữakíchthướccủakhóavà kíchthướccủadiskpage.23.2.2004 Ch.4:BTrees 3 Cácthaotáclênmộtđĩa° Choxlàmộtcontrỏđếnmộtđốitượng(vídụ:mộtnútcủamộtB cây).Đốitượngxcóthểcónhiềutrường – Nếuxnằmtrongbộnhớchính,truycậpcáctrườngcủaxnhư thườnglệ,vídụnhưkey[x],leaf[x],... – NếuxcònnằmtrênđĩathìdùngDISKREAD(x)đểđọcnóvàobộ nhớchính. – NếuxđãthayđổithìdùngDISKWRITE(x)đểtrữnóvàođĩa.° Cáchlàmviệctiêubiểuvớimộtđốitượngx ... x mộtcontrỏđếnmộtđốitượngnàođó DISKREAD(x) cácthaotáctruycập/thayđổicáctrườngcủax DISKWRITE(x) cácthaotáckhôngthayđổimộttrườngcủax ...23.2.2004 Ch.4:BTrees 4 Hệsốphânnhánh° VídụmộtBcâymà: – mỗinútcó1000khóa(sốtrongmỗinútlàsốkhóanóchứa),tức làBcâycóhệsốphânnhánhlà1001 root[T] 1nút 1000 1000khóa 1001 1001nút 1000 1000 1000 1.001.000khóa 1001 1001 1001 1.002.001nút 1000 1000 1000 1.002.001.000khóa23.2.2004 Ch.4:BTrees 5 ĐịnhnghĩacủaBcâyMộtBcâyTlàmộtcâycógốc,màgốclàroot[T],cócáctínhchấtsau° Mỗinútxcócáctrườngsau – n[x],sốlượngkhóađangđượcchứatrongnútx – cáckhóa:cón[x]khóa,đượcxếptheothứtựkhônggiảm,tứclà key1[x] key2[x] keyn[x][x] – leaf[x],cótrịboollà TRUEnếuxlàmộtlá FALSEnếuxlàmộtnúttrong ° Mỗinúttrongxchứan[x] 1contrỏc1[x],c2[x],…,cn[x]+1[x]đến cácnútconcủanó.23.2.2004 Ch.4:BTrees 6 ĐịnhnghĩacủaBcây(tiếp)° Nếukilàkhóatrữtrongcâyconcógốclàci[x]thì • k1 key1[x] k2 key2[x] kn[x] keyn[x][x] kn[x]+1° Tấtcảcáclácócùngmộtđộsâu,đólàchiềucaohcủacây° Cómộtsốnguyênt 2gọilàbậctốithiểucủacâysaocho – Mọinútkhôngphảilànútgốcphảicóítnhấtt 1khóa.Nếu câykhôngtrốngthìnútgốcphảicóítnhấtmộtkhóa. – Mổinútcóthểchứatốiđa2t 1khóa.Mộtnútlàđầynếunó chứađúng2t 1khóa.23.2.2004 Ch.4:BTrees 7 ChiềucaocủamộtBcâyĐịnhlýNếun 1thìmọiBcâyTvớinkhóa,chiềucaoh,vàbậctốithiểut 2 n 1có h log t 2ChứngminhCótốithiểu2nútởđộsâu1,2tnútởđộsâu2,...,và2th1nútởđộ sâuh.Vậysốkhóatốithi h ểulà n 1 (t 1) 2t i 1 i 1 th 1 1 2(t 1) t 1 2t h 1 n 1 th 2 Dođó,từđâysuyrađịnhlý.23.2.2004 Ch.4:BTrees 8 SốkhóatốithiểutrongmộtBcây°Bcâysaochomọinútđềucót 1khóa,ngoạitrừnútgốcchỉcó1khóa. ...