title: Alternatives for data entry k* in index k
body: <p>I'm having a hard time wrapping my head around this concept of Alternative 1 vs 2/3 for data entry into an index. Here is an excerpt from some notes:</p>
  <blockquote>
  <p>Alternative 1:<br>
  Actual data record (with key
  value k)<br>
  – If this is used, index structure is a file
  organization for data records (like Heap
  files or sorted files).<br>
  – At most one index on a given collection of
  data records can use Alternative 1.<br>
  – This alternative saves pointer lookups but
  can be expensive to maintain with
  insertions and deletions.</p>
  </blockquote>
  <br>
  <blockquote>
  <p>Alternative 2: (k, rid of matching data record) and<br>
  Alternative 3: (k, list of rids of matching data records)<br>
  – Easier to maintain than Alt 1.<br>
  – If more than one index is required on a given file, at most
  one index can use Alternative 1; rest must use Alternatives 2
  or 3.<br>
  – Alternative 3 more compact than Alternative 2, but leads to
  variable sized data entries even if search keys are of fixed
  length.<br>
  – Even worse, for large rid lists the data entry would have to
  span multiple blocks!</p>
  </blockquote>
  <p>Can someone help me understand this by providing some concrete examples?</p>