Hi, On Thu, Feb 18, 2010 at 2:01 PM, Thomas Müller <thomas.muel...@day.com> wrote: > The repository is one large b-tree, and each JCR node is a b-tree node > (except for the JCR nodes that don't have any child nodes: those are > b-tree leaves).
I don't think we can model the entire repository as a B-tree (it's certainly a tree, but the B-tree restructuring and balancing features don't apply). Instead I'd store the child node lists of each node as separate B-trees. > Path lookups would still be fast (the same speed as now), except for > large child node lists that were re-ordered. The difference is only > for large child node lists. There is a difference between 'orderable' > nodes (have the ability to reorder the child node list) and actually > 're-ordered' child node lists. Is it acceptable if new nodes appear in > lexicographic order in the child node list? Instead of modifying the standard insertion order semantics for orderable nodes, we could add a "next" pointer to the B-tree entries to overlay a linked list on top of the B-tree structure. This makes the data structure more complex but allows us to maintain support for orderable nodes. BR, Jukka Zitting