On 01/08/2014 10:42, Tommaso Teofili wrote: > I don't yet have a proper proposal, but maybe what could be done may be > something similar to what Davide has done with regards to the ordered index > (using a skiplist), that is defining a specific structure of the nodes, > together with a specific implementation, that avoids having to use sortable > node types but is an inherently sorted structure, e.g. binary search tree. > Any opinions?
Unfortunately both the above options won't efficiently work for a reason or another as we discovered during the implementations of the ordered index. Skip list: * doesn't really scale with large numbers (500k-1M) as of the randomised access due to the probabilistic data structure. On the Segment case for example, fetching the "next" property resulted in an expensive operations with big data as you end-up most probably fetching a new segment that is not cached (read from disk). * in case of mongo back-end is not concurrent due to the storing of the "next" property under the node. The stack will raise a merge exception and it can't be catch by the commit hook. That's why we have to keep it asynchronous when running on mongo. Segment is not affected. BTree: Considered it but it requires sooner or later a big tree moving due to tree restructure and this is not efficient with oak. With the result that some CUD operations could take long to complete. Hopefully if the new algorithm will result in a fully working and scalable one we could consider making it a node type. Cheers Davide
