LIS 558 - File structures

File structure feature Advantages Disadvantages
Data files
Ordering by sort key
  • Useful for display and printing.
  • Binary search on the sort key is possible.
  • Duplicates are easier to detect.
  • Inserting a new record may mean rewriting the whole file.
Fixed record lengths
  • Easier record processing; for example, for binary searching.
  • Easier to reclaim freed space without danger of fragmentation.
  • Waste of space.
  • Problem of dealing with overflows.
Linked list structures
  • Insertion involves only minor changes to the file.
  • Searching or processing a long list may be time consuming, requiring many disk accesses.
  • A raw display or printout of the file is harder to interpret.
  • A little more space is required for pointers.
  • Reclaiming freed space can be complex if records are not fixed-length.
Index files
  • More efficient searching.
  • More space and processing requirements.
Primary key range indexing
  • Search on the primary key is speeded up, since the index will usually be small enough to fit into memory.
  • Range lengths, and hence search times, may vary, especially with additions, deletions, and changes.
  • Additions, deletions, and changes may require modification of the index, depending on the data file structure.
Full primary key indexing
  • Search on the primary key is speeded up further, especially if the index is still small enough to fit into memory.
  • The user can easily browse the primary key values.
  • Additions, deletions, and some updates require changes to the index as well as to the data file.
Secondary key indexing
  • Search on secondary keys is speeded up.
  • The user can easily browse the secondary key values.
  • Many additions and deletions and some updates require changes to the secondary key index.

Home

Last updated July 5, 2001.
This page maintained by Prof. Tim Craven
E-mail (text/plain only): craven@uwo.ca
Faculty of Information and Media Studies
University of Western Ontario,
London, Ontario
Canada, N6A 5B7