From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lj1-f193.google.com (mail-lj1-f193.google.com [209.85.208.193]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 2715E4696C3 for ; Sat, 25 Apr 2020 12:00:33 +0300 (MSK) Received: by mail-lj1-f193.google.com with SMTP id b2so12395604ljp.4 for ; Sat, 25 Apr 2020 02:00:32 -0700 (PDT) Date: Sat, 25 Apr 2020 12:00:27 +0300 From: Konstantin Osipov Message-ID: <20200425090027.GA8860@atlas> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: Subject: Re: [Tarantool-patches] [PATCH] rfc: multi-directional iterators List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Nikita Pettik Cc: tarantool-patches@dev.tarantool.org, v.shpilevoy@tarantool.org * Nikita Pettik [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