title: How to represent and insert into an ordered list in SQL?
body: <p>I want to represent the list "hi", "hello", "goodbye", "good day", "howdy" (with that order), in a SQL table:</p>
  
  <pre><code>pk | i | val
  ------------
  1  | 0 | hi
  0  | 2 | hello
  2  | 3 | goodbye
  3  | 4 | good day
  5  | 6 | howdy
  </code></pre>
  
  <p>'pk' is the primary key column. Disregard its values.</p>
  
  <p>'i' is the "index" that defines that order of the values in the 'val' column. It is <em>only</em> used to establish the order and the values are otherwise unimportant.</p>
  
  <p>The problem I'm having is with inserting values into the list while maintaining the order. For example, if I want to insert "hey" and I want it to appear <em>between</em> "hello" and "goodbye", then I have to shift the 'i' values of "goodbye" and "good day" (but preferably not "howdy") to make room for the new entry.</p>
  
  <p>So, is there a standard SQL pattern to do the shift operation, but only shift the elements that are necessary? (Note that a simple "UPDATE table SET i=i+1 WHERE i>=3" doesn't work, because it violates the uniqueness constraint on 'i', and also it updates the "howdy" row unnecessarily.)</p>
  
  <p>Or, is there a better way to represent the ordered list? I suppose you could make 'i' a floating point value and choose values between, but then you have to have a separate rebalancing operation when no such value exists.</p>
  
  <p>Or, is there some standard algorithm for generating string values between arbitrary other strings, if I were to make 'i' a varchar?</p>
  
  <p>Or should I just represent it as a linked list? I was avoiding that because I'd like to also be able to do a SELECT .. ORDER BY to get all the elements in order.</p>