FYI, I have been too swamped with work-work and keeping Armory from breaking under the increased blockchain load to spend too much time on this specific proposal.  I have not lost interest by any means, I just need to catch my breath after some big deadlines.  Then I'll be taking some time off to work explicitly on some Bitcoin stuff... including this proposal.

I'm going to spend some time in the near future looking at space efficiency of a couple variants of the trie data-structure.  I'm not sure exactly how this theoretical datastructure can be merged with a disk-based DB engine (I imagine that what I have in mind is not used by an existing, acceptable DB engine) but maybe there's a way to make a hybrid.  This is a problem that still needs to be resolved before we can move forward with an implementation:  Once we agree on a datastructure, how do we use it but avoid re-inventing the wheel in terms of robust, scalable disk-based database engines?

The more I've been thinking about it, the more I have become convinced that a trie-like structure is necessary.  Note only are query and insert times are constant, the determinism of tree structure for a given set of tree nodes means that queries and inserts can be parallelized.  For instance, the tree could be implemented with the first layer (the first 256 nodes of a 256-way trie) split into a different files/DBs/processes/servers for each branch.  Then every new piece can be distributed and queued for its particular destination.  It could even be distributed amongst different, independent servers.  This seems to be advantageous.

For reference, I learned of this particular tree in my data structures class in college, but I find no reference that anyone else has ever heard of it.  In my class it was called a "De La Brandia Tree/Trie".  A Patricia tree is a level-compressed trie.  A "de la brandia tree" is a Patricia tree that uses a linked-list of pointers, instead of a constant-size array.  i.e. -- in a 256-way trie or patricia tree, each branch node contains 256 pointers (8 bytes each), which could point to other nodes.  However, the sparseness of lower-level nodes means that the nodes will frequently have 255 null pointers, with only one relevant pointer.  The de-la-brandia tree will represent all child pointers with an ordered linked list.  It has some extra overhead for nodes that have mostly-full child lists, but it I think such near-full nodes will be tiny compared to the amount of space saved on sparse nodes.

When I get some more time, I'll make some pictures, and update the original post with the updated proposal.  

Not sure if this helps:

http://wiki.postgresql.org/wiki/IndexingXMLData#Patricia_Trie
http://stackoverflow.com/questions/355051/how-do-you-store-a-trie-in-a-relational-database

yes, that is the correct answer. I'm just concerned that miners will be convinced that they are "supporting" the block chain with only the compressed/pruned version on their disk drive.
That is why I'm asking etotheipi to clarify how this will be presented to the miner community. That is, its a tool for the miners and everyone else, but the miners should still support the full blockchain.

FYI, I opened a bounty jar for this project at booster.io. Please add a link to the OP.

Since the alt-chain can only update as often as the main chain, would using a different difficulty mechanism make sense? Of course adherer or not merged mining is used matters.

For example: Instead of saying that the first hash below difficulty wins, is there any way to say that the absolute lowest hash wins? The biggest issue I can see without an obvious answer is how to keep the chain from backpedaling if someone releases a better block N-1 while everyone else is working on block N , but it might just be a variant on the 51% attack.

TL;DR - would a different difficulty mechanism be warranted?

Everything would work as is, but this chain wouldn't work quite the same I don't think. Since this alt-chain essentially needs to have the same number of blocks as the primary bitcoin chain. If the alt-chain catches up there's no incentive, or value, in mining anything else on it, which otherwise "wastes" the workers that are participating on the chain.

My main point is that linking the block count to the main chain one-to-one changes things somewhat. Or is this not as big of an issue as I'm thinking it is?

Edit: Fixed typos made while using my phone.

The chain has established itself as a good proof-of-work system, which is the largest reason to stick with it that I can see right off hand. However it may run more like P2Pool in that storing old blocks (other than headers) may be slightly useless, or at least contrary to the goal of eliminating extra data. Setting up the alt-chain with either "none" or "some" updates may be the way to go to preserve simplicity however compared to normal chains. For one of the datastructure guys, would there be an advantage in marking updates as "a few" vs "many" in terms of packing the data? Maybe something else worth looking into for someone who knows how the current setup would work.

As a much more random aside, any idea what the alt-chain coins could be used for? and if transfer would be worthwhile. If transfer doesn't matter just give 1 coin per block and let people sign with their keys how many they've accumulated helping to secure the chain for lite nodes. 

+100

The term that makes the most sense for me is a "meta-tree".  It would never be "mined" - it would simply be committed to in normal blocks - optionally - at least until it is proven to work in practice and a decision is made to make it a mandatory part of the protocol.

Perhaps that's another reason to use insert-order-invariant tree structure.  If you have to reverse some transactions, you don't have to worry how you undo them.  Undoing a block/tx is just as easy as adding it in the first place.