     

       ,        
 .        
        .  
        
        ,   
  DB2  IBM. ,  ,  ,  
     (..  ,    
 ). 

      

         

    .1.  

            
     ,   . (  
         
, ..         
,     ,    
.) ,         
 ,   ,  , ,  ( 
),  /  ..     
    ,  [.4].	* 
             
   .       
            
 10 ,     ()    
 5 10  /.        
  -  ,      , 
     .    
      - 
.      ,   
  , ..        
   -,      . 
      ,   ()    
  .      
,        
 .      , 
      .   ,  , 
          
  .  ,     
         . 
          .     
 (.2)         , 
     ,    
. (,       ,  
      , 
     , .. ,   ..)  
  (.)      (file 
manager)    (disk manager).     .2  
.  ,         
  .   .4-.7   
,            
       : 
, ,     . ,  
 .8   . 

    674	 


    .          
  ,     .    
         
    .     
       ,    
   . 


    .2.    :  

         ,    
      .     
        . 
,           
,           
   (. ). 
    1.      ,      
  . (    , 
          .    
           
        . ,  
, ,        
   .) 
    2.     ,     
,         . 

       
       
      / 
       
       
        

    . .1.         ,      
  


       

    3.   ,       
        - . 
. ,         
       . 
,            
 . 
     ,          , 
      .   ,  
         ,  
     . ,   
     .     
 . 

      

          ,  
      - (  
       -). 

     .      675 

             
 . ,       , 
      ,    
    .  ""  , .. 
 ,     .   
        
  (..  ""   )  
    .  ,   
,        
,      .   
          . 
 (  )      
 ,     ,   
  ,     ,     
  ,    ,   
 . 
       ,       
.    ,   ,    
 ,         
 (        
).     /    
     .    
,      , .. ,  
       , 
        /?    s, 
        /?    5. 
            s (..    
          ). 
            5 (..     
     ). 
          -   
,           
 . 

      

            (    
 1,      )   
         
 .           
 . 

    .            
 ,          
 . ,   ,    
             
   . 

         (file name)    
(file ID),     .    ,  
 ,     (record number  
record ID), ,   ,     . 
(           
,     .   ,       
     ,    
.    .) 

    676	 

         ,   
, .. ,        . 
    	      / 
    	      / 
    	       / 
    	      / 
    	   / 
    	  / 
                
    (    ). 

    .        
 ,        .   
       .    
,   ,     , 
     ,  
 ,  .     
  [.44]. 

     

            
 .          
          
 .       
  ,     
. ,       rl 
 pi,          2 
 2.     : 
    1.   !  2 ,      2  
      -,  
       . 
    2.     !  2  ,    
 ,   ,      2 
      - (, 
,  2      ). ,  
 /        
 ,     .    !  2 
   ,      . 
              
    . (      
  ,      
         - 
       ,   
  .) 
                 
    ,      
    ,     S1  
  S2,  S2    S3  ..    
,        . 
         ,         
         ,    
      . ,  

     .     	677 

   S1       
   S1,      S2   
     S2  ..    , 
    . 
    ,          
      . 
          , 
       (  )  
   (  ).      
     ,    .     
  ,         
""   , ..    ,   ,  
  .   ,    
,         
 .    . 
    ,        ,  
    .     
        
 .         
           
,    .  ,  
    ,     
        . 

    ..     

      ,       
        -  
   ""  -.   
    .    
  . 
    ,          
        . 
( ,   " "    , 
     . ,     
          , 
 - .)    ,     
   ,      ,  
     65 536 = 64  (     
,      ).    
   . 
    1.         .    
  ,      ,   
 "",     .    
 ,    "". 
    2.           
         S1-S5.   
    1-5        
 "  ". 
    3.            
 .       :   
( 1 5),   ( 6-11),   ( 12-23)  
   ( 24,25,26  ..).   
   . .2. 

    678	 

        . 
    4.  ,         
 S6.        ,  
       (   
  24),        . 

    -OJ	JJ S1	JJ S2	JJ S3	 S4	_LJ S5 
    _ej PI	JJ 2	JJ 	JJ 4	 5	LJ 6 
    J2J S1/P1	J3J S1/P2	 S1/P3	J5J S1/P4	16J S1/P5	1LJ S1/P6 
     S2/P1	19J S2/P2	20J S3/P2	 S4/P2	22J S4/P4	23J S4/P5 
    24J	_25J	26J	27J	28J	29J 
    ^^		__	-~~~^~ 	 -  	_^-J 
    _-  ^              \ 

    . .2.          
       

    5.           S2, 
   ,       
S2 ( 2)    . 
    6.            
( 7),    ,      
      ( 2)      
  . 
    7.            S4, 
   ,       
S4 ( 4)    . 
            
. ..   ,     ,   
      ,  
        . 
         
  ,          
.           
   ,      
 (. .4). 
         . 
        ,    " ", 
         . 
         ,     
      (,   ). 
            
