Лекция №11. Работа с внешней памятью (файлами). Предмет "Структуры и алгоритмы обработки данных"

  • Published on
    13-Dec-2014

  • View
    659

  • Download
    0

Embed Size (px)

DESCRIPTION

 

Transcript

<ul><li> 1. . .. : (). , www.grebenshikov.ru </li></ul> <p> 2. - . . 5 . .1 3. 2 4. : - . - r1, . . . , rk , ri ri+1, 1 i k r1, . . . , rm k, i 0, k i m rk(i1)+1, rk(i1)+2, . . . , rki 3 5. 3 2 5 7 78 98 101 2 3 4 3 674 6. 5 7. merge(F 1, F 2, G1, G2, k)1 outswitch true G12 while not eof(F 1) or not eof(F 2)3do used[1] 0; used[2] 0; f in[1] f alse; f in[2] f alse;4cur[1] get(1, f 1, f 2); cur[2] get(2, f 1, f 2);5while not f in[1] or not f in[2]6 do if f in[1]7 then winner 28else if f in[2]9 then winner 1 10else if cur[1].key &lt; cur[2].key 11 else winner 2 12if outswitch 13 then write(g1, cur[winner]) 14 else write(g2, cur[winner]) 6 15cur[winner] = getRecord(winner) 16outswitch = not outswitch 8. merge-sort(F, N ) 1 k 1; switch 0 2 while k &lt; 2 N 3do if switch = 0 4 then F 1 F [0, 0]; F 2 F [0, 1]; 5G1 F [1, 0]; G2 F [1, 1]; 6 else F 1 F [1, 0]; F 2 F [1, 1]; 7G1 F [0, 0]; G2 F [0, 1]; 8merge(F 1, F 2, G1, G2, k) 9k k2 7 9. C(N ) = M (N )Tmerge(N ) = (N )Tmergesort(N ) = (N ) (logN ) = (N logN ) 8 10. . 6- 4- . 9 11. : 10 12. B- - , - (, ). : 11 13. B-12 14. B- T root[T ], - : x : n[x] - ; key1[x] . . . keyn[x][x] ; - leaf [x] true, x - . c1[x], c2[x], . . . , cn[x]+1[x] . h. t 2 - B-. - n[x] t 1. - n[x] 2t 113 15. B- T n 1 t 2 logt(n + 1)/2.hth 1 n 1 + (t 1) 2ti1 = 1 + 2(t 1)= 2th 1 i=1 t1 th (n + 1)/2 h logt(n + 1)/2 14 16. B- B Tree Search(x, k) 1 i1 2 while i n[x] k &gt; keyi[x] 3 do i i + 1 4 if i n[x] k = keyi[x] 5 then return(x, i) 6 if leaf [x] 7 then returnN IL 8 else Disk Read(ci[x]) 9 return B Tree Search(ci[x], k)15 17. O(h) = O(logtn) : n[x] &lt; 2t T (n) = O(th) = O(t logtn) 16 18. B- B Tree Create(T ) 1 x Allocate Node() 2 leaf [x] true 3 n[x] 0 4 Disk Write(x) 5 root[T ] xOPdisk = O(1) T (n) = O(1) 17 19. B-18 20. B- 19 21. B-20 22. B- 21 23. B-22 24. B-23 25. B-: OPdisk = O(1) T (n) = O(t): OPdisk = O(h) = O(logtn) T (n) = O(th) = O(t logtn) 24 26. B-. B+ . B- . 25 27. ., ., . . - . : , 2000..311-338. ., ., ., . -: , 2- . - . : - , 2007. .515-536. http://en.wikipedia.org/wiki/B-tree http://en.wikipedia.org/wiki/B%2B tree26 </p>

Recommended

View more >