title: Data structure/algorithm for variable length record storage and lookup on disk withsearch only on primary keys
body: <p>I am looking for an algorithm / data structure that works well for large block based devices (eg a mechanical hard drive) which is optimised for insert, get, update and delete where searches are always done using the id of the data and where the data fields for any ID have a variable length.</p>
  
  <p>The B-Tree seems to be a commonly quoted structure but mainly for fixed length records. I also expect dramatically more gets and updates than I do inserts and deletes. Can I get rid of the O(log m) lookup of the B-tree?</p>
  
  <p>I am quite happy for it to be a combined system, for instance ISAM combines a B-tree and linear file storage which looks like it can be made to work with variable length records as an approach. Is there something better?</p>
  
  <p>Some further constraints:</p>
  
  <p>1) IDs are potentially sparse but they can be made to come in blocks of linear numbers - but in a large range (64 bit)</p>
  
  <p>2) I don't want to use a DBMS, performance for my particular problem hasn't proved very good. I don't need any of the operations a full DBMS uses, I don't need search. I need something I can tweak and optimise easily. Call it academic curiosity, if it is out performed by MySQL then I'll use that but I have to try and go faster.</p>
  
  <p>3) The dataset is larger than can fit in memory, the index however may well fit into memory if its as simple as key, offset. I am certainly looking at something like 1 billion entities or more in storage.</p>
  
  <p>4) Ideally space should be recovered when a record is deleted. That may be via compaction but I am interested to see if there is a better way (A B-tree for instance recovers space easily).</p>