C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  What about B+Tree in STL? Goto page 1, 2  Next          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Ema Guest Posted: Thu Feb 23, 2006 1:06 pm    Post subject: What about B+Tree in STL? Hi, after reading Alexandrescu's"Maps with Expensive Keys", I had a flash: Why isn't there a B+Tree implementation in STL? Correct me if I'm wrong, but isn't std::map implemented just like a 2-way balanced tree or even a binary tree? Wouldn't be better to have a B+Tree template too? Thanks in advance, Ema. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Guest Posted: Thu Feb 23, 2006 7:06 pm    Post subject: Re: What about B+Tree in STL? Ema wrote: Quote: Hi, after reading Alexandrescu's"Maps with Expensive Keys", I had a flash: Why isn't there a B+Tree implementation in STL? Because no one put it in? Because the STL algorithms will work perfectly with your own implementation, if BTree::iterators is defined correctly (or if an independent BTree_iterator class is written). Remember, the STL was designed to be extensible, not complete. Quote: Correct me if I'm wrong, but isn't std::map implemented just like a 2-way balanced tree or even a binary tree? The latter is one possible implementation which meets the STL requirements. AFAIK, most STL implementations use some form of red-black trees. I can imagine some optimizations for small keys, 'int' keys, etc. I'm not sure if you can rebalance the tree on every modification and still meet the complexity requirements. HTH, Michiel Salters [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Daniel K. O. Guest Posted: Fri Feb 24, 2006 3:06 am    Post subject: Re: What about B+Tree in STL? Michiel.Salters (AT) tomtom (DOT) com escreveu: Quote: AFAIK, most STL implementations use some form of red-black trees. I can imagine some optimizations for small keys, 'int' keys, etc. I'm not sure if you can rebalance the tree on every modification and still meet the complexity requirements. I did implement an AVL tree for GNU libstdc++ v3's map (http://stlavlmap.sourceforge.net). Some people told me it doesn't meet the complexity requirements for insertion with hints, but for most of my needs it's usually faster than the provided std::map - and the good thing is that the client code remains untouched. So even if a B Tree may not be suited to be the standard implementation, it may still be faster for some applications. ---- Daniel K. O. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ema Guest Posted: Fri Feb 24, 2006 10:06 am    Post subject: Re: What about B+Tree in STL? Michiel.Salters (AT) tomtom (DOT) com ha scritto: Quote: Ema wrote: Hi, after reading Alexandrescu's"Maps with Expensive Keys", I had a flash: Why isn't there a B+Tree implementation in STL? Because no one put it in? Because the STL algorithms will work perfectly with your own implementation, if BTree::iterators is defined correctly (or if an independent BTree_iterator class is written). Remember, the STL was designed to be extensible, not complete. Correct me if I'm wrong, but isn't std::map implemented just like a 2-way balanced tree or even a binary tree? The latter is one possible implementation which meets the STL requirements. AFAIK, most STL implementations use some form of red-black trees. I can imagine some optimizations for small keys, 'int' keys, etc. I'm not sure if you can rebalance the tree on every modification and still meet the complexity requirements. HTH, Michiel Salters Well the point is about algorithmic performance. All we know a B+Tree (with more than 2 refs for node) is much faster than a std::map; so why not think to include one implementation in future STL? I think this would be much more appriciated than other things... Bye, Ema. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Le Chaud Lapin Guest Posted: Fri Feb 24, 2006 10:06 am    Post subject: Re: What about B+Tree in STL? Daniel K. O. wrote: Quote: I did implement an AVL tree for GNU libstdc++ v3's map (http://stlavlmap.sourceforge.net). Some people told me it doesn't meet the complexity requirements for insertion with hints, but for most of my needs it's usually faster than the provided std::map - and the good thing is that the client code remains untouched. What are hints and why would yours not meet complexity requirements? -Le Chaud Lapin- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Guest Posted: Fri Feb 24, 2006 11:06 am    Post subject: Re: What about B+Tree in STL? Le Chaud Lapin wrote: Quote: Daniel K. O. wrote: I did implement an AVL tree for GNU libstdc++ v3's map (http://stlavlmap.sourceforge.net). Some people told me it doesn't meet the complexity requirements for insertion with hints, but for most of my needs it's usually faster than the provided std::map - and the good thing is that the client code remains untouched. What are hints and why would yours not meet complexity requirements? std::map::insert has an overload which takes an iterator. The intent is that you can insert N presorted items in O(N) time if you already know where they'll go. Each hint is used to avoid a O(log N) search for the insertion point, if it's correct. If the AVL tree can't deduce the hinted insertion point in O(1), it will always fall back to a O(log N) unhinted insertion. HTH, Michiel Salters [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Guest Posted: Fri Feb 24, 2006 11:06 am    Post subject: Re: What about B+Tree in STL? Ema wrote: Quote: Michiel.Salters (AT) tomtom (DOT) com ha scritto: Ema wrote: Hi, after reading Alexandrescu's"Maps with Expensive Keys", I had a flash: Why isn't there a B+Tree implementation in STL? Because no one put it in? HTH, Michiel Salters Well the point is about algorithmic performance. All we know a B+Tree (with more than 2 refs for node) is much faster than a std::map; so why not think to include one implementation in future STL? I think this would be much more appriciated than other things... Perhaps, but there's no B+Tree container in boost. (www.boost.org). That suggests to me that no one actually cared enough to make one implementation available. However, if you have one available, and you would like to share it with the world, please check the boost website to see if they are willing to include it. Regards, Michiel Salters [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Daniel K. O. Guest Posted: Fri Feb 24, 2006 3:06 pm    Post subject: Re: What about B+Tree in STL? Michiel.Salters (AT) tomtom (DOT) com escreveu: Quote: correct. If the AVL tree can't deduce the hinted insertion point in O(1), it will always fall back to a O(log N) unhinted insertion. Well, the "hint handling" code is not in the AVL implementation, but above it (it remained untouched in my implementation). Seems the problem is that an AVL tree may perform more rotations to keep its balancing constraints than an RB tree. But I don't have yet knowledge to really confirm this, and don't know how to make synthetic benchmarks to show the hinted insertion being any different between both implementations. I only know that for everything else the AVL tree looks faster. --- Daniel K. O. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top peter koch larsen Guest Posted: Fri Feb 24, 2006 3:06 pm    Post subject: Re: What about B+Tree in STL? Ema wrote: Quote: Hi, after reading Alexandrescu's"Maps with Expensive Keys", I had a flash: Why isn't there a B+Tree implementation in STL? Correct me if I'm wrong, but isn't std::map implemented just like a 2-way balanced tree or even a binary tree? std::map is a balanced tree. If it was not, the performance guarantees could not have been met. Quote: Wouldn't be better to have a B+Tree template too? Why? Contrary to your belief, a B-tree (of any variety) is not faster than a std::map. B-trees are useful for reducing the number of disk-accesses in a structure that resides (at least conceptually as it could be cached to memory) on secondary storage. The number of comparisons made in a B-tree is not less than for a std::map and the number of "pointer traversals" is also the same. For a normal map which resides in memory you would thus gain nothing*: only if paging should begin to set in and your map gets paged would the B-tree solution begin to show a real advantage and in that case you should reconsider your design anyway. /Peter *: Local cpu-caches might benifit from the better locality provided, but I doubt that this will have a non-neglectible effect in real life. For that we need entirely new structures where the object is "put apart" when it gets inserted into the datastructure and reconstructed as it is taken out. That would mean that we would not be able to use our normal iterator concept anymore. Quote: Thanks in advance, Ema. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Antoun Kanawati Guest Posted: Fri Feb 24, 2006 3:06 pm    Post subject: Re: What about B+Tree in STL? Ema wrote: Quote: Well the point is about algorithmic performance. All we know a B+Tree (with more than 2 refs for node) is much faster than a std::map; so why not think to include one implementation in future STL? I think this would be much more appriciated than other things... Interesting assertion. It is my recollection that the B+tree's advantage is in supporting persistence storage schemes. For in-memory work, the self-balancing binary search tree is simpler and better. Note that textbook presentations of the B+tree show linear scans of the key lists in nodes. Since the key-lists are sorted, we can assume that a logarithmic search is possible on them (i.e.: binary search). But, if you have an AVL or red-black tree, you have all of that already, and a much simpler data structure. -- A. Kanawati [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Marek Vondrak Guest Posted: Fri Feb 24, 2006 3:06 pm    Post subject: Re: What about B+Tree in STL? Quote: I did implement an AVL tree for GNU libstdc++ v3's map (http://stlavlmap.sourceforge.net). Some people told me it doesn't meet the complexity requirements for insertion with hints, but for most of my needs it's usually faster than the provided std::map. This is very interesting to hear since AVL trees are theoretically worse than red-black trees used by the libstdc++'s std::map. Whenever a DELETE is performed on an AVL tree, one might be forced to do up to O( log N ) rotations in order to rebalance the tree. Contrary, red-black trees are guaranteed to be rebalanced by at most 2 rotations. -- Marek [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top fandoras Guest Posted: Fri Feb 24, 2006 5:06 pm    Post subject: Re: What about B+Tree in STL? Ema schrieb: Quote: Well the point is about algorithmic performance. All we know a B+Tree (with more than 2 refs for node) is much faster than a std::map; so why not think to include one implementation in future STL? I think this would be much more appriciated than other things... Maybe i'm blind at the moment... but... The algorithmic performance of a B[+-]Tree should be bader then of a binary tree implementation (ignoring balancing...). A binary Tree replace some of the O(log(n)) searching with a linear search O(n) while checking the more then 2 refes in a node. That only makes sence if the time required for the linear search is much lower then the time to access a node, e.g. if you have to load such a node from a disk. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top John Potter Guest Posted: Sat Feb 25, 2006 12:06 pm    Post subject: Re: What about B+Tree in STL? On 24 Feb 2006 09:37:45 -0500, "Daniel K. O." <danielko (AT) abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijk (DOT) com> wrote: Quote: Well, the "hint handling" code is not in the AVL implementation, but above it (it remained untouched in my implementation). Seems the problem is that an AVL tree may perform more rotations to keep its balancing constraints than an RB tree. But I don't have yet knowledge to really confirm this, and don't know how to make synthetic benchmarks to show the hinted insertion being any different between both implementations. I only know that for everything else the AVL tree looks faster. Yes an AVL tree may perform more rotations to rebalance after an erase than an RB tree. See any good algorithms book (Corman et al). However, the requirements are amortized across all possible locations. Because of the amortization, the AVL tree will still do a constant number of operations after erase. The constant may be greater than that for the RB, but it will still be a constant. That has nothing to do with the hints and rebalance after insert is on par with the RB. It does satisfy the standard. John [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top John Potter Guest Posted: Sat Feb 25, 2006 12:06 pm    Post subject: Re: What about B+Tree in STL? On 24 Feb 2006 09:31:34 -0500, Antoun Kanawati <antounk (AT) comcast (DOT) net> wrote: Quote: Ema wrote: Well the point is about algorithmic performance. All we know a B+Tree (with more than 2 refs for node) is much faster than a std::map; so why not think to include one implementation in future STL? I think this would be much more appriciated than other things... Interesting assertion. It is my recollection that the B+tree's advantage is in supporting persistence storage schemes. For in-memory work, the self-balancing binary search tree is simpler and better. With modern multilevel cache, locality of reference may shift the scales to the B-tree. Quote: Note that textbook presentations of the B+tree show linear scans of the key lists in nodes. Since the key-lists are sorted, we can assume that a logarithmic search is possible on them (i.e.: binary search). But, if you have an AVL or red-black tree, you have all of that already, and a much simpler data structure. Not much difference in simplicity. An RB tree is just a binary implementation of a forward balancable B-tree. The real question is can the B-tree be implemented to meet the requirements of the associative containers? Validity and size of iterators is a problem. OTOH, if one takes the view that iterators should become invalid at the drop of a hat like for vector, it might be a useful addition. John [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top John Potter Guest Posted: Sat Feb 25, 2006 12:06 pm    Post subject: Re: What about B+Tree in STL? {Note that this thread is beginning to drift away from C++ into something that would be more appropriate in a groups specialising in algorithms. -mod} On 24 Feb 2006 09:27:51 -0500, "Marek Vondrak" <none (AT) none (DOT) com> wrote: Quote: I did implement an AVL tree for GNU libstdc++ v3's map (http://stlavlmap.sourceforge.net). Some people told me it doesn't meet the complexity requirements for insertion with hints, but for most of my needs it's usually faster than the provided std::map. This is very interesting to hear since AVL trees are theoretically worse than red-black trees used by the libstdc++'s std::map. Whenever a DELETE is performed on an AVL tree, one might be forced to do up to O( log N ) rotations in order to rebalance the tree. Contrary, red-black trees are guaranteed to be rebalanced by at most 2 rotations. Actually, it is 3, see Corman. So, the worst that can happen on a single erase is worse for an AVL than an RB. The worst height of an AVL tree is around 1.4 times the best height for given number of nodes while that for an RB is 2 times. Search may be better for an AVL than for an RB. All of this is about worst things which usually has nothing to do with what really happens in the application. I have seen each outperform the other in the same application with different data. John [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Goto page 1, 2  Next Page 1 of 2   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.