2. Indexing
2.1. Indexing
Goals:
Store large files
Support multiple search keys
Support efficient insert, delete, and range queries
2.2. Files and Indexing
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.
2.3. Keys and Indexing
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.
2.4. Linear Indexing (1)
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.
2.5. Linear Indexing (2)
If the index is too large to fit in main memory, a second-level index might be used.