GATE CS - DATABASES (DBMS):Indexing and File Organization
Mastering indexing and file organization concepts and implementation.
Indexing for GATE CS
GATE indexing asks dense vs sparse, primary vs secondary, and B/B+ tree fan-out or height estimates. File-organization buzzwords are secondary.
Why an index
An index is a separate structure that maps search-key → record pointer(s) so you avoid scanning the whole file.
| Type | Idea |
|---|---|
| Dense | Index entry for every search-key value |
| Sparse | Index entry per block (sorted file) |
| Primary | On the ordering key of the file |
| Secondary | On a non-ordering attribute (may be non-unique) |
| Clustered | File order matches index order (≈ primary on ordered file) |
B+ trees (the usual GATE tree)
- Data in leaves only; internal nodes = routers
- Leaves linked for range scans
- All leaves at same depth
Height / fan-out questions: given order or max children, bound the number of levels for keys. Roughly: more fan-out ⇒ shorter tree.
B tree vs B+: B trees can store records in internal nodes; B+ keep them in leaves — GATE may ask which supports faster range queries (B+).
Hash indexes
Static hashing: → bucket. Dynamic (extendible / linear) appear less often. Good for equality; weak for ranges compared with B+.
Cost intuition
Unindexed select: . Indexed equality: height + data block(s). Know that a bad secondary index on a low-selectivity column can be worse than a scan.
Previous: Transactions. Practice: GATE hub.