[ZODB-Dev] B-tree enhancement : interval search.
Vladimir Voznesensky
vovic at smtp.ru
Fri Sep 5 17:27:35 EDT 2003
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
More information about the ZODB-Dev
mailing list