2.2.11. Clustering Index (as pairs list)

  • Two fields <K(i),P(i)>
  • Ordering non-key field and pointer to block
    • Internal structure e.g. linked list of records
  • Each block may contain multiple records
    • K(1)="Barnes",P(1) -> block 1
    • K(2)="Bates",P(2) -> block 2
    • K(3)="Zeta",P(3) -> block 3
  • K(i) not required to have
    • a distinct value for each record
    • non-dense, sparse