Re: [Boost-users] [multiindex] Why not to add B+Tree index to multiIndex?

Subject: Re: [Boost-users] [multiindex] Why not to add B+Tree index to multiIndex?
From: joaquin_at_[hidden]
Date: 2008-11-24 08:15:42

Ion Gaztañaga escribió:
> Cory Nelson wrote:
>   
>> On Thu, Nov 20, 2008 at 9:18 AM,  <joaquin_at_[hidden]> wrote:
>>     
>>> fgmailbox escribió:
>>>       
>>>> we can use multiindex as a memory db,but the multiindex only support
>>>> hash index and Order index(RB TREE),why not to add b+ Tree Index to
>>>> multiindex to make it much faster .
>>>>         
>>> I'm no expert in B+ trees, but I understand that these structures are
>>> more effective than regular binary trees when secondary storage (i.e.
>>> hard disk) is used, which is not the case for an in-memory container
>>> like multi_index_container. Have you any reference on the performance
>>> of B+ trees in in-memory scenarios?
>>>       
>> The b+tree implementation here: http://idlebox.net/2007/stx-btree/
>>
>> Seems to boast greater speeds than std::multiset, but I question if
>> that is merely due to having far less allocations with the b+tree.
>>     
>
> For in-memory classes simple b-trees would be more size efficient 
> because b+ trees store all the data in leaves (and this is specially 
> important for DB where data is in files). And yes, allocating several 
> values in a node saves costly allocations and improves locality.
>   

This seems to clash with some very basic design features of 
Boost.MultiIndex, where each
elements inhabits its own node. Having multiple elements per allocated 
chunk of memory
does not look feasible within the current framework.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo