Goals:

• Store large files

• Support multiple search keys

• Support efficient insert, delete, and range queries

Entry sequenced file: Order records by time of insertion.

• Search with sequential search

Index file: Organized, stores pointers to actual records.

• Could be organized with a tree or other data structure.

Primary Key : A unique identifier for records. May be inconvenient for search.

Secondary Key: An alternate search key, often not unique for each record. Often used for search key.

Linear index: Index file organized as a simple sequence of key/record pointer pairs with key values are in sorted order.

Linear indexing is good for searching variable-length records.

If the index is too large to fit in main memory, a second-level index might be used.