Pushed SortedTree to Git after adding a unit test and doing some debugging. TODO:Add API for indexed relationships using SortedTree as the implementation.Make SortedTree thread safe. With regard to the latter issue. I am considering the following solution. Acquire a lock (delete a non existent property) on the node that points to the root of the tree at the start of AddNode, RemoveNode and Delete. No other node in the SortedTree is really stable, even the rootnode may be moved down, turning another node into the new rootnode, while after a couple of remove actions the original rootnode may even be deleted. Locking the node pointing to the rootnode, prevents all other threads/transactions from updating the tree. This may seem restrictive, but a single new entry or a single removal may in fact have impact on much of the tree, due to balancing. More selective locking would require a prebalancing tree walk, determining the affected subtrees, lock them and once every affected subtree is locked, perform the actual balancing. Please let me hear if there are any objections to locking the node pointing to the tree as the a solution to make SortedTree thread safe. Niels
> Date: Tue, 5 Jul 2011 08:27:57 +0200 > From: neubauer.pe...@gmail.com > To: user@lists.neo4j.org > Subject: Re: [Neo4j] Indexed relationships > > Great work Nils! > > /peter > > Sent from my phone. > On Jul 4, 2011 11:39 PM, "Niels Hoogeveen" <pd_aficion...@hotmail.com> > wrote: > > > > Made some more changes to the SortedTree implementation. Previously > SortedTree would throw an exception if a duplicate entry was being added. > > I changed SortedTree to allow a key to point to more than one node, unless > the SortedTree is created as a unique index, in which case an exception is > raised when an attempt is made to add a node to an existing key entry. > > A SortedTree once defined as unique can not be changed to a non-unique > index or vice-versa. > > SortedTrees now have a name, which is stored in the a property of the > TREE_ROOT relationship and in the KEY_VALUE relationship (a new relationship > that points from the SortedTree to the Node inserted in the SortedTree). The > name of a SortedTree can not be changed. > > SortedTrees now store the class of the Comparator, so a SortedTree, once > created, can not be used with a different Comparator. > > SortedTree is now an Iterable, making it possible to use it in a > foreach-loop. > > Since there are as of yet, no unit tests for SortedTree, I will create > those first before pushing my changes to Git. Preliminary results so far are > good. I integrated the changes in my own application and it seems to work > fine. > > Todo: > > Decide on an API for indexed relationships. (Community input still > welcome).Write unit tests.Make SortedTree thread safe (Community help still > welcome). > > Niels > > > >> From: pd_aficion...@hotmail.com > >> To: user@lists.neo4j.org > >> Date: Mon, 4 Jul 2011 15:49:45 +0200 > >> Subject: Re: [Neo4j] Indexed relationships > >> > >> > >> I forgot to add another recurrent issue that can be solved with indexed > relationships: guaranteed unicity constraints. > >> > From: pd_aficion...@hotmail.com > >> > To: user@lists.neo4j.org > >> > Date: Mon, 4 Jul 2011 01:55:08 +0200 > >> > Subject: [Neo4j] Indexed relationships > >> > > >> > > >> > In the thread [Neo4j] traversing densely populated nodes we discussed > the problems arising when large numbers of relationships are added to the > same node. > >> > Over the weekend, I have worked on a solution for the > dense-relationship-nodes using SortedTree in the neo-graph-collections > component. After some minor tweaks to the implementation of SortedTree, I > have managed to get a workable solution, where two nodes are not directly > linked by a relationship, but by means of a BTree (entirely stored in the > graph). > >> > Before continuing this work, I'd like to have a discussion about > features, since what we have now is not just a solution for the dense > populated node issue, but is actually a full fledges indexed relationship, > which makes it suitable for other purposes too. > >> > An indexed relationship can for example be used to maintain a sorted > set of relationships in the graph, that is not necessarily huge, but large > enough to make sorting on internal memory too expensive an operation, or > situations where only one out of a large number of relationships is actually > traversed in most cases. > >> > There are probably more use cases for in-graph indexed relationships, > so I'd like to know what features are desirable and what API would Neo4J > users appreciate. > >> > P.S. I still think it would be good to consider, if technically > possible, partitioning the relationship store per relationship type and per > direction. The indexed relationship solution works, but is of course slower > than a direct relationship, both with respect to insert time and traversal > time. If dense relationships are never traversed going out of the dense > node, the extra structure maintained by the BTree is only extra burden. > >> > P.P.S. If there are people with experience to make an implementation > thread safe, please volunteer to help make the implementation production > proof. > >> > Niels > >> > _______________________________________________ > >> > Neo4j mailing list > >> > User@lists.neo4j.org > >> > https://lists.neo4j.org/mailman/listinfo/user > >> > >> _______________________________________________ > >> Neo4j mailing list > >> User@lists.neo4j.org > >> https://lists.neo4j.org/mailman/listinfo/user > > > > _______________________________________________ > > Neo4j mailing list > > User@lists.neo4j.org > > https://lists.neo4j.org/mailman/listinfo/user > _______________________________________________ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user _______________________________________________ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
