[ZODB-Dev] B-tree enhancement : interval search.

[Vladimir Voznesensky]

Christian Reis wrote:

>>My algorythm accelerates searching in many cases from times to 
>>magnitudes (depending on template and data variations) comparing to 
>>traditional approach of standard Berkeley DB API. I'd like to have and 
>>use the same thing in ZODB.
>>    
>>
>
>Question: does the template necessarily have a fixed number of
>characters, or is something like the * wildcard supported too?
>  
>
Well, when searching using my method, need to supply a estimation 
function getting first and last key of the interval and returning one of 
3 possible answers:
1. There are no suitable keys inside the interval [first, last).
2. All of the keys are sutable.
3. Some of the keys inside maybe suitable, some of them -- maybe not 
(worst case). In this case, we need to divide interval into parts and 
estimate every part separately.
First estimation on a specific B-tree is on the first and the last keys 
interval of the whole tree (first key usually stored in the root page -- 
I do not know ZODB B-tree specifics). Next estimations (if 1st 
estimation returns 3) are on parts of root (and possibly child) pages.
So (as I understood), in case of * wildcard we cannot estimate intervals 
efficently, so, in case of *, the benefit is not big, if exists at all.

Thank you.
VV
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.zope.org/pipermail/zodb-dev/attachments/20030905/35f20d72/attachment-0001.htm