[Tarantool-patches] [PATCH] rfc: multi-directional iterators

[Konstantin Osipov]

* Nikita Pettik <korablev at tarantool.org> [20/01/26 23:58]:
> +Cons (-):
> + - obviously the main drawback of this approach is time complexity -
> +   it doesn't seem to be way faster than simple full-scan (the more key parts
> +   with different iterating order are declared, the slower process will be).

This is not true. Getting to the next distinct element in a tree is O(log(distance
between elements)) of the tree, not O(distance between elements).

Actually it's quite evident that for BPS it's best to use this
option, the main issue with the implementation is that
multi-directional iterators require more state (they need to
remember a stack of positions), than a single-directional one (it
only has one position, the current one).


-- 
Konstantin Osipov, Moscow, Russia