3. () , - , , . , , , - . copy, 1.3: . , , . , - , - . , , , - . , - . , , , . - , - . , - . - , - , (*) , - . 2.1 , - (- ). - - . , , , . - , , , , , . - , , - , . - , . , - . ----------------------------------------- (*) , - , . 39 3.1  - , . : - , , , - , . - , "" , - , . , , . - ; , , , . . , , , , , . , , , A B. A, B, B, . , , , , - . ( 3.1) " " " ", - . - - +------------------+ | | +------------------+ | | +------------------+ +-------------> | | | +------------------+ | - | ------+---+ <-------------+ +------------------+ | | ------+-----------------> | +------------------+ +---+------ | +------------------+ - | ------+---+ +------------------+ | <-----------------+------ | | +------------------+ +-------------> 3.1. (. 2.2.1), (). - , , , . - : * ( " ()" "" - 40 , , "" ""), * , * , - ; , ", ", * , * . , , ( ), - . 3.2 ( ) , , : +----------------------------------------------------------------+ | | | +-------------------+ +-------+ +-------+ +-------+ | +->| |--->| |--->| |--->| |--+ +--| |<---| 1 |<---| 2 |<---| n |<-+ | +-------------------+ +-------+ +-------+ +-------+ | | | +----------------------------------------------------------------+ +----------------------------------------------------------------+ | | | +-------------------+ +-------+ +-------+ | +->| |---------------->| |--->| |--+ +--| |<----------------| 2 |<---| n |<-+ | +-------------------+ +-------+ +-------+ | | | +----------------------------------------------------------------+ 3.2. , - . , . - ( 3.2). . , "" , , . , . , , "" ( - ), . "" ( 3.2). , , "" , , , - "" . , - . , - , , 41 . - - , - . - , . - , -, , . - - . - +-----------------+ | | +----+ +----+ +----+ <----| 0 4 |------| 28 |-----| 4 |-----| 64 |----> | | +----+ +----+ +----+ +-----------------+ | | +----+ +----+ +----+ <----| 1 4 |------| 17 |-----| 5 |-----| 97 |----> | | +----+ +----+ +----+ +-----------------+ | | +----+ +----+ +----+ <----| 2 4 |------| 98 |-----| 50 |-----| 10 |----> | | +----+ +----+ +----+ +-----------------+ | | +----+ +----+ +----+ <----| 3 4 |------| 3 |-----| 35 |-----| 99 |----> | | +----+ +----+ +----+ +-----------------+ 3.3. - 3.3 -: - , - -. , 28, 4 64 - " 0 4". -; , . , - - ; - . -, . , - ; - . , , "". - , . -, , , . , - , - . : -, , . 42 3.3  2.1, , - , - . - , . , , , - , 4. - , , - , , - . , , , , . getblk ( 3.4). getblk . 1. -, - . 2. -, - . 3. - , ( 2), , " ". - . 4. -, - . 5. -, . . , -, . -, , ( ) . - , , "- " , (**) . , - . - , , - , . 3.5 , 4 -, " 0 4". , , 5 28 . ---------------------------------------- (**) , - , . , "- " , . , - , ; - "", . 43 +------------------------------------------------------------------+ | getblk | | : | | : , | | { ( ) | | { ( -) | | { ( ) /* 5 */ | | { | | ( ); | | ; /* */ | | } | | ; /* 1 */ | | ; | | ; | | } | | /* - */ | | { | | ( ) /* 4*/ | | { | | ( ); | | ; /* */ | | } | | ; | | ( ) | | /* 3 */ | | { | | ; | | ; /* */ | | } | | /* 2 -- */ | | -; | | -; | | ; | | } | | } | | } | +------------------------------------------------------------------+ 3.4. - +-----------------+ +-----------------+ | | |+----+ +----+| +----+ | 0 4 |---- ++ 28 ++ ++ 4 ++ | 64 | +-----------------+ +----+| +------+ +----+ | | +----+| +----+| +----+ | 1 4 |---- | 17 || ++ 5 ++ ++ 97 ++ | | +----+| |+----+ +-++----+| +-----------------+ +---|--------+ +------+ | | +----+ |+----+ |+----+ | 2 4 |---- | 98 |+---+| 50 | ++ 10 ++ +-----------------+ +----+| +----+ +----+| | | +----+| +----+ +----+| | 3 4 |----+>| 3 ++ | 35 | | 99 || +-----------------+ | +----+ +----+ +----+| +-----------------+ | | | +----+ | | |<---------------------------------+ +-----------------+ () 4 - 44 - +-----------------+ +--------------+ | | +----+| +----+ |+----+ | 0 4 |---- ++ 28 ++ | 4 | || 64 | | | |+----+ +----+ |+----+ +-----------------+ +-----------------+ | | | +----+ +----+| |+----+ | 1 4 |---- | 17 | ++ 5 ++ ++ 97 ++ | | +----+ |+----+ +----+| +-----------------+ | +------+ | | +----+ |+----+ |+----+ | 2 4 |---- | 98 |+---+| 50 | ++ 10 ++ | | +----+| +----+ +----+| +-----------------+ | | | | +----+| +----+ +----+| | 3 4 |----+>| 3 ++ | 35 | | 99 || | | | +----+ +----+ +----+| +-----------------+ | | +-----------------+ | | | +----+ | | | | | |<---------------------------------+ +-----------------+ () 4 3.5. - 1: - +------------------------------------------------------------+ | brelse | | : | | : | | { | | | | , ; | | | | , ; | | , | | ; | | ( ) | | | | | | | | , | | ; | | (); | | } | +------------------------------------------------------------+ 3.6. , , , , . . ""; - 45 , , . - , - brelse ( 3.6). , - , , , - , . , , , , , , (. 2.2.2.4). - , - "" - , ; . . brelse , , , - (. 3.4). , - - , - brelse. , brelse - getblk, getblk. . getblk 2, - -, , - . -, - "" - +-----------------+ +-----------------+ | | |+----+ +----+| +----+ | 0 4 |---- ++ 28 ++ ++ 4 ++ | 64 | | | +----+| |+----+ +----+ +-----------------+ | +------+ | | +----+| +----+| +----+ | 1 4 |---- | 17 || ++ 5 ++ ++ 97 ++ | | +----+| |+----+ +-++----+| +-----------------+ +---|--------+ +------+ | | +----+ |+----+ |+----+ | 2 4 |---- | 98 |+---+| 50 | ++ 10 ++ | | +----+| +----+ +----+| +-----------------+ | | | | +----+| +----+ +----+| | 3 4 |----+>| 3 ++ | 35 | | 99 || | | | +----+ +----+ +----+| +-----------------+ | | +-----------------+ | | | +----+ | | | | | |<---------------------------------+ +-----------------+ () 18 - 46 - +-----------------+ +-----------------+ | | |+----+ +----+| +----+ | 0 4 |---- ++ 28 ++ ++ 4 ++ | 64 | | | +----+| |+----+ +----+ +-----------------+ | +------+ | | +----+| +----+| +----+ | 1 4 |---- | 17 || +->| 5 ++ ++ 97 ++ | | +----+| | +----+ +-++----+| +-----------------+ +-|----------+ +------+ | | +----+ | +----+ |+----+ +----+ | 2 4 |---- | 98 | | | 50 | ++ 10 ++ | 18 | | | +----+ | +----+ +----+| +----+ +-----------------+ | | | | | +----+ +----+| | 3 4 |---- | | 35 | | 99 || +-----------------+ | +----+ +----+| +-----------------+ | | | +--------------+ | | |<---------------------------------+ +-----------------+ () , 18 3.7. , , . ; -. , , -- , , - , , -. , , . , - , - . , . 3.7, - , 18, -, " 2 4". - ( 3), 18 -. getblk 3, . , , , . - . , - . . , " " , - , . , 3.8, 18, ( ) , , . , - , , 4. " " " " , " 18", -- . 47 ( 3.9) , A, - - , 2. , , A , brelse, - . A, - - . , , - , A. - , , . 3.10 . ( 3.11) , . , , A, , . - , A - , 2, - . , A , , B, , A. B ( 5) -- . , , , B "" , A . A , . A "" , " ", B. B, B , - - +-----------------+ +-----------------+ | | |+----+ +----+| +----+ | 0 4 |---- ++ 28 ++ ++ 4 ++ | 64 | | | +----+| |+----+ +----+ +-----------------+ | +------+ | | +----+| +----+| +----+ | 1 4 |---- | 17 || +-+ 5 ++ ++ 97 ++ | | +----+| | +----+ +-++----+| +-----------------+ +--|-+ +------+ | | +----+ | +----+ |+----+ | 2 4 |---- | 98 |+--+ | 50 | ++ 10 ++ | | +----+| +----+ +----+| +-----------------+ | | | | +----+| +----+ +----+| | 3 4 |----+>| 3 ++ | 35 | | 99 || | | | +----+ +----+ +----+| +-----------------+ | | +-----------------+ | | | +----+ | | | | | |<---------------------------------+ +-----------------+ () 18 48 - +-----------------+ | | +----+ +----+ | 0 4 |----+>| 28 +------------+ | 64 | | | | +----+ | +----+ +-----------------+ | | | | | +----+ +----+ | +----+ | 1 4 |----| | 17 | | 5 | +-->| 97 ++ | | | +----+ +----+ +----+| +-----------------+ | +------+ | | | +----+ +----+ |+----+ +----+ | 2 4 |----| | 98 | | 50 | ++ 10 ++ | 18 | | | | +----+ +----+ +----+| +----+ +-----------------+ | | | | | +----+ +----+ +----+| | 3 4 |----| | 3 | | 35 | | 99 || | | | +----+ +----+ +----+| +-----------------+ | | +-----------------+ | | | +----+ | | | | | |<---------------------------------+ +-----------------+ () 3 5, 4 18 3.8. - +-----------------+ | | +----+ +----+ +----+ | 0 4 |---- | 28 | | 4 | | 64 | | | +----+ +----+ +----+ +-----------------+ | | +----+ +----+ +----+ | 1 4 |---- | 17 | | 5 | | 97 | | | +----+ +----+ +----+ +-----------------+ | | +----+ +----+ +----+ | 2 4 |---- | 98 | | 50 | | 10 | | | +----+ +----+ +----+ +-----------------+ | | +----+ +----+ +----+ | 3 4 |---- | 3 | | 35 | | 99 | | | +----+ +----+ +----+ +-----------------+ +-----------------+ | +---------+ | | | | |<--------+ +-----------------+ 18, 3.9. . , , C, , 49 C B; C . , B , . B , - , C , 2. B - , , - B . - , , - . A B +------------------------------------------------------------- | b - | - - | - | - - | - | - | - | - b | - - | - | - - | - | - | - | - - | +------------------------------------------------------+ | | : brelse | | +------------------------------------------------------+ | - | - | - | - | - b | - v 3.10. , B , - , 2. - , 99 ( 3.11), -, . - , - . 3.12 . ; "- " . , , , - , ,