11.Indexing
- Goals:
- Store large files
- Support multiple search keys
- Support efficient insert, delete, and range queries
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.
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.
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.
Linear Indexing (2)
- If the index is too large to fit in main memory, a second-level index
might be used.
Tree Indexing (1)
- 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
Tree Indexing (2)
Tree Indexing (3)
- Difficulties when storing tree index on disk:
- Tree must be balanced.
- Each path from root to leaf should cover few disk pages.
Tree Indexing (4)
