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.

Linear index is poor for insertion/deletion.

Tree index can efficiently support all desired operations:

• Insert/delete

• Multiple search keys (multiple indices)

• Key range search

Difficulties when storing tree index on disk:

• Tree must be balanced.

• Each path from root to leaf should cover few disk pages.