Database Indexing

Goal: Perform binary search (or some algorithm) on an index for more efficiency

An index is computed separately from the table An index uses a key (like the primary one for a table, or a different one)

Types of sequential file organization

Basically just the file organization tree or whatever structure (e.g. bucket to table) Records stored in sequential order (like a sorted list)

1. Dense - index entry for each record
2. Sparse - index entry for some records (point to block, not records), extracted
3. hash into buckets based on key

Types of indexing

1. Clustered - stored in one index file, sorted, any key (typically non primary)
2. Primary - primary key, corresponds to a block of records
3. Non-clustered - just references to values (data is in leaf nodes), dense organization, idk when this should be used
4. Multi-level - add more extractions (grow tree height)

Pros

• Fast search

Cons

• Slower write/update
• more storage space

Common Scenarios

1. Lookup is slow. How can it be sped up?