Please enable JavaScript.

Coggle requires JavaScript to display documents.

File management (Architecture (Physical I/O (Deals w/ blocks of data),…

- - - - Max file size allocated @ creation
        
        Can be difficult to estimate
    - - Portion of file = contiguous set of blocks
      - Large enough to hold entire file?
      - 1 portion = 1 block?
      - Considerations
        
        Contiguity increases performance
        
        Many small portions = larger tables to manage
        
        Variable-size/small fixed-size > less wasted space
        
        Fixed-size > simpler
      - Major alternatives
        
        Variable, large contiguous portions
        
        Better performance
        
        Avoids waste
        
        Space hard to reuse
        
        Dealing w/ fragmentation
        
        First fit
        
        Best fit
        
        Nearest fit
        
        Blocks
        
        Flexible
        
        Not concerned w/ contiguity
  - - - External fragmentation
      - Preallocation
    - - Allocation on individual block basis
      - Blocks have pointer to next block
      - Usually dynamic allocation
      - No locality (w/o consolidation)
    - - Fixed- or variable-size
  - - - Bit table
        
        0 = free
        
        1 = allocated
        
        Bit for each block on disk
        
        Small
        
        Easy to find contiguous groups
    - - Pointer & length in free portions
    - - 24 or 32 bits per block #
        
        24 or 32 times bit table size
- - - - >1 child
      - Keys
        
        Nondecreasing order
        
        #: 1-max
        
        Left child, subtree of all smaller keys
        
        # of keys + 1 = # of children
      - Right child, subtree of greater keys
    - - max 2d pointers per node
      - min d pointers per node (not root)
        
        root: min 1 key, 2 children
  - - - Leftmost child
    - - Rightmost child
    - - Pointer between lower/upper bound keys
  - - - Not in tree
        
        Current node is full
        
        Split node around median key into two nodes
        
        Insert left if key < median
        
        Insert right if key > median
        
        Promote median node into upper level
        
        Promote recursively and split root if parents are full
        
        Current node is not full
        
        Insert in node
- - - - Data collected in order of arrival
      - Named fields
      - No structure
      - Recird access by exhaustive search
      - Usage scenarios
        
        Data is hard to organize
        
        Before processing
    - - Same length records
        
        Same # of fixed-lengths fields in order
      - Key field
      - Usage scenarios
        
        Batch applications
      - Sequential search
      - Organization
        
        Linked list
        
        Additions in a pile, merge w/ master in batches
    - - Key file
      - Index for random access
        
        Key field
        
        Pointer to main file
      - Overflow file
        
        Additions go here
        
        Main records have invisible pointer to overflow records
      - Single- or multilevel indexing
    - - Exhaustive index
      - Partial index
      - Usage scenarios
        
        Information timeline critical
        
        Data not/rarely processed exhaustively
        
        e.g. airline reservation system
    - - Key field
      - Usage scenarios
        
        Rapid access required
        
        Fixed length records
        
        Records accessed one at a time
- - - - Reader/writer problem
      - Methods
        
        Fixed blocking
        
        Internal fragmentation
        
        Fixed-length records
        
        Variable-length spanned blocking
        
        Records may span two blocks
        
        No internal fragmentation
        
        Difficult to implement
        
        Variable-length unspanned blocking
        
        Internal fragmentation
        
        Limits record size to block size