Kiran Ayyagari wrote:
On Mon, Oct 19, 2015 at 5:57 PM, Emmanuel Lécharny <[email protected] <mailto:[email protected]>> 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/
