Boost logo

Boost Users :

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:
> 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.



Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at