How are paged binary trees different from AVL trees and/or B-trees?
+1
A:
I suggest reading the excellent Wikipedia articles on the topic.
Very briefly:
- AVL trees are binary search trees (i.e. binary trees used to impose an ordering on its elements). The difference is that AVL trees implement a self-balancing strategy to distribute the nodes evenly as to reduce the maximum depth of the tree.
- B trees are a generalization of binary search trees, i.e. they are no longer binary.
Konrad Rudolph
2010-04-29 07:27:17
+2
A:
In spite of the different structure of AVL and B-tree as stated by Konrad, usage of AVL and B-tree is also different, I think. B-tree generally used to implement indexing. Purpose of employing B-tree is to reduce disk I/O, while data of AVL-tree often resists totally in memory instead of partially in memory partially on disk like B-tree. Purpose of AVL-tree is to avoid the appearance of left/right branch tree in some extreme situation ensuring a perfect O(logn) time complexity when doing search operation.
Summer_More_More_Tea
2010-04-29 07:36:11
Historically, you’re right. However, “recent” developments in hardware have shifted the balance massively in favour of B trees, due to cache locality issues. In fact, B trees that use cache lines optimally tend to outperform binary trees everywhere. For more information, have a look at the excellent study at http://idlebox.net/2007/stx-btree/, in particular the benchmarks: http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html
Konrad Rudolph
2010-04-29 08:48:36
@Konrad: Thanx:-)
Summer_More_More_Tea
2010-04-29 13:05:13