What are the differences between B trees and B+ trees?

Question

In a b-tree you can store both keys and data in the internal and 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?

Ailee

I think what they're saying is "B-Tree" vs. B+-Tree. They mean a hyphen, not a minus sign. – Irrigate

Answer 1

The image below helps show the differences between B+ trees and B trees.

Advantages of B+ trees:

• Because B+ trees don't have data associated with interior nodes, more keys can fit on a page of memory. Therefore, it will require fewer cache misses in order to access data that is on a leaf node.
• The leaf nodes of B+ trees are linked, so doing a full scan of all objects in a tree requires just one linear pass through all the leaf nodes. A B tree, on the other hand, would require a traversal of every level in the tree. This full-tree traversal will likely involve more cache misses than the linear traversal of B+ leaves.

Advantage of B trees:

• Because B trees contain data with each key, frequently accessed nodes can lie closer to the root, and therefore can be accessed more quickly.

---

Gamelan

Is their any constrain on number of entries in leaf node?? – Breakfast

@Breakfast Good question! Yes. A hard drive accesses a minimum of a page of memory at a time, so we want to fit all the pointers in a single page of memory. We want to require only one disk read per leaf access, so we don't want to assign more than a page size of pointers to a leaf. If we fill a leaf with a page size of pointers, and then we want to add another pointer to this leaf, we create two children of this node, and give half of the leaf's pointers to each new child. Of course, there may be some reshuffling to ensure the tree's height is kept to a minimum. Does this help? – Gamelan

the last pointer of each leaf node of B-tree should point to the next leaf node, right? – Sanitarian

So sorry for bumping such an old thread, but @Babyburger's comment about how camino's comment was correct is not actually true; a B-Tree does not, in fact, have connected leaf nodes. A B+, sure. – Capreolate

Thanks for the excellent answer, what is a use-case when a full-scan of the objects would be needed in a B/B+ tree in a database context? Since it's primarily used for indexing, searches would barely ever need to scan the entire tree right and instead traverse via the index path, is that correct? – Felon

@Felon From DbSystemConcepts 6 (457): Large objects are often represented using B+-tree file organizations. B+-tree file organizations permit us to >read an entire object<, or specified byte ranges in the object, as well as to insert and delete parts of the object. B+Tree file organization is one of extensions for this data structure. I think this can be one of use cases related to your question. – Jeffiejeffrey

The chaining of leaf nodes for B+ trees is of questionable usefulness and should generally be ignored as property. Many databases will still traverse from the root to be able to pre-fetch the leaf pages as seek time still often dominates the processing (see e.g. Write-Optimized B-Trees section 3.1.In general, B+ trees consume less space in total and require less height than corresponding B trees. – Marinara

Answer 2

The principal advantage of B+ trees over B trees is they allow you to pack in 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.

Symonds

I prefer Jeff's answer, because it emphasizes the difference in efficiency when doing a full scan. – Gamelan

I am really confused because traversing a b-tree using an in-order traversal will read all of the values in sorted order in O(n) time. If each tree node is optimally sized for the physical page size, it seems like things don't get any more optimal. Conversely, the cost to get to the first (smallest) value in a b+tree is O(log n) and then to walk through every leaf is O(n) so the total cost is O(log n + n). This is more work and more disk reads which makes sense because the tree has all this extra data in it. I don't get it. – Allistir

What would it be another word for 'fanout' in the above sentence? – Immune

@JorgeBucaran fanout = number of edges coming out of a node – Valdemar

Answer 3

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.

Pattern

Would you agree then a B+ tree would be used for situations in which there may be a sequential read across all of the data thus be able to go across the leaves. Whereas the B tree would be ideal for Random Access situations? – Gaylene

@Gaylene very curious about your question as well – Felon

Answer 4

1. In a B tree search keys and data are stored in internal or leaf nodes. But in a B+-tree data is stored only in leaf nodes.
2. Full scan of a B+ tree is very easy because all data are found in leaf nodes. Full scan of a B tree requires a full traversal.
3. In a B tree, data may be found in leaf nodes or internal nodes. Deletion of internal nodes is very complicated. In a B+ tree, data is only found in leaf nodes. Deletion of leaf nodes is easy.
4. Insertion in B tree is more complicated than B+ tree.
5. B+ trees store redundant search keys but B tree has no redundant value.
6. In a B+ tree, leaf node data is ordered as a sequential linked list but in a B tree the leaf node cannot be stored using a linked list. Many database systems' implementations prefer the structural simplicity of a B+ tree.

Beberg

Answer 5

Example from Database system concepts 5th

B+-tree

corresponding B-tree

Sanitarian

I don't think a B-Tree has links to the node's children. For instance form the Clearview bucket to the Mianus Bucket. It wouldn't make much sense to do that anyway because in between the two you have the Downtown bucket which much be searched in the event you want to do an Index Scan in a B-tree (requires backtracking). Where did you get this? – Geothermal

@EvanCarroll Database system concepts 5th, maybe you need to confirm with the author :) – Sanitarian

Answer 6

Adegoke A, Amit

I guess one crucial point you people are missing is difference between data and pointers as explained in this section.

