5.5 Inverted Files

5.5 Inverted Files

In the early days of relational databases, the consensus of ignorance was that an implementation would have to use fully inverted files. In an inverted file, every column in a table has an index on it. It is called an inverted file structure because the columns become files. Imagine a file where each record starts with a value, followed by a list of row numbers. This means that you could then throw away the tables, since they can be reconstructed from the row numbers. NULL values have a natural representation by not having a row number in the record for them.

Inserting, updating, and deleting on a fully indexed table is very slow, since many different index files have to be searched to find and reconstruct each row. But searching for groups of rows with a common value is very fast. Doing a GROUP BY operation is a matter of merging the index files for the columns in the grouping and seeing what records overlap.

The Model 204 database is based on the inverted file model. It is very good at picking a small subset from a much larger set and has been favored by the U.S. government for certain agencies, such as the CIA and NSA.

< Previous Excerpt Next Excerpt >

Purchase This Book

Joe Celko's Data and Databases: Concepts in Practice

TABLE OF CONTENTS

5.5 Inverted Files

Contact Preferences

This is embarrasing...

Customize Your GlobalSpec Experience

Select Your Free Newsletters

Industry Newsletters

Select Your Free Product Alerts

This is embarrasing...