,      ,   ( 
 ;     ),   64 
 . 

     .      679 


    .OJ	JJ S1	-U P7	JJ S3	JJ	_5J S5 
    jU PI	JJ P2	JJ P3	_aj P4	IflJ PS	1U P6 
    J2J S1/P1	JU S1/P2	L14J S1/P3	1LJ S1/P4	ULU S1/P5	JLJ S1/P6 
    Jll S2/P1	J9J S2/P2	JOJ S3/P2	2JJ S4/P2	22J S4/P4	23J S4/P5 
    24J S6	Jll	J6J	1LJ	28J	29J 
    J||?>---  I			k--i_^- 		u^^ I 
    
    
    . .,          

    _OJ 
        7     si    i_a_-LJ    I  I    in 111 
    1 
    181       9. S2/P1 
    24J       IX 251 
    S6 
    2 
     
    4 
    5 
    U 6 
    29[     

    . .4.    ,   . .,  
 " "       

        ,        
   , ,     
  ? (      
 ,          
    .)      
 ,      .  , 
,      ,  , 
      0 ( "").   
           
      (. .5). 
           
-          
   .        
  -         
        .  , 
  ,    .  
        . 
     (    ),    
    ,    ,   
 .       
, ..   .     
  . 

    680  

    1.       S1-S5     
/? ,    . .6.  ,     
   . 

    0			X 
    
    
     	    
     	4 
    	1 
    	6 
    	12 
    
    
    P		(  ) 
    S1	Smith		20	London	S2 Jones    10   Paris 
    S3	Blake		30	Paris	S4   Clark    20  London 
    S5	Adams		30	Athens 
    
    
    . .5.   ( 0) 

    . .6.          
     S1-S5 

    2.  ,      ,   
  S9.         
(     )     S5. 
    3.     ,       
S2.     S2    ,   
     S1  S3, ""  
S3, S4, S5  S9. 
    4.            S7, 
        (    
 )    S5,    S9,   
.       . .7. 

    . .7.         S9, 
  S2    S7 

       ,    
        
,    .     
      ,     
          
. (       
      ,  
     .) 

    		(  ) 
    S1	Smith		20	London	S3	Blake	20	Paris 
    S4	Clark		20	London	S5	Adams	10	Athens 
    S7					S9			.... 
    
    
     .      681 

      ,      
   (record ID  RID),  . .8  
   .       
     ,     ,   
     , ,   ,   
      .      
      . 
,         ,  
  . .7  .8,      
(       ).   , 
    ,     
  ,       
, (,       
,         
   ,   .     
         
     .) 

      
          ;   i     

    . .8,     (record ID  RID) 

    .          
    (  ) .    
   ,         
    .       
  ,      
     .     
         
 . 

           
    .     , 
         , 
   ,    .    
   ,      . 
                
         
,    " "  " 
       
   " (    
  ).    
,   ,      
    .     
      . 

    682  

       ,        
  ,      
      (..   ).   
,      ,    
     (   ). 
       ,      
     .      
 (    ,     ). 
  ,      
.      ,    
    "  ". 
             ,    
"" ()     
  ,     . , 
       ,   
  , ,     
 ,    ,  
  -      , 
..   . 
                
     .    
   ,       
.         
   (        
 ),   (    ),  
 (   ,   ),  ( 
   )  .. ,      
     . 
       ,  ,       
     ..,     (  
 ),      .  , 
          
 :         
,            . 
          ""   
, ..  ,     
      . ,   
    , ,  
,    .   ,    
     . ,   
          
      ,    
          . 

    .4.  

            ,   
        "   
  ",     .      
     ,    . 
.9.      :        
   

     .     	683 

    ;       . 
,         
  , ..    CITY ()  RID-  
    . 

      () 
      () 
    V 
    S1	Smith	20	London 
    S2	Jones	10	Paris 
    S3	Blake	30	Paris 
    S4	Clark	20	London 
    S5	Adams	30	Athens 

    . ,9.      CITY   

      ,       
  . 
    1.     ,   ,    
   London (). 
    2.        London (),    
       . 
               
  ,      
.   , , -,    
     (    
        ).  
-,       ,   
     -,   
   ,     -  
 . 
             
     ,  ,   
 (  )     . 
       ,     
   ,     RID-.   
   ( )   ,    
      .  
     (index key),      
   . 

    .        , 
      "" ( )  
        " 
" (..   ).  ,   
,     CITY,    ,  
     ,    .   
 . 

    ,       , 
    S#  ,    . 
       ,   CITY,   
 ,    .  , , 
       ,  . 

    684  


       

          
     ,     
   . ,    
           
 .    ,    
  ,     ,  S2,    
  (. . .9).         
  ,      :  
    ? 
         ,    
     . 
          . -, 
        , 
    ",  
  ". ,  CITY    
         
 . -,        
        
 .   "   "  
    . 
             
 . 
        .      
    , : "   , 
       " (,   
 ).        : "  
 ,     ,   
 (    )"  "   , 
    ()   ". 
       .       
   ,  : "   , 
   " (,  ,   -). 
             , 
        . , 
   "    "   "", 
    CITY     . 
         : ,   
    CITY ()   STATUS () (. 
).    ,       
     .    
""     "   
   30".    CITY     
   RID- 2  ,    STATUS    
RID-   5,         
 ,          
 .           
     . 

     .     	685 

     CITY 
         
     STATUS 
    V 
    S1 
    S2 
    S3 
    S4 
    S5 
    Smith 
    Jones 
    Blake 
    Clark 
    Adams 
    20 
    10 
    30 
    20 
    30 
    London 
    Paris 
    Paris 
    London 
    Athens 
    10 
    20 
    20 
    30 
    30 

    , , 10,       CITY  STATUS 

    .     .   
,     (. . )    
      ,     
      .  ,   
       . 

         

              . 
,  . . 11       
   CITY  STATUS.       
   "      30"   
     .     
      CITY  STATUS,    
     .  ,  
        
    .   ,     
,         
 . 

     CITY /STATUS 
         
    S1	Smith	20	London 
    S2	Jones	10	Paris 
    S3	Blake	30	Paris 
    S4	Clark	20	London 
    S5	Adams	30	Athens 

    , A.11.        
CITY  STATUS 

     ,    CITY/STATUS   
     CITY,      
     . (   
   STATUS,    .) , 
     Fl, F2, F3,,.. Fn (  ) 
        F1,   
    F1F2 ( F2F]),    
   F1F2F3 (   )  ..  , 
 ,        
     (    
   ). 

    686  


        

         ,     
    , ,   
  -,     .  
     .     
