jackrabbit-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Thomas Müller <thomas.muel...@day.com>
Subject Re: [jr3] Flat hierarchy
Date Thu, 18 Feb 2010 11:34:24 GMT
Hi,

I would also use a b-tree structure. If a node has too many child
nodes, two new "invisible internal nodes" are created, and the list of
child nodes is split up. Those internal nodes wouldn't have any
properties.

For efficient path lookup, the child node list should be sorted by
name. This is a bit tricky.

Currently, when adding a node, it is added as the last child. I
suggest to change that behavior, and add it at the "right place" by
default (so that the sort order is preserved). Like this, a path
lookup is very fast even if there are many child nodes (binary search
/ b-tree). Is that an acceptable change (usability and spec conform)?

If the user changes the child node order (manually re-ordered the
nodes), then the sort order is broken. Then the path lookup has to
scan through all nodes. While that's much slower, I think it's
acceptable. One alternative is to use a linked list (each child node
points to the next child node), which is very problematic for sharable
nodes.

So there would be a hidden flag 'child nodes are sorted by name'.

Regards,
Thomas

Mime
View raw message