jackrabbit-oak-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Thomas Mueller (JIRA)" <j...@apache.org>
Subject [jira] [Comment Edited] (OAK-169) Support orderable nodes
Date Mon, 09 Jul 2012 07:07:33 GMT

    [ https://issues.apache.org/jira/browse/OAK-169?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13409228#comment-13409228
] 

Thomas Mueller edited comment on OAK-169 at 7/9/12 7:05 AM:
------------------------------------------------------------

Iterating over all child nodes is always an O( n ) operation (n = number of child nodes).
Of course if you store all child nodes names in the parent node you only have to access the
parent node, but that parent node is just n time larger then. We would be back to the behavior
of Jackrabbit 2.x, where adding many child nodes is an O( n^2 ) operation, for orderable child
node lists. This might or might not be acceptable - I don't think we decided this when we
defined our goals.

With the linked list approach, iterating over all child nodes will have to read all child
nodes (also an O( n ) operation), on the other hand it will make it possible to support many
child nodes without limitations. It is true that this approach is probably slower if there
are few child nodes (compared to storing the complete child node name list in the parent).

I guess to decide which approach works best in practice we first need have to define which
use cases we care about and which are the most common ones.
                
      was (Author: tmueller):
    Iterating over all child nodes is always an O(n) operation (n = number of child nodes).
Of course if you store all child nodes names in the parent node you only have to access the
parent node, but that parent node is just n time larger then. We would be back to the behavior
of Jackrabbit 2.x, where adding many child nodes is an O(n^2) operation, for orderable child
node lists. This might or might not be acceptable - I don't think we decided this when we
defined our goals.

With the linked list approach, iterating over all child nodes will have to read all child
nodes (also an O(n) operation), on the other hand it will make it possible to support many
child nodes without limitations. It is true that this approach is probably slower if there
are few child nodes (compared to storing the complete child node name list in the parent).

I guess to decide which approach works best in practice we first need have to define which
use cases we care about and which are the most common ones.
                  
> Support orderable nodes
> -----------------------
>
>                 Key: OAK-169
>                 URL: https://issues.apache.org/jira/browse/OAK-169
>             Project: Jackrabbit Oak
>          Issue Type: New Feature
>          Components: jcr
>            Reporter: Jukka Zitting
>
> There are JCR clients that depend on the ability to explicitly specify the order of child
nodes. That functionality is not included in the MicroKernel tree model, so we need to implement
it either in oak-core or oak-jcr using something like an extra (hidden) {{oak:childOrder}}
property that records the specified ordering of child nodes. A multi-valued string property
is probably good enough for this.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

        

Mime
View raw message