,        
(RID-),           
(..  ). ,       
       .  
            
    -. 

    .         
   ,      
,   "". 

        ,  ,     
     ""    
        
     . ,  
      
,     ,   
.  ,         
(    ). ,    
   ;      
        (  
   ). ,  ,      
,          
  .      
. . 12,     ,       
   . 

     S# 
    
    """  *1	S1	Smith	20	London 
    S2	Jones	10	Paris 
    ^  + ^->	S3	Blake	30	Paris 
    S4	Clark	20	London 
    S5	Adams	30	Athens 
    
      - 1 
      
      + 1 

    . .12.     

           S3   
 .          , 
   S3.        S4,  
    .   ,   
         
(       ). 
          ( ), 
          . 
      . .12. (   

     .      687 

, ,  .)     
         ,   
    .     
     .      
       . 
     ,           
  ,     ()  
,   .       
 . 

      - 

             
 - (B-tree).      , 
   ,    ,     
      .    
        
,       ,  
       . 
          -,    
  ,     . 
         -   
       
    .   ,   
    ,       . 
         
 .       ,   : 
            
 .         
(   ,     
       ).  
            
  (    ,   
 ,          
,    +1,         
 ). 
      -       
      ()  - (McCreight)  1972  
[. 16].           
   .       
      .     
   ,   (Knuth) [A.I]. 
( ,         
  (Virtual Storage Access Method  VSAM),  
  IBM,   ,  .  
 VSAM        
,    .    
 VSAM     1969  [. 19].) 
      VSAM        : 
    . 
             
,    ,     ,   
      .   
   ,      

    688	 

,         
 ,        
      ..  ,   
       
  . 
        ,   ,    
    ( ,   ).  ,  
        
,  ,    -.   
       -- 
(B-plus tree  B+-tree).        
    (,   ), 
   (root). 
     . . 13     .  6, 8, 12, ... 
97, 99     F.    
   F (50  82)    ( ).   
  F,    50,       
;     F,  50     82,   
  ; ,     F,  82,  
   .      
  .  ,    
            
        F,  32   
  50. 
       - (..  ),   . . 13, 
    . 
       -,  -      
  . 
       -,  -     
 . 
    , "-  "        2   
      (  k    
k+1 ).  ,         
 .       
 V   -  ,   . . 13. 

    set N to the root ;	/*     */ do until N is a 
sequence-set node ;          /*   */ 
    /*   */ let X, Y (X < ) be the data values in node N ; 
    /*    */ if V< X then set N to the left lower node of 
N ; 
    I*  V < X,     */ if X < V < Y then set N to the 
middle lower node of N ; 
    /*  X < V < ,     */ if V >  then set N to 
the right lower node of N ; 
    I*  V > Y,     */ end ; 
    if V occurs in node N then exit	/*   */ if V does not occur 
in node N then exit    /*    */ 

           
       .   ,   
         
          . 
          
  ,      
     . 

     .     	689 


    .          
  (    )      
   ,       . 

         -  
     . (   
   , "B-tree",    
 ""  "" (balanced).)    
    V    -  .  
        ,    
          . 
                
(,    /V),      
 V.   /V   ,   V 
       . 
         (   , ..  
   )  N (,    2  
)      N1  N2.   S  
 2+1 ,   2       V. 
      ( )  
    N1,      N2,    
  W         . 
,     U    , 
      N1,  U<W,    
 N2,  U>W, 
               W  
       . 
             
         
 . 
           , 
    .       ,  
  . 

    .5.  

    , -  -   
          
 .    ,    .  
    . 
               
(RID-   ),      
-       , .. -, 
 -.     -  .  
  -. 
             -  
,          . 
             -   
  -,        
    . 

    690	 


    M50I.I82M 
      
     
    16 I 8 |12|   115118132|   1351401501   |51|52|58|   |60|62|70|   
|71|78|82|   |83|85|89|   |91|93|94|    (   III        III     
   III         III        III        III        III        III        III    
   
    ) 
    . .13.    - 
     |				Jj				Jj                              [Jj                           
  [J									. 
    S300	Blake	30	Paris	I									S200	Jones	10	Paris 
    				JJ				H	Jj				UJ				J 
    S500	Adams	30	Athens						S100	Smith	30	London	S400	Clark	20	London	I 
    N				I I 
    
    
    . .14.    


        ,       
     S100, S200, S300, S400, S500 ( SI, S2, 
S3, S4, S5),        ,  
  -  : 

    - (..  ) = 
        13 ,      S# 

         -  /. ( 
      ;   
     .)       
   9, 5, \, 10  6 .   
      . . 14. 
      ,      , 
       ,     
 ,  ,  -. (   
,    ,      
   .      [.24].) 
        ,     
,      - 
 .         
      (   
  ).     ,  
          
 .          
   SOOO-S999, ..     1000,    
      .  , 
        
 -,      000-999, ,  0-9. 
      ( 20%  
 ),  0-9      0-12. 
           .   
,         
     ,     
  . (  ,   
      .) 
       
           . 
    (,          
        
    .    , 
        
  [.35, .37].) 
           
, .. ,       ("") 
  . ,       
(  S100, S200  ..)      S1400.  
 -  "    13"   
(  9)   S100. ,   -    
    . 
             
     13    ,    
      .  ,  
     S1400 (,     
  S100-S500)     9,    
  .   

    692	 

    11.      
    .  ,    
    (    ), 
    . ,   
  ()    .     
       -     
           
 .     +1   
        
 ,       -. 
       ,     , 
    -      
-   ,   .      
    ( ),     
    ,      .  
        -  
  . 

      

             
      . ,   , 
       ,  
            
 .     ,  
 , ..       , 
  -. 
      [.28]      
. ,      
          (.., , 
    ),      
       . (    
   .) 

    .     ,  
  -  ,        
,  -  . 

            . 
    1.  ,    -   /?,  
        k.   
    k, ..   - 
h(k),       .  
     ,       
  .     . 
    2.        ,    
 .    ,   d,   
 ,   21       
  .  ,     d  
  ,  2J    . 
    3.     d   (..  d  
,     -   
 )      ,  /-   
 (1</<2'')    ,   ,  
    /1. 

     .     	693 

     ,        ,  
 b   ,       ,  
 b  0...01,  .. (    ,   
,   ,  ,    
  2J.) ,         
,  k,    -    s, 
   d      /1    
 (  ( )  )   /- 
  ,    (   ). 
.      ,     
         . 
    4.            
  (p<d). , ,  d     
        /,  
.      . . 15.   
  ,         
 000,      00 (, 000  001). 
 ,   001     . 

       


      000  001  010  011  
100  101  110  111 
    *	2 |   
     
     00 
     :     010 

    , . 15,     

    5.   ,          
 000 ( 001)     000.    
           
.   

    694  

 ( )       000,   
    000,     ( )  
     001,       001. 
    6.  ,      000  
         .  
,   ,      
  .       , .. 
           
.            
   0000       0001   
.  ,        
  ,        . 
             
,        
 .      , ,  [.29-.36]. 

    .6.   

        "    "  
        . 
     ,  .  . . 16 
          
. ,       (. . .9),  
       .    
  ,   .   
   ,       
-. 
       -     
   .   ( )   
    ,      
      ,    
     .  ,    
     ,       
          "London"  
 ,          . 
      -   
          
   .  , -  
    ,    , 
      .     
  . 
             -  
        
: 1-, 2-, ... (-1)-.       
,         
,        -    
 . 
                
"    ",      
 "   ",      
.         - 
,  -       
  .   , ,   

     .     	695 

,         . 
 -      
        . 
     ,       ,  
      . 
,          
    ,     
     . 
       -       
    ,       
 (..       
),         
      .     
      .     
       . 

    .         
  ,       [.24]. 

         - . 
             ,    .  
        
 -  . 
               
        . 
           
    "   " ( 
,         
  ). 
        ,           
  (     ).   
    ,    
"    S4",   .  
 ,         
 ,        
   . 
            ,    
  . ( ,    
.)  . . 17        
, ..    - .   
      (     . . 16),  
   ,         . 

    .7.   

         ,  
    .      
     ,      
- (, ,    ).   
,           
 -. ,   ,     
     ,   
   -   , 
    . 

    696	 


    			J                ^   ""'"""   IJI	S^T   |     r      ,,.,r  rnnonQB 
    /          
    J	( 
    '                                            ^ 
    r 
    lr 
    |S1  | Smith     20 |f|     | S2 | Jones   | 10 |f>| S3 | Blake   | 30 
|'				|S4	Clark	20 |l	i|     | S5    Adams | 30   4	1 |   
    [                 t 
    
    
    . .16.   -  


    ^    ^UUM     |   -   ,	S^**     "   i	.J 
    
    
    J 
    ^ 
    
    
    t=	^ 
    :				, , 
        | S1  | Smith   |  '	III     I S2  | Jones   |   ,	-f>| S3  | 
Blake   |   !	|4     | S4 ] Clark   |   |  |	| S5 | Adams |     | 
    t	1    I          1	\       I	==j 4-	._J 
    1	S   ]	\	i 
    ^	 1  -i_	X	      _4. 
    *~		i                                                    ^	s\ 
    r 1  *	'  !	   ~          |	^/ 
    1        1 L_J ,n 1   1   1	i   _ i L^Unl    1	 __ J" L^J  1    1 
    

    . . 17.      
