Re: [boost] [BTREE] Get BTREE library into boost - Market Research

Subject: Re: [boost] [BTREE] Get BTREE library into boost - Market Research
From: Beman Dawes (bdawes_at_[hidden])
Date: 2012-12-21 16:15:47

On Thu, Dec 20, 2012 at 8:41 PM, Joel <jdy_at_[hidden]> wrote:
> Beman, Antony, thanks for the feedback.
>
> Beman Dawes <bdawes <at> acm.org> writes:
>> On Thu, Dec 20, 2012 at 6:30 AM, Antony Polukhin <antoshkka <at> gmail.com> >
>
>> > 6) Search methods can be speed up, if a `position hint` iterator is
>> > provided (just like in ` iterator std::set::insert (iterator position,
>> > const value_type& val);`)
>>
>> The implementation already does a lot of page caching; if there is an
>> outstanding iterator the page is already in memory, as are all pages
>> above it in the Btree. Thus it isn't obvious that a hint would
>> actually have much effect. But it would be interesting to add such a
>> search function and run some timings.
>>
>
> One query mode we often need to do is retrieve the payloads for an ordered
> list of keys.  It would be advantageous if the search could take advantage of
> knowing that the next answer is guaranteed to be after the previous one (and
> probably closer to the previous one than to the last record in the btree).

The cache keeps the most recently used tree in memory, so the basic
mechanisms for optimizing such retrievals are already in place. What
might be helpful would be to add some profiling or even automatic
tuning to take advantage of particular workloads. Automatic, rather
than manual, packing might also be worthwhile, particularly for
applications with sufficient idle time.

--Beman