title: The core of a reservation system - finding an unreserved item efficiently
body: <p>This seems like a common question, but I have been web searching and can't find the answers.</p>
  
  <p>I want to reserve something for a number of days (no partial days), so I guess I need a table something like:</p>
  
  <pre><code>CREATE TABLE reservations 
      (
       item int, 
       customer int, 
       startDate date, 
       endDate date
      );
  </code></pre>
  
  <p>(Hmm, what's my primary key? item and startDate? Do I even need a PK?)</p>
  
  <p>But my main question is how to find a free item, given a start and end date. What does my <code>SELECT ...</code> look like?</p>
  
  <p>For bonus marks, can we assume that all items are identical and that I want to make this as efficient as possible, so that if I want to reserve from Friday I would prefer to find a item which is reserved until Thursday (and, thus is free from Friday).</p>
  
  <p>For double bonus marks, if I need an item for X days, I would like to find an item with a hole in its reservations as close to X days as possible.</p>
  
  <p>I think that the problem is that I am trying to find something which is not there (an existing reservation). All other solutions which I have found seem to have a table of bookable dates with an item Id (with a value of NULL, 0 or -1 to mean "not yet booked"). That seems inefficient to me. And how far into the future would this table extend?</p>
  
  <p>Note: some people are asking about the ratio of reads to writes. Obviously each reservation is made only once, so that's one write (maybe one per day, depending on the implementation) and I would expect multiple reads as users search for an unbooked slot.</p>