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: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2008-11-23 10:09:34

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.

As Daniel has mentioned, T-trees seem appropriate for in-memory DB (some 
popular memory DB use them). I've been thinking in those data structures 
for Intrusive these days but B-trees, B+-trees and T-trees require some 
well-thought ideas because each node store several values and that might 
  complicate the implementation of multi-index containers. Take in care 
that those containers also require copy/move constructible values (they 
transfer values between nodes to maintain their invariants) and 
copying/moving will require fixing a lot of pointers from other indexes.

A STL-like T-tree-based associative container would be also a great idea 
for a boost library. Maybe we could reuse multiindex or intrusive t-tree 
code to implement it.

Regards,

Ion