title: Java - how to efficiently write a sequential file with occassional holes in it
body: <p>I have a requirement to write records to a file where the data is written at a file location (i.e, seek position) depending on the value of a numeric key. For example, if the key is 100, I might write at position 400.</p>
  
  <p>The records consist of the numeric key and a piece of data. The record won't be very large (a few bytes). However, there may be a lot of records (millions).</p>
  
  <p>There are two possible scenarios:</p>
  
  <ol>
  <li><p>The keys are monotonically increasing. In this case, the best approach is to write using a <code>DataOutputStream</code> wrapping a <code>BufferedOutputStream</code>, setting the buffer size to some number (e.g. 64k) to maximize I/O throughput.</p></li>
  <li><p>The keys are increasing but with possible large gaps. In this case using an OutputStream would require zeros to be written in the gaps in the file. To avoid this, a <code>RandomAccessFile</code> would be better as it could seek over the gaps, saving space if it is possible to seek over an entire block. The drawback is that, as far as I know, <code>RandomAccessFile</code> doesn't buffer, so this method is going to be slow for sequential keys.</p></li>
  </ol>
  
  <p>However, the likely situation is that the file is a bit of both. There are sequences of monotonically increasing keys. There are some keys with small gaps between and others with very large gaps.</p>
  
  <p>What I am looking for is a solution that gives the best of both worlds. It might be that I switch between the two I/O modes if a gap between keys is detected. However, it would be better if there is a standard Java class that can do both of these things. I have seen <code>FileImageOutputStream</code>, but I am not sure how this works.</p>
  
  <p>Note that I am not looking for code samples (although that would be helpful for demonstrating for complex solutions), just a general strategy. It would be good to know optimal sizes buffer sizes for sequential data and at what point (gap size) you need to switch from a sequential strategy to a random-access strategy.</p>
  
  <p><strong>EDIT:</strong></p>
  
  <p>For an answer to be accepted, I would like some assurance that the proposed solution handles both, not just that it might. This would require:</p>
  
  <ul>
  <li>Confirmation that the sequential mode is buffered.</li>
  <li>Confirmation that the random access mode leaves holes in the file.</li>
  </ul>
  
  <p>Also, the solution needs to be memory efficient as there could be many of these files open simultaneously.</p>
  
  <p><strong>EDIT 2</strong></p>
  
  <p>The files could be on a NAS. This is not by design, but simply recognition that in an enterprise environment, this architecture is used a lot and the solution should probably handle it (perhaps not optimally) and not prevent its use. AFAIK, this should not affect a solution based on <code>write()</code> and <code>lseek()</code>, but might invalidate some more esoteric solutions.&nbsp;</p>