On Mon, Oct 19, 2015 at 5:57 PM, Emmanuel Lécharny <elecha...@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
> No test, not need to remember if the seek(K) method set the position
> before or after K.
>
>
> Is that extravagant, or just spurious ? I mean, we can live with
> seek(K), it does the job, I just wonder if the additional methods don't
> mke the developer lifer easier.
>
> wdyt ?
>
>
--
Kiran Ayyagari
http://keydap.com