-  


697	 


        ,      
        . , 
,           
   R,  ,       
   .   , ,      
    . 
           , 
          
 .  ,      
   ,     
    .     
 ,     ,    
  .  ,        
   .   ,      
       , 
        .   
        .  
 ,      ,   
   ,      ,  . 
              
   : 

    Roberton Robertson Robertstone Robinson 

    ,       12   
       (  )  
  .       
           
          .  
      : 

    	- Robertonf++-t 
    6	- son+++ 
    7	- tone+ 
    3	- inson+++^ 

    (      "",   
     ). 
          ,    
     .  ,     
          
 .      : 

     - 7 - Roberto 
    6 - 2 - so 
    7 - 1 - t 3 - 1 - i 

             
 ,      .  , 
       ,   
          
(    ): 

    Roberto????? Robertso???? Robertst???? Robi???????? 

        ,   -    
  ,       . 
    

    698	 


      

    ,        
 (..    )   
 F,       
()   . ,     
 ,      , 
       ,    
    ..          
           
 .         
 ,            
  ,    (. . 18). 

    Athens		S5	Adams	30 
    
    
    London		S1	Smith			1 S4      Clark    I 20 
    
    
    Paris		S2	Jones	*		1 S3      Blake    I 30 

    . . 18.      

      ,   . . 18,    
:      ,      
 . (        
,        .) 
         
  .  ,  ,   
,   . . 18,        
    , ,   ,   
   ,        ( 
        ). 
           ,   
         
  ,    . 
            
.           
. . ,       
     ,      
 , ..     S1  
     S1,     
S2       S2  .. , , 
   S1         /, 
  S2         2  ..  
     ,    . 
. 19. 

    .      ,    
    ,     
,     .  ,      
   ,   . . 18. 


     .      699 


     1 
     2 
    S1	Smith		20	London		JP1	300 
    2	200		400	h	200	5	100 
    
    
    	100J 
    
    
    S2 
    Jones 
    10 
    Paris 
    (   , 4, 5) 

    . , 19.      

       ,      , 
  . . 16,     ,  
   . (    
 ,        
.       ,  .) 

      

      (Huffman) [A.39]     
