DATABASE-MANAGEMENT WITH SEQUENCE TREES AND TOKENS

An approach to organizing storage in database systems is presented tha t, under a wide range of conditions, saves both storage space and proc essing time. Text values in a database are replaced by short, fixed-le ngth, rank-preserving numeric tokens. The actual values are stored in separate, nonredundant storage. Database operations that depend only o n the relative magnitude of data values can be performed directly on t he tokens. Tokenization is shown to improve database performance most in situations where there are a lot of ad hoc queries and a low volume of database insertions relative to other operations.