tree-structure mapping node-IDs to pages reducing number of nodePages to create after modifications
<p>I'm working on a persistent tree-structure supporting versioning through the COW-principle and different versioning approaches. Now I want to save storage space overhead due to our node-ID => page ID mapping.</p>

<p>Each node page currently holds up to 128 nodes. Our node keys are long values thus our approach works best in revision 0 where all node pages are completely filled except the last one.</p>

<p>After that we are loading nodePages depending on the revisioning approach whereas our mapping is as follows:</p>

<pre><code>/**
 * Calculate node page key from a given node key.
 * 
 * @param pNodeKey
 *            node key to find node page key for
 * @return node page key
 */
final long nodePageKey(@Nonnegative final long pNodeKey) {
    return pNodeKey &gt;&gt; IConstants.NDP_NODE_COUNT_EXPONENT;
}

/**
 * Calculate node page offset for a given node key.
 * 
 * @param pNodeKey
 *            node key to find offset for
 * @return offset into node page
 */
final int nodePageOffset(@Nonnegative final long pNodeKey) {
    final long shift =
        ((pNodeKey &gt;&gt; IConstants.NDP_NODE_COUNT_EXPONENT) &lt;&lt; IConstants.NDP_NODE_COUNT_EXPONENT);
    return (int)(pNodeKey - shift);
}
</code></pre>

<p>That is after that we are loading for each node to modify the nodePage whereas each nodePage has an array of nodes, and I expect most entries are null which certainly also occupies space in memory, not to mention the space for persistent storage. As we also use pointers for each node (well, I've compressed them through a range-encoding and compression of the long-keys, but nontheless) which is a space overhead I now first want to optimize storage cost for updates. Sadly I couldn't come up with a better mapping which maps node keys more densely even after updates. Optimally reducing the size from 0 to 128 after updates to the nodePage which just contains the modified node to use subsequent indexes starting from 0, such that we don't have gaps and modified nodes residing on different nodePages just add to a list in the nodePage which is newly created to save modifications.</p>

<p>Currently depending on the node-ID we likely have large gaps and too many new nodePages with sometimes only one modified node in the worst case and all other 127 entries in the array nulled and somehow persisted (127 bytes or even more due to our Integer based node types which we probably also should reduce to a single byte).</p>

<p>Well, I'm now doing a nodePage local optimization, instead of using an array I'm using a List and do something along the lines in getNode(long): just return an Optional (whereas Optional is the Guava Optional-class and T is of type T extends INode: the index in the list should be just the original nodePageOffset divided by the list size if I'm not too confused tonight.</p>