,       ,    
     ,    
 (,  ,   ).    
        
 ,       
  .  ,        
      -  . 
    ,        , , , D, 
;  ,    ,      . 

    	, %	 
    	35	1 
    	30	01 
    D	20	001 
    	10	0001 
    	5	0000 

              , 
     .       
(      ,       
     )    .  
          
 01,          00.  
  ' D,      001, 0001  0000 . 
            
   : 

    0,35 *  1 + 0,30 *  2 +  0,20 *  3 + 0,10 * 4 + 0,05 *  1 = 2,15 

            ,  
           
 , ..        ( ) 
    40% ,    . 

    700  

    .        , 
 ? 
    1.       00110001010011 
    2.    0100000110011 

    .8.  

          (   )  
     .     
     , 
    ,      
  ,     .   
          
         
 .        ,  
    . 
         .  ,  
 ,       
  .  ,    
     , RID-. 
      ,  
  . 
        (  ,   -)   
     . 
        (  )     
 . 
         (   - 
)    . 
     ,     . 
       ,      ( 
   )     . , 
 ,      
  ,     :   
    ,    
   .     
      ,    
       .     
   (      ),   
,   . 

     

     .1-.8      ,  
         
  ,   .9     . 
    .        ( ,  
)   ,       
    ,    .  
    ?  '  ? 
  ( )   ( )  ?  
  ?   ?      
     

     .     	701 

 ?   -     
  ?  ,  ?      
 ?       ?  ,  ? 
    .2.         ,  
   .      ,  
     .     
       .   
      , .. , 
            
. .   "     "  
"     "     
 "     " (    
 --).    ,      
      ,     
   . 
    ..  . .2         
.       ,    
     . .    
.--    .     
      (  
  ).       
              
  .     -   
   --? 
    .4,  . .2         
,       ,    
  . .      . .? 
    ,5.           
 (..  , -  ..)   .  
        .   
, ..    ,      
 ,    .     
           
    ,      
 .        
   . 
    .6.        . 
,          
         , 
     -;   
     ;   ( 
).       ? 
    .7.      ,     
      -   
      ( 
 ).       
 ? 

    702	 

    .8.       
-- ?     
 .        ? 
    .9. ,  " " ,    
     . ,   
       ,      
   :      ,   
    .      
   : )  ; )  ; ) N . 
    .    - (    
),       
   N    ,      
 (..    )   
  ,    .      
 ()   .  ,   
       .   
          -. 
    .11.        
  : 
    Abrahams, GK Ackermann,LZ Ackroyd,S Adams, Adams,TR Adamson, CR Alien,S 
Ayres,ST Bailey, Baileyman, D 
             
 15 .          
,    ?     
 ( )?       
 ,   (  )   
  Ackroyd, s  Adams, v?       
   Allingham,M? 

      

           . 
   [.1-.10],   , 
   .  [A.I 1-A.I5]    
   ,  [.16-.23]   , 
   -.  ,     
 [.24-.38],   [.39-.40],   
      [.41.59]. 
    . Knuth D.E. The Art of Computer Programming. Volume III: Sorting and 
Searching.  Reading, Mass.: Addison-Wesley, 1973. 
              
 . 

     .     	703 

    A,2, Martin J, Computer Data-Base Organization. (2nd ed.).  Englewood 
Cliffs, N.J.: Prentice-Hall, 1977, 
          "Logical Organization"  "Physical 
Organization".      ( 300 ) 
     . 
    ,3, T'eorey T.J., Fry J.P. Design of Database Structures.  Englewood 
Cliffs, N.J.: Prentice-Hall, 1982. 
             
   ( 200    ), 
    .4. Wiederhold G. Database Design (2nd ed.).  New York, N.Y.: 
McGraw-Hill, 1983. 
     (15 )        
   ( ,  50 ),   
    ( ,  250 ). 
    ,5, Merrett .. Relational Information Systems.  Reston, VA.: Reston 
Publishing Company, Inc., 1984. 
            ( 100 
),     ,       . 
    ,6. Ullman J.D. Principles of Database and Knowledge-Base Systems: Volume 
I. Rockville, MD.: Computer Science Press, 1988. 
       ,     
,     . 
    .7. Korth H.F., Silberschatz A. Database System Concepts (2nd ed.).  New 
York, N.Y.: McGraw-Hill, 1991. 
    A.8. Smith P.O., Barnes G.M. Files and Databases: An Introduction. --- 
Reading, Mass.: Addison-Wesley, 1987. 
    A.9, Elmasri R., Navathe S.B.  Fundamentals of Database Systems (2nd ed.). 
 Redwood City, Calif: Benjamin/Cummings, 1994. 
     [.7-.9]     ,    
  ,       , 
    (   [.8]). 
    , Ghosh S.P. Data Base Organization for Data Management (2nd ed.).  
Orlando, Fla: Academic Press, 1986. 
               
   -          
.      . 
    A.ll, Hsiao D.K., Harary F. A Formal System for Information Retrieval from 
Files //  ACM,  1970.  13, 2. 
    , ,     ,   
 ,     ,    
   . 
    .12. Severance D.G. Identifier Search Mechanisms: A Survey and 
Generalized Model // ACM . Surv.  1974.  6,  3. 
         .     
    ,     

    704	 

.      [ 1],     
      - 
(trie-tree),      ,    . 
 trie (""),    ,   try,   
    [.42].      
        
 .    (  )   
          
   . 
            ,   
 -  ,   ,   
[ 1],   . 
    .13. Senko M.E., Altman E.B., Astrahan M.M., Fehder P.L. Data Structures 
