title: B-Trees / B+Trees and duplicate keys
body: <p>I'm investigating the possibility of putting together a custom storage scheme for my application.  It's worth the effort of potentially reinventing the wheel, I think, because both performance and storage efficiency are a main objective and the data and operations on it are far simpler than everything provided by an RDBMS (no updates, no deletes, predefined set of queries).</p>
  
  <p>I'm using just a small handful of web resources I've found about B-Trees and B+-Trees - Wikipedia, <a href="http://www.bluerwhite.org/btree/">http://www.bluerwhite.org/btree/</a>, <a href="http://slady.net/java/bt/view.php">http://slady.net/java/bt/view.php</a>, <a href="http://www.brpreiss.com/books/opus6/html/page342.html">http://www.brpreiss.com/books/opus6/html/page342.html</a> (the last one is the most valuable).</p>
  
  <h2>Duplicate keys</h2>
  
  <p>The first problem I'm trying to solve is how to deal with duplicate keys - this tree will be acting as a DB index and for example there won't just be one 'thing' with 'color=red', so looking up 'red' in this tree should yield many results.</p>
  
  <p>There are two solutions I have come up with so far.  The first is simply having multiple entries in the tree for each of these.  But when there are 100,000 or 1,000,000 'red' things in the tree.. is that very efficient for a tree structure?  The second was to have just one entry for each key, but the 'payload' associated with each key points to a different block of data, which is a linked list pointing to all instances of items that are 'red'.</p>
  
  <p>Is there a common / better option?</p>
  
  <h2>B+Tree nodes changing types</h2>
  
  <p>I wanted to check an assumption I'm making.  Say you have a B+-Tree, height 2 - the external (leaf) nodes at level 2 hold 'actual data'.  Then an insertion necessitates a split of a leaf node - the leaf node no longer holds 'actual data'.  Am I right in thinking that in implementation terms because the data might be of a substantial size that you would instead store a kind of 'pointer' as the 'actual data' - so if a leaf node becomes a branch node, that pointer (of the same size) is instead updated to point to the new subtree? </p>
  
  <p>By that I mean, internal and external nodes, they should be the same size really since external nodes might become internal ones, and shuffling data around isn't a good idea?</p>
  
  <p>(Added the C# tag since I'm implementing this from scratch in C#.)</p>