Sorted Order

• The big drawback of sorted files is that they're hard to update

• You can't just append a new record at the end

• Comparison:

                Unsorted        Sorted

        Lookup  Slow            Fast
        Add     Fast            Slow
        Delete  Slow            Slow

• An alternative is a hybrid approach

  • Have two files, one sorted, one unsorted

• For lookups, search the sorted file first, then the unsorted file

• To add records, append to the unsorted file

• Periodically merge the unsorted file into the sorted one

Next

Copyright © 2003 M. J. Dominus