How does "headers first" affect BLKxxxx.dat structure? Assuming a full node running Bitcoincore v0.10 (with txindex=1), how exactly does the new "headers first" functionality affect the structure of the blockchain data? (Specifically, the blkxxxx.dat data, though perhaps I'm unaware of other files which are ancillary to the data structure).

The README.md for the release specifies that there's no v0.9.x back-compatibility for v0.10 blockchain blk data. 


  Because release 0.10.0 makes use of headers-first synchronization and
  parallel block download (see further), the block files and databases
  are not backwards-compatible with older versions of Bitcoin Core or
  other software:
  
  Blocks will be stored on disk out of order (in the order they are
  received, really), which makes it incompatible with some tools or
  other programs. Reindexing using earlier versions will also not work
  anymore as a result of this.


How then, does the 0.10 version blk data get parsed by the client? And by extension, why does "headers first" change the structure at all, given it seems to logically set up "a template" for the Tx data to sit?
To the best of my understanding, it's just that the blocks are stored in a different order. Headers first synchronization makes use of parallel downloads and the blocks are downloaded (and then stored) out of order. It used to be the case in older versions that blocks were downloaded and then stored in order, so that's whey they added the comment to the README. 

I believe it doesn't change the structure of how any individual block is stored, just that they are now likely to not be in the proper order.