Method of sorting and compressing data

摘要

A method for sorting data in a computer data storage system that has particular advantages in implementing a key index tree structure. The sorting method uses buffer-size substrings to sort strings of key records into a linked list structure that can be directly transformed into an index tree. The sorting method also may be used for sorting large sets of data records in place on a computer storage system. The method further integrates prefix compression and suffix compression of key records with the sorting method to reduce the number of input/output operations required to create a more compact key index tree structure.