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

Cory Nelson wrote:

On Thu, Nov 20, 2008 at 9:18 AM, wrote:

...

...

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

fgmailbox escribió: 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