In a B- tree you can store both keys and data in the internal/leaf nodes. But in a B+ tree you have to store the data in the leaf nodes only. Is there any advantage of doing the above in a B+ tree? Why not use B- trees instead of B+ trees everywhere? As intuitively they seem much faster. I mean why do you need to replicate the key(data) in a B+ tree?
+7
A:
Define "much faster". Asymptotically they're about the same. The differences lie in how they make use of secondary storage. The Wikipedia articles on B-trees and B+trees look pretty trustworthy.
Charlie Martin
2009-05-15 18:45:07
A:
One possible use of B+ tress is that it is suitable for situations where the tree grows so large that it need not fit into available memory. Thus, you'd generally expect to be doing multiple I/O's. Often it does happen that a B+ tree is used even when it in fact fits into memory, and then your cache manager might keep it there permanently. But this is a special case, not the general one, and caching policy is a separate from B+ tree maintenance as such.
Also, in a B+ tree, the leaf pages are linked together in a linked list (or doubly-linked list), which optimizes traversals (for range searches, sorting, etc.). So the number of pointers is a function of the specific algorithm that is used.
stack programmer
2009-05-15 18:51:16
What about B- trees?
Malfist
2009-05-15 18:54:05
This is in answer to the question that why should we not use B-trees instead of B+ trees everywhere :)
stack programmer
2009-05-15 19:20:40
But you only described one side, as far as we know, with your answer b-trees could function exactly the same way. The OP asked to explain the differences and you only talked about one and not the other. You can't have a venn diagram with one circle!
Malfist
2009-05-15 20:00:49
+7
A:
The principal advantage of B+ trees over B trees is they allow you to in pack more pointers to other nodes by removing pointers to data, thus increasing the fanout and potentially decreasing the depth of the tree.
The disadvantage is that there are no early outs when you might have found a match in an internal node. But since both data structures have huge fanouts, the vast majority of your matches will be on leaf nodes anyway, making on average the B+ tree more efficient.
Vic E
2009-05-15 19:05:43
+1
A:
B+ Trees are especially good in block-based storage (eg: hard disk). with this in mind, you get several advantages, for example (from the top of my head):
high fanout / low depth: that means you have to get less blocks to get to the data. with data intermingled with the pointers, each read gets less pointers, so you need more seeks to get to the data
simple and consistent block storage: an inner node has N pointers, nothing else, a leaf node has data, nothing else. that makes it easy to parse, debug and even reconstruct.
high key density means the top nodes are almost certainly on cache, in many cases all inner nodes get quickly cached, so only the data access has to go to disk.
Javier
2009-05-15 19:52:02
+3
A:
B+Trees are much easier and higher performing to do a full scan, as in look at every piece of data that the tree indexes, since the terminal nodes form a linked list. To do a full scan with a B-Tree you need to do a full tree traversal to find all the data.
B-Trees on the other hand can be faster when you do a seek (looking for a specific piece of data by key) especially when the tree resides in RAM or other non-block storage. Since you can elevate commonly used nodes in the tree there are less comparisons required to get to the data.
Jeff Mc
2009-05-15 20:33:12
A:
In B+ Tree, since only pointers are stored in the internal nodes, their size becomes significantly smaller than the internal nodes of B tree (which store both data+key). Hence, the indexes of the B+ tree can be fetched from the external storage in a single disk read, processed to find the location of the target. If it has been a B tree, a disk read is required for each and every decision making process. Hope I made my point clear! :)