and Accessing in Date-Base Systems // IBM Sys. J.  1973.  12,  1. 
        . 
    1.Evolution of Information Systems (  ). 
    2.Information Organization ( ). 
    S.Data Representations and the Data Independent Accessing Model 
(       ). 
             1973 
.       " ", 
        
     (    
 ANSI/SPARC).      , 
           (Data 
Independent Accessing Model  DIAM).  ,      
     ,  :  
 ( ), ,    . 
     ,      
     ANSI/SPARC. 
       DIAM (  [ 1,   2])    
       .  
  (   ,   [ 1, . 12]) 
   ,       
      ,   
 . 
    .14. Yao S.B. An Attribute Based Model for Database Access Cost Analysis 
// ACM TODS. 1977.2,  1. 
           ,   [ 1, .12], ..  
        , 
        .   
         
    .  ,    
 ,        
         . 

     .     	705 
    23      


    , 15. Batory  D.S.  Modeling  the  Storage  Architectures  of Commercial  
Database Systems // ACM TODS.  1985.  10 ,  4. 
         ,  , 
          
   (   
-  .  2)    . 
        
 (      , 
 ),    (      
 ).   ,    
-     
   .  ,  
        
  .        
 : INQUIRE, ADABAS  System 2000. 
    . 16. Bayer R., McCreight . Organization and Maintenance of Large 
Ordered Indexes // Acta Informatica.  1972.  1,  3. 
    A, 17. Comer D. The Ubiquitous B-tree // ACM . Surv.  1979.  11,  2. 
        -. 8. Wagner R.E. Indexing Design 
Considerations // IBM Sys. J.  1973.  12,  4. 
       ,   ,  
   ,    VSAM  IBM. 
    . 19. Chang   H.K.   Compressing   Indexing  Method  //  IBM   Technical  
 Disclosure Bulletin. 1969.II,  11. 
    A.20. Gupta G.K. A Self-Assessment Procedure Dealing with Binary Search 
Trees and B-trees // CACM.  1984.  27,  5. 
    A.21. Lum V.Y. Multi-Attribute Retrieval with Combined Indexes // Ibid.  
1970.  13,  11. 
           
 . 
    .22. Mullin J.K. Retrieval-Update Speed Tradeoffs Using Combined Indices 
// Ibid.  1971.14,  12. 
      [.21];     
        
       /. 
    .23. Shneiderman . Reduced Combined Indexes for Efficient Multiple 
Attribute Retrieval // Information Systems.  1976.  2,  4. 
           
 ,   [.21],    
      . ,  
 ABCD, BCDA, CDAB, DABC, ACBD, BDAC (.   . .9,)  
  ABCD, BCD, CDA, DAB, AC, BD. ,     , 
, , D   10  ,       
    60 000  ,   
   13 200. 

    706	 

    .24. Morris R. Scatter Storage Techniques // CACM.  1968.  11,  1. 
            
  ,        
.        ,  
     [.28].    
      ,     
       -   
 .  ,       
      ,    
         - (  
   -). 
          ,    
    ,      
      . 
    .25. Maurer W.D., Lewis T.G. Hash Table Methods // ACM . Surv.  
1975.  7, 1. 
      ,    ,    
 ,  , ,  .   
     (   /, 
   , , ,     
 ),    -   , 
    ,    ( 
,        ). 
.   -    
  (  ,   ),  
    -. 
    .26. Lum V.Y., Yuen P.S.T., Dodd M. Key-to-Address Transform Techniques: 
A Fundamental Performance Study on Large Existing Formatted Files // CACM.  
1971. 14, 4. 
         (.. 
"")  .    ,  
  "/"   . 
    .27. Ramakrishna M.V. Hashing in Practice: Analysis of Hashing and 
Universal Hashing // Proc. 1988 ACM S1GMOD Intern. Conf. on Management of 
Data.  Chicago, 111., 1988. 
         (    [.1]),   
,  ,      
  :   -    
 .   ,    
   ,       , 
..     -  
    .     [.26] 
 .         
-?    ,      
       
   .      
 . 

     .     	707 

    .28, Fagin R., Nievergelt J., Pippenger N., Strong H.R, Extendible 
Hashing  A Fast Access Method for Dynamic Files // ACM TODS.  1979.  4,  3. 
    A.29. Knott G.D. Expandable Open Addressing Hash Table Storage and 
Retrieval // Proc. 1971 ACM SIGF1DET Workshop on Data Description, Access, and 
Control.  San Diego, Calif., 1971. 
    A.30. Larson P.-A. Dynamic Hashing // BIT.  1978.  18. 
    A.31. Litwin W. Virtual Hashing: A Dynamically Changing Hashing // Proc. 
4th Intern. Conf. on Very Large Data Bases.  Berlin, FOR, 1978. 
    A.32. Litwin W. Linear Hashing: A New Tool for File and Table Addressing 
// Proc. 6th Intern. Conf. on Very Large Data Bases.  Montreal, Canada, 1980. 
    A.33. Larson P.-A. Linear Hashing with Overflow-Handling by Linear Probing 
// ACM TODS. 1985.10,  1. 
    A.34. Larson P.-A. Linear Hashing with Separators  A Dynamic Hashing 
Scheme Achieving One-Access Retrieval // Ibid.  1988.  13,  3.   
[A.28-A.34]        . 
 [.29]           
,         ,   [.28].  
        [.30].    
[.28],          
    ,   [.28]. 
""      ,   [.31]. 
"" ,   [.32]    [.33, 
.34],     . 
    .35. Litwin W. Trie Hashing // Proc. 1981 ACM SIGMOD Intern. Conf. on 
