Bài giảng B-Tree

Bài giảng B-Tree được biên soạn nhằm giúp cho các bạn biết cách để xóa một khóa ra khỏi một B-cây. Mời các bạn tham khảo bài giảng để nắm bắt nội dung chi tiết. Với các bạn chuyên ngành Công nghệ thông tin thì đây là tài liệu hữu ích.
Nội dung trích xuất từ tài liệu:
Bài giảng B-TreeB-Tree 1 Xoùa moät khoùa khoûi moät B-caâyThuû tuïc B-TREE-DELETE(x, k) ñeå xoùa khoùa k khoûi caây con coù goác taïix baûo ñaûm raèng khi B-TREE-DELETE ñöôïc goïi ñeä quy leân x thì — soá khoùa trong x phaûi  t (baäc toái thieåu cuûa caây).Do ñoù, khi thuû tuïc thöïc thi, ñoâi khi moät khoùa ñöôïc di chuyeån (töømoät nuùt thích hôïp khaùc) vaøo moät nuùt tröôùc khi ñeä quy xuoáng nuùt ñoù. 2 Xoùa moät khoùa khoûi moät B-caâyB-TREE-DELETE(x, k)1. Neáu khoùa k coù trong nuùt x vaø x laø moät nuùt laù thì xoùa k khoûi x, rồi tái cân bằng (phần sau).2. Neáu khoùa k coù trong nuùt x vaø x laø moät nuùt trong thì a. Neáu nuùt con y ôû tröôùc k coù ít nhaát t khoùa thì tìm khoùa tröôùc (predecessor) k’ cuûa k trong caây con coù goác taïi y. Xoùa k’, trong nuùt x thay k baèng k’. (Tìm vaø xoùa k’ coù theå thöïc thi trong moät löôït ñi xuoáng duy nhaát.) x  k  y … caây con coù goác taïi y 3 Xoùa moät khoùa khoûi moät B-caâyB-TREE-DELETE(x, k)1. ...2. Neáu khoùa k coù trong nuùt x vaø x laø moät nuùt trong thì a. ... b. Töông töï, neáu nuùt con z ôû sau k coù ít nhaát t khoùa thì tìm khoùa sau (successor) k’ cuûa k trong caây con coù goác taïi z. Xoùa k’, trong x thay k baèng k’. (Tìm vaø xoùa k’ coù theå thöïc thi trong moät löôït ñi xuoáng duy nhaát.) x  k  z … caây con coù goác taïi z 4 Xoùa moät khoùa khoûi moät B-caâyB-TREE-DELETE(x, k)1. ...2. Neáu khoùa k coù trong nuùt x vaø x laø moät nuùt trong thì a. ... b. ... c. Neáu khoâng, caû y laån z ñeàu chæ coù t  1 khoùa, hôïp nhaát k vaø nguyeân caû z vaøo y, thaønh ra x maát k vaø con troû ñeán z , vaø baây giôø y chöùa 2t  1 khoùa. Giaûi phoùng (free) z vaø goïi ñeä quy B-TREE-DELETE(y, k) ñeå xoùa k khoûi caây con coù goác y. x  k  y  k’ z l’  5 Xoùa moät khoùa khoûi moät B-caây(tieáp)Minh họa bước hợp nhất x  k  y  k’ z l’  x   y  k’ k l’  z 6 Xoùa moät khoùa khoûi moät B-caâyB-TREE-DELETE(x, k)1. ...2. ...3. Neáu khoùa k khoâng coù trong nuùt trong x thì xaùc ñònh goác ci[x] cuûacaây con chöùa k, neáu k coù trong caây. Neáu ci [x] chæ coù t  1 khoùa, thöïcthi böôùc 3a hay 3b neáu caàn (ñeå ñaûm baûo raèng giaûi thuaät, khi ñöôïc goïiñeä quy, seõ xuoáng moät nuùt chöùa ít nhaát t khoùa). Xong roài goïi B-TREE-DELETE leân nuùt con thích hôïp cuûa x. 7 Xoùa moät khoùa khoûi moät B-caây(tieáp)3. ... a. Neáu ci [x] chæ coù t  1 khoùa, nhöng laïi coù moät nuùt anh em beân phaûi (hay beân traùi) vôùi ít nhaát t khoùa, thì cho nuùt ci [x] theâm moät khoùa baèng caùch ñem moät khoùa töø x xuoáng ci [x], ñem moät khoùa töø nuùt anh em cuûa ci [x] leân x, vaø ñem con troû töông öùng töø nuùt anh em vaøo nuùt ci [x]. x  m  ci [x] nuùt anh em beân phaûi  l n n’  8 Xoùa moät khoùa khoûi moät B-caây(tieáp)Minh hoïa x  m  ci [x]  l n n’  x  n  ci [x]  l m n’  9 Xoùa moät khoùa khoûi moät B-caây(tieáp)3. ... a. ... b. Neáu ci [x] vaø moïi nuùt anh em cuûa noù chæ coù t  1 khoùa, thì hôïp nhaát ci [x] vaø moät nuùt anh em baèng caùch ñem moät khoùa töø x xuoáng nuùt môùi taïo, khoùa naøy seõ laø khoùa giöõa cuûa nuùt. x  l l’  ci [x] h m  m’ n  10 Xoùa moät khoùa khoûi moät B-caây(tieáp)Minh hoïa x  l l’  ci [x] h m  m’ n  x  l’  h l m  m’ n  11 Xoùa moät khoùa khoûi moät B-caây(tieáp)Thuû tuïc B-TREE-DELETE caàn— soá truy caäp leân ñóa laø O(h) vì coù O(1) laàn goïi DISK-READ vaø DISK-WRITE giöõa caùc goïi ñeä quy cuûa thuû tuïc.— thôøi gian CPU cuûa thuû tuïc laø O(t h) = O(t log t n). 12 Ví duï cho caùc tröôøng hôïp khi xoùa moät khoùa khoûi moät B-caây ...