title: Finding next gap within values
body: <p>Suppose I have the following table:</p>
  
  <pre><code>id  name  base   index
  0   A     2      0
  1   B     2      2
  2   C     2      4
  3   D     2      6
  4   E     2      8
  5   F     2      10
  </code></pre>
  
  <p>So, index = base * i, where i is the position of that row in a sequence.</p>
  
  <p>From time to time, some rows are deleted, for instance, if I delete rows named C and D:</p>
  
  <pre><code>id  name  base   index
  0   A     2      0
  1   B     2      2
  4   E     2      8
  5   F     2      10
  </code></pre>
  
  <p>New rows are always added after the last, so the next row would be MAX(index)+base=12 in this case, but the gap left between values in the index column due to the deleted rows would be a problem after some time. If instead of inserting last I insert it in the first available gap, the problem won't happen.</p>
  
  <p>So, I doubt any queries to find the first available gap would be as efficient as the MAX(index), but what would the most efficient solution be? Maybe it's good enough.</p>
  
  <p>In case it's not clear, I need to find the first row 'a' such that the row with the closest upper index value is more than a.index + a.base.</p>
  
  <p>This is meant for an application using an ORM for any SQL databases, so it has to be strictly standard SQL.</p>
  
  <p><strong>edit</strong></p>
  
  <p>This is a simplification of the real table and the real problem, and I'm looking for a solution using the base and index columns only. Solutions involving adding new columns or indexing in other table are not practical for my application.</p>
  
  <p><strong>edit 2</strong></p>
  
  <p>It seems the base column is making it more complicated, but that isn't essential. The problem can be reduced to a table like:</p>
  
  <pre><code>id  name  index
  0   A     0
  1   B     1
  4   E     4
  5   F     5
  </code></pre>
  
  <p>Where I need to find the first row 'a' such that the row with the lowest index that's higher than a.index + x. In this case x = 1.</p>
  
  <p>Enumerating without ordering first or leveraging on the id aren't reliable solutions, since those can change. For instance, a solution has to work if the rows are like this too:</p>
  
  <pre><code>id  name  index
  0   A     0
  23  F     5
  45  E     4
  90  B     1
  </code></pre>