Management of Data.  Ann Arbor, Midi., 1981. 
           . 
      , .. ""   
   ,   -. 
       ,      
 . 
         (     )  
     ,      . 
         (    , 
   ,    ,  
       ). 
       - (   ,     
   )    
- [.42],        
 ,         
  .     ""  
 -,       
 -    ""  
  .       
,     ,   -. 

    708	 

     -,     ,   
 ,      ( 
 -       -).  
    ,    
  , ,   ,   
 .     -,   
       
 .  ,   - 
    (   ).   
  ,  -      
,      ,    
      [.32]   . 
    .36. Lomet D.B. Bounded Index Exponential Hashing // ACM TODS.  1983.  
8,  1. 
         ,   : 
             ( )  
 - (    ). 
            (  
   ,      
   ,    
    ). 
          . 
          . 
    .37. Card ..,  Gotlieb ..  Order-Preserving Key Transformations // 
Ibid.  1986. 11, 2. 
         [.35], - (  
)   ,    
      , 
    -.    
     .   , 
 ,   : 
    - =     -    
(, 10 000) 
        -  ,   
,   -   (  
  ).      
-,       .  
     -  
  -   . 
(- [.35]    .)    
    -     
      . 
    .38. Ramakrishna M.V., Larson P.-A. File Organization Using Composite 
Perfect Hashing // Ibid.  1989.  14,  2. 
    -  ,      "". 
( ""    "". ,  
,  -    ,   
 ,     

     .     	709 

    ,  -  ,   
           .) 
 -         
  -.       
     . 
    .39. Huffman D.A. A Method for the Construction of Minimum Redundancy 
Codes // Proc. IRE.  1952.  40. 
    A.40. Marron B.A., Maine P.A.D. Automatic Data Compression // CACM.  
1967.  10,  11. 
       /: NUPAK   , 
ANPAK   -  ""  (..   
 ). 
    .41. Severance D.G., Lohman G.M. Differential  Files:  Their Application 
to the Maintenance of Large Databases // ACM TODS.  1976.  1,  3. 
      " ".   
       ,    
     ( )   
           .  
     . 
             . 
            . 
              
    . 
            . 
            . 
         . 
       -. (-   
     ,   
    , , ,    
,      .) 
        . 
          . 
          . 
             
, ..   ,       
,      . 
    .42, Fredkin E. TRIE Memory // CACM.  1960.  3,  9. 
    - (trie)       
    ,      ,  
          ,  , 
,   - [.35].   - 
    ,     
. ,        , 
     10 

    710	 

: , 1, 2,... 9.       
"4285".         "4"  
    ,       
 "4".   ,     "2"   
  ,       "42".  
       "8"    
 ,        "428". , 
,     ,     "429",   
 "42"  "9"       . 
 ,       . ( 
, -,  ,    .) 
    .   (trie)     "retrieval" 
(),        try. 
-    ""    . 
    .43. Wong E., Chiang T.C. Canonical Structure in Attribute Based File 
Organization // Ibid. 1971.14, 9. 
             . 
,         
   " = ",      
.           , 
""  ,      , 
    .      
  . 
             . 
              
  . 
            - . 
    .44. Stonebraker M. Operating System Support for Database Management // 
Ibid.  1981. 24, 7. 
     ,       ( 
,  )       
 ,   ,    
  . 
    .45. Schkolnick M. A Survey of Physical Database Design Methodology and 
Techniques // Proc. 4th Intern. Conf. on Very Large Data Bases.  Berlin, FOR, 1978. 
    A.46. Finkelstein S., Schkolnick M., Tiberio P. Physical Database Design 
for Relational Databases // ACM TODS.  1988.  13,  1. 
            
      ,    
 .   ,  ,    ,  
 ""   .  ,   
 ,       
,     .  , 
         
   .   ,    
  .          
  

     .     .  711 

    ,        
, DBDSGN,       System R 
[8,12, 8,13].      DBDSGN   
   (..      
 ),        
.        
      (,    
..),     . 
     DBDSGN        
 RDT  IBM,      
     SQL/DS. 
    .47. Sevcik K.C. Data Base System Performance Prediction Using an 
Analytical Model // Proc. 7th Intern. Conf. on Very Large Data Bases.  
Cannes, France, 1981. 
       ,       , 
   ,      
 ,     .   
       ,   
   .       
       ,   . 
          
:  ,   ,   , 
   ,   -   
.   ,       
 ,       
  ,   
,     . 
            
  ( ).  ,    
      . 
    .48. Samet H. The Quadtree and Related Hierarchical Data Structures // 
ACM . Surv.  1984,  16, 2. 
              
   .      
         ,  
      ,   
       .   
        .   
      [.49],    [.50-.59]. 
    .49. Samet H. The Design and Analysis of Spatial Data Structures.  
Reading, Mass.: Addison-Wesley, 1990. 
    .    . 
    .50. Christodoulakis S., Ford D.A. Retrieval Performance Versus Disc 
