Lecture 8 — Indexing & Hashing

What an index is and costs, the eight evaluation metrics (with a live selectivity calculator), the ten index types, and B-Tree / B+ Tree construction step by step.

Sections

Quick summary

INDEX = a separate sorted structure of (key → row pointer) so the DBMS need not scan the table.
   Search index → get pointer → fetch row.  Table scan O(n) → index O(log n).
BENEFITS: fast search · fast ORDER BY · faster joins · UNIQUE enforcement · less disk I/O.
DEMERITS: extra storage · slower INSERT/UPDATE/DELETE · too many indexes hurt writes ·
   useless on very small tables.

METRICS: search time · disk I/O cost · query execution time ·
   SELECTIVITY = distinct values / total rows (high is good) · index size ·
   maintenance cost · index hit ratio · cardinality (# unique values).

TYPES: primary · secondary · unique · composite · clustered (one per table, rows physically
   ordered) · non-clustered (many) · ordered · DENSE (entry per key) · SPARSE (entry per block,
   needs a sorted file) · MULTILEVEL (index over an index → the idea behind B/B+ trees).

B-TREE: keys AND record pointers in internal + leaf nodes; balanced (all leaves same level);
   a search may END AT AN INTERNAL NODE.
B+ TREE: internal nodes hold ONLY keys; all record pointers in the LEAVES; leaves LINKED in
   sorted order ⇒ excellent range queries; every search ends at a leaf (uniform cost);
   higher FAN-OUT ⇒ fewer levels ⇒ fewer disk reads. Used by almost every RDBMS.

Max 3 keys/node, insert 10…22 (course convention: on 4 keys promote the 3rd):
   B-Tree  → [18] ; [12 15] , [21] ; leaves [10 11][13 14][16 17] | [19 20][22]
   B+ Tree → [10 14 18] ; [10 12][14 16][18 20] ;
             leaves [10 11][12 13][14 15][16 17][18 19][20 21 22] (chained)