Thanks Rich.
Just a point of terminology: When we talk about featureids in geogig we usually call them "paths" by analogy to files in git. "ids" or shas would be the hashes used to turn key-value stores into content-addressable storage. I may have used ID for both when I was explaining this week, sorry to muddy the waters.
If we include spatial metadata in the ordering of the trees, then we will be hindering one of the optimizations in the diff algorithm - since tree nodes are hashed as well, we can omit entire subtrees if they have the same SHA (objectid.) If you can think of a way to avoid it that's great, but my current thinking is that the best way would be to isolate the spatial index in a separate tree structure. That also makes it easier to use non-tree indices if appropriate.
Another thing to keep in mind is that even if we only index one attribute of one layer we probably really have a family of indices - there should be an index of every version of a layer (or at least the facility for having that.) In this case even though a tree structure is inefficient use of the key/value store we do benefit from some storage savings by being able to share unchanged parts of the index between versions. OTOH spatial rebalancing may mean that this doesn't work as well for things other than the path. How would you envision a non-tree-based index co-existing with what is in place already? We do have frequent need for lookup by just the objectid.