directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Howard Chu <...@symas.com>
Subject Re: [Mavibot] Cursor handling
Date Mon, 19 Oct 2015 17:55:51 GMT
Kiran Ayyagari wrote:
>
>
> On Mon, Oct 19, 2015 at 5:57 PM, Emmanuel Lécharny <elecharny@gmail.com
> <mailto:elecharny@gmail.com>> wrote:
>
>     Le 19/10/15 04:37, Emmanuel Lécharny a écrit :
>      > Le 19/10/15 03:24, Howard Chu a écrit :
>      >> Emmanuel Lécharny wrote:
>      >>> Hi,
>      >>>
>      >>> some thoughts about the current implementation :
>      >>>
>      >>> Cursor support in Mavibot
>      >>> -------------------------
>      >>>
>      >>> The current implementation is a bit unsastifactory, and it does not
>      >>> necessarily fits with the simplifications we are introducing (namely,
>      >>> the removal of duplicate values). Typically, the current cursor allows
>      >>> the user to move forward and backward across keys and values, when
we
>      >>> only need to move across keys now.
>      >>>
>      >>> Moving
>      >>> ------
>      >>>
>      >>> First of all, we must be able to move backward and forward. Fetching
an
>      >>> element is a different operation than moving, but one should still
be
>      >>> able to get back an element when moving. This is done through 4 methods,
>      >>> 2 which are relative, and 2 which are absolute.
>      >>>
>      >>> Relative moves :
>      >>> next() : move forward to the net key
>      >>> prev() : move forward to the net key
>      >>>
>      >>> Absolute moves :
>      >>> next(K) : move after the given key
>      >>> prev(K) : move before the given key
>      >> These absolute moves seem like an extravagance. I have never seen a
>      >> dbm-style library with such methods. It's more natural to have an
>      >> explicit seek() method and then do a relative next/prev after that.
>      > It is used for searches like (age>20). If the key 20 does not exist in
>      > the B-tree, next(20) will move to the closest key above 20, and prev(20)
>      > will move to the closest key below 20. If the key 20 exists, then
>      > next(20) will be moved after the key 20 and prev(20) before the key 20.
>      >
>      > Now, we may need a seek(K) to fetch an element we know exists in the
>      > Btree, to avoid having to do things like prev(K); tuple = next();
>      >
>      > I have to thought a bit more about the real need for those before(K) and
>      > after(K) methods, wil wait for my morning shower for that : insomnia is
>      > not the best timing to have a clear thought about API design decisions ;-)
>
>     Second thought :
>
>     if we want to efficiently browse forward *and* backward, the seek(K)
>     method is not sufficient to correctly guess what to do when doing the
>     first next or prev move when the K is not present. Either we set the
>     position after K, or before K, but in any case, we have to do annoying
>     things like :
>
>     (NOTE : we don't check the limits here, which means some extra checks
>     have to be done to see if we are at the beginning or at the end of the
>     B-tree. This can also be done using exceptions)
>
>     (NOTE 2 : I assume the  position is set after K if K is not existent, or
>     set on K if it exists)
>
>     getting the previous key
>     ------------------------
>
>     tuple = seek(K);
>
>     if ( tuple == null )
>     {
>          tuple = prev();
>     }
>
>     getting the next key
>     --------------------
>
>     tuple = seek(K);
>
>     if ( tuple == null )
>     {
>          tuple = get();
>     }
>
>     If the key is present, we are done, the seek(K) will return the value.
>
>     OTOH, using the before(K)/after(K), it's easier :
>
>     getting the previous key
>     ------------------------
>
>     tuple = before(K);
>
>     getting the next key
>     --------------------
>
>     tuple = after(K);
>
> the before(K) and after(K) are convenient to support filters with >= and <=
> operators

In BDB and LMDB, "seek" is SET_RANGE, and it's defined to locate the item >= 
to the given key.

In practice, <= operator isn't a case of its own, we simply use first() and 
iterate until the returned key is >= the target.

-- 
   -- Howard Chu
   CTO, Symas Corp.           http://www.symas.com
   Director, Highland Sun     http://highlandsun.com/hyc/
   Chief Architect, OpenLDAP  http://www.openldap.org/project/

Mime
View raw message