Space Utilization on WORM Optical Discs // Proc. 1989 ACM SIGMOD Intern. Conf. 
on Management of Data.  Portland, Ore., 1989. 
    .   [.51], 

    712	 

    .51. Lomet D., Salzberg B. Access Methods for Multiversion Data // Ibid. 
     ,       
 ,   WORM (   "Write 
Once, Read Many times"   ,  ).  
      ,    
 ,    .   
      ,   
 .    ,   
 -      ,   
   . ,    
    .  [.50, .51]   
   . ,  [.51]  , 
   ,      
   (,  ,    
,    ). 
    .52. Encarnafao J., Krause F.L. (eds.). File Structures and Data Bases 
for CAD.  New York, N.Y.: North-Holland, 1982. 
        ()   
   .        
  ,  . 
    1.   Data Modeling for CAD (   ). 
    2.   Data models for geometric modeling (    ). 
    3.   Databases for geometric modeling (    ). 
    4.   Hardware structures (  ). 
    5.  CAD database research issues (     ). 
    6.   Implementation problems in CAD database systems ( 
    ). 
    7.   Industrial applications ( ). 
    .53 Finkel R.A., Bentley J.L. Quad-Trees  A Data Structure for Retrieval 
on Composite Keys // Acta Informatica.  1974.  4. 
    A.54 Nievergelt J.,  Hinterberger H.,  Sevcik K.C.  The Grid File:  An 
Adaptable, Symmetric, Multikey File Structure // ACM TODS.  1984.  9,  1. 
    A.55 Guttman A. R-Trees: A Dynamic Index Structure for Spatial Searching 
// Proc. ACM SIGMOD Intern. Conf. on Management of Data.  Boston, Mass., 1984. 
    A.56 Roussopoulos N., Leifker D. Direct Spatial Search on Pictorial 
Databases Using Packed R-Trees // Ibid.  Austin, Texas, 1985. 
    A.57 Beckley D.A., Evens M.W., Raman V.K. Multikey Retrieval from K-D 
Trees and Quad-Trees // Ibid.  Austin, Texas, 1985. 
    A.58 Freeston M. The BANG File: A New Kind of Grid File // Ibid.  San 
Francisco, Calif, 1987. 
    A.59 Barnsley M.F., Sloan A.D. A Better Way to Compress Images // BYTE.  
1988.13,  1. 
           .  
     ,   

     .     	713 

 ,      
    .    
     10 000  . 

        

    .5.     . 
             
   .      
 . 
            
    .    
  . 
        : 
             
,         
 ,  . 
      , ,    ,  
    .     
         
      . 
    .6,          
        .  
,  ,       
   .  ,     
   ,  , 
   . 

    . ,        
 ,   . ,  
           , 

    .7, ,  - h      
   k. 
        ,   ,    
  -     -   
   -. ,      
   -    . 
         ,     h(k)  
,         
.          
   . 
     ,       ,  
    ,     
    -,    -,  
 .   rl     
- 2,   ,   2   
- h2        
 ,      ,   

    714	 

        - h2.  
,        ,  
      . 
    .9. ) 3; ) 6 (,     , , , D   
       ,   
  ABCD, BCDA, CDAB, DABC, ACBD, BDAC); ) ,  
          N 
 (     ,     N12), .. 
  N\l(n\*(N-n)\).       
  (Lum) [A.21]. 
    .   -     k,  
 nk~' < N<nk.      ,  k1 < 
lognW < k,  
    k = cz\\(\ognN),  ceil(jc)    ,    
 . 
     ,     /-    , ( / = 
1    ).  ,  

    '~< 

    , ,     

    /=* JN^ 
    ill 
    Zceil| 
    U' 

      

    ceil 
    iW 
    ceil  
    U'J 
     
    
    V	J 

     ,  N = qti + r ( <  < '-\).  )  =0, 
    )  r>Q, 

    if N 
    = ceil 
    Jq + l x = ceil - 
    V   n 

     .      715 

    ,  q = q'n + ' ( < ' <  -1),  

    N = (q'n + r')ri +r = q'nM + (r'ri +r), 

       0 < ' < ' -1  0 < ' <  -1,  

     < (  +)<  -('-)< , 

     

    N 
    ,,ceil(  ' + 1, 
     
    ../ + ' +   ~ ceil - 
    = ' + 1, 

      1 < ' 4-1 < /7,  ,     ()  ()  
      

    ceil 
    ,/ 
    " 
    = ceil 
    ./ N 
    V  
    /41 

     ,  \ = cei\(N/n),   \+\  ceil(f,/w), 1 ? i < k. 
 ,  , ~ ceil(/V/'),  

    />   =ceil 
    ( -/"V ceil  U'J 
    	^^.ii       . U' 

    A.ll. 
       . ,       

       

     - 2 - 	 
    1 - 3 - eke	Acke 
    3 - 1 - 	Ackr 
    1  7  dams,T+	Adams, TR 
    5  1  	Adamso 
    1-1-1	Al 
    1 - 1 - 	Ay 
    0  7 - Bailey,	Bailey, 
    6 - 1  m	Baileym 

       . 

    1,   ,    , ! 
    ,     
  ,     . 

    716  


    2.      ,    
   (  )   
 . 
    3.    "+"      . 
    4.   ,        
 "Baileym"     . 
            100*( 
150-35)/!50 = 76,67 %. 
        ; ,     
   (       
 15 ). 
    found := false ; /*    */ do for each index entry in turn 
; /*      */ expand current index entry and let 
expanded length = N ; /*    */ /*   
 N */ 
    if expanded entry = leftmost N characters of V /*   
  */ /*   N    V */ then do ; 
    /*     */ 
    retrieve corresponding stored record ; 
    /*    */ if value in that record = V 
    I*    = V */ then found := true ; 
    /*    */ leave loop ; 
    /*    */ 
    end ; if expanded entry > leftmost N characters of V 
    /*     */ 
    /*    N    V */ then leave loop ; 
    /*     */ end ; 
    if found = false /*     */ then /*   
   V * I ; else /*     V  */ ; 
       "Ackroyd, s"      
 ;       
    . 
       "Adams,v"      
    . 
       "Aiiingham,M"     
   , ..     "Alien, s", 
,  "Aiiingham,M"     
"Mien, s". ( ,     .) 
   "Aiiingham,^'     
. 1.         . 

     .     	717 

    2.         "Alien, s"   : 
    1 - 3 -  
    3.           
    "Alien, s"  ","  : 
    3 - 1 -  

     ,        
   . ,       
   ,    ,     
  . 

    718  

