[multiindex] Why not to add B+Tree index to multiIndex?
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 . 2008-11-20 fgmailbox
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? Joaquín M López Mun~oz Telefónica, Investigación y Desarrollo
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?
My understanding is that B-tree variants are better for secondary storage lookups and T-trees are better for in-memory lookup. A quick reference would be http://en.wikipedia.org/wiki/T-tree . I know that isn't a definitive source, but I would think it would be a good place to start looking. This e-mail transmission contains information that is confidential and may be privileged. It is intended only for the addressee(s) named above. If you receive this e-mail in error, please do not read, copy or disseminate it in any manner. If you are not the intended recipient, any disclosure, copying, distribution or use of the contents of this information is prohibited. Please reply to the message immediately by informing the sender that the message was misdirected. After replying, please erase it from your computer system. Your assistance in correcting this error is appreciated.
On Thu, Nov 20, 2008 at 9:18 AM, <joaquin@tid.es> 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. -- Cory Nelson
Cory Nelson wrote:
On Thu, Nov 20, 2008 at 9:18 AM, <joaquin@tid.es> 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
Ion Gaztañaga escribió:
Cory Nelson wrote:
On Thu, Nov 20, 2008 at 9:18 AM, <joaquin@tid.es> 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
participants (5)
-
Cory Nelson -
Dilts, Daniel D. -
fgmailbox -
Ion Gaztañaga -
joaquin＠tid.es