Pointer : pointer to other nodes.

Data :- In context of database indexes, data is just another pointer to real data (row) which reside somewhere else.

Hence in case of B tree each node has three information keys, pointers to data associated with the keys and pointer to child nodes.

In B+ tree internal node keep keys and pointers to child node while leaf node keep keys and pointers to associated data. This allows more number of key for a given size of node. Size of node is determined mainly by block size.

Advantage of having more key per node is explained well above so I will save my typing effort.

Mansard

Answer 7

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.

Turpeth

mostly for in-memory trees; but there are other popular options, like red-black trees, skip lists, and such. – Turpeth

B-trees are also designed for efficient block-based storage, limiting the asymptotic number of node accesses. Otherwise, if using a memory-like storage medium with random access, one can use a self-balancing binary tree such as a red-black tree to achieve better results. – Individualize

shouldn't your first point say "less seeks" rather than "more seeks". Smaller depth -> less seeks – Subinfeudate

@Jesse: high fanout=> low depth => less seeks, but mixing data and pointers means less pointers => low fanout => more depth => more seeks – Turpeth

@Turpeth What do you mean by 'mixing data with pointers'? How does that works? See Q5d in this exam paper. This is the image of B+ Trees that I have in my head. tcd.ie/Local/Exam_Papers/2010/XC/XCS20311.pdf – Marchland

@AdegokeA: a B+tree has two kinds of nodes: inner nodes with only keys and pointers, no data; and leaf nodes, with data and no pointers. that allows for maximum number of keys on each inner node. if you store data on an inner node, then you can fit less pointers and your tree gets taller. – Turpeth

Answer 8

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.

Merkel

I agree with Charlie. Since one node of a B-Tree represents one secondary memory page or block, the passage from one node to another requires a time consuming page-change. – Wolters

Answer 9

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! :)

Scop

Answer 10

**

The major drawback of B-Tree is the difficulty of Traversing the keys sequentially. The B+ Tree retains the rapid random access property of the B-Tree while also allowing rapid sequential access

** ref: Data Structures Using C// Author: Aaro M Tenenbaum

http://books.google.co.in/books?id=X0Cd1Pr2W0gC&pg=PA456&lpg=PA456&dq=drawback+of+B-Tree+is+the+difficulty+of+Traversing+the+keys+sequentially&source=bl&ots=pGcPQSEJMS&sig=F9MY7zEXYAMVKl_Sg4W-0LTRor8&hl=en&sa=X&ei=nD5AUbeeH4zwrQe12oCYAQ&ved=0CDsQ6AEwAg#v=onepage&q=drawback%20of%20B-Tree%20is%20the%20difficulty%20of%20Traversing%20the%20keys%20sequentially&f=false

Scottscotti

This should have been the correct answer. In short: Locality of reference. – Machado

Answer 11

The primary distinction between B-tree and B+tree is that B-tree eliminates the redundant storage of search key values.Since search keys are not repeated in the B-tree,we may not be able to store the index using fewer tree nodes than in corresponding B+tree index.However,since search key that appear in non-leaf nodes appear nowhere else in B-tree,we are forced to include an additional pointer field for each search key in a non-leaf node. Their are space advantages for B-tree, as repetition does not occur and can be used for large indices.

Yepez

Interesting, the thoughts about repetition are unique among the replies here and make more sense than in-order traversal of b+tree being more efficient than in-order traversal of a b-tree. As far as I can tell, that's either not quite right, or not the whole story as in order traversal of a b-tree is O(n) and finding the smallest node in a b+tree is O(log n) and then traversing each leaf is O(n) in addition to that. However, if you were indexing something with a small range of values, like a boolean field, the b+tree makes a lot more sense than a b-tree because of its duplicate handling. – Allistir

Answer 12

Take one example - you have a table with huge data per row. That means every instance of the object is Big.

If you use B tree here then most of the time is spent scanning the pages with data - which is of no use. In databases that is the reason of using B+ Trees to avoid scanning object data.

B+ Trees separate keys from data.

But if your data size is less then you can store them with key which is what B tree does.

Georgetta

"If you use B tree here then most of the time is spent scanning the pages with data" - not necessary. B-tree nodes can keep only "pointers" to data on disc, not data itself. – Demoiselle

Answer 13

One possible use of B+ trees is that it is suitable for situations where the tree grows so large that it does not fit into available memory. Thus, you'd generally expect to be doing multiple I/O's.
It does often 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.

Hundley

This is in answer to the question that why should we not use B-trees instead of B+ trees everywhere :) – Hundley

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! – Chi

Answer 14

A B+tree is a balanced tree in which every path from the root of the tree to a leaf is of the same length, and each nonleaf node of the tree has between [n/2] and [n] children, where n is fixed for a particular tree. It contains index pages and data pages. Binary trees only have two children per parent node, B+ trees can have a variable number of children for each parent node

Gragg

Just for clarity, B trees are not binary trees. In fact, B trees and B+trees are closer to each other in construction and usage than binary trees. The wiki articles can help in clearing the definitions - B+Tree, B Tree and Binary Tree – Laurustinus