database B树和B+树有什么区别？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/870218/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What are the differences between B trees and B+ trees?
提问by simplfuzz
In a b-treeyou can store both keys and data in the internal and leaf nodes, but in a b+ treeyou have to store the data in the leaf nodes only.
在b 树中，您可以在内部节点和叶节点中存储键和数据，但在b+ 树中，您必须仅将数据存储在叶节点中。
Is there any advantage of doing the above in a b+ tree?
在 b+ 树中执行上述操作有什么好处吗？
Why not use b-trees instead of b+ trees everywhere, as intuitively they seem much faster?
为什么不到处使用 b 树而不是 b+ 树，因为直观上它们看起来要快得多？
I mean, why do you need to replicate the key(data) in a b+ tree?
我的意思是，为什么需要在 b+ 树中复制密钥（数据）？
回答by Rose Perrone
The image below helps show the differences between B+ trees and B trees.
下图有助于显示 B+ 树和 B 树之间的差异。
Advantages of B+ trees:
B+树的优点：
- 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.
- 因为 B+ 树没有与内部节点关联的数据，所以一页内存可以容纳更多的键。因此，为了访问叶节点上的数据，将需要更少的缓存未命中。
- B+ 树的叶节点是链接的，因此对树中的所有对象进行完整扫描只需要一次线性遍历所有叶节点。另一方面，AB 树需要遍历树中的每一层。这种全树遍历可能比 B+ 叶的线性遍历涉及更多的缓存未命中。
Advantage of B trees:
B树的优点：
- Because B trees contain data with each key, frequently accessed nodes can lie closer to the root, and therefore can be accessed more quickly.
- 因为 B 树包含每个键的数据，经常访问的节点可以更靠近根，因此可以更快地访问。
回答by Vic E
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.
B+ 树相对于 B 树的主要优点是它们允许您通过删除指向数据的指针来打包更多指向其他节点的指针，从而增加扇出并可能降低树的深度。
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.
缺点是当您可能在内部节点中找到匹配项时不会提前退出。但由于这两种数据结构都有巨大的扇出，无论如何，绝大多数匹配都将在叶节点上，从而使 B+ 树的平均效率更高。
回答by Jeff Mc
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 更容易和更高的执行完整扫描，就像查看树索引的每条数据一样，因为终端节点形成一个链表。要使用 B 树进行完整扫描，您需要进行完整的树遍历以找到所有数据。
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.
另一方面，当您进行查找（通过键查找特定数据）时，B 树可以更快，尤其是当树驻留在 RAM 或其他非块存储中时。由于您可以提升树中的常用节点，因此获取数据所需的比较较少。
回答by androidcodehunter
- 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.
- 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.
- 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.
- Insertion in B tree is more complicated than B+ tree.
- B+ trees store redundant search keys but B tree has no redundant value.
- 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.
- 在 B 树中，搜索键和数据存储在内部或叶节点中。但是在 B+ 树中，数据仅存储在叶节点中。
- 完全扫描 B+ 树非常容易，因为所有数据都可以在叶节点中找到。B 树的全扫描需要全遍历。
- 在 B 树中，数据可以在叶节点或内部节点中找到。删除内部节点非常复杂。在 B+ 树中，数据只能在叶节点中找到。删除叶节点很容易。
- B树中的插入比B+树更复杂。
- B+ 树存储冗余搜索键，但 B 树没有冗余值。
- 在 B+ 树中，叶节点数据按顺序链表排序，但在 B 树中，叶节点不能使用链表存储。许多数据库系统的实现更喜欢 B+ 树的结构简单性。
回答by camino
Example from Database system concepts 5th
数据库系统概念第 5 个示例
B+-tree
B+树
corresponding B-tree
对应的B树
回答by Saket
Adegoke A, Amit
Adegoke A，阿米特
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.
因此，在 B 树的情况下，每个节点都有三个信息键，指向与键关联的数据的指针和指向子节点的指针。
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.
在 B+ 树中，内部节点保存键和指向子节点的指针，而叶节点保存键和指向关联数据的指针。对于给定的节点大小，这允许更多数量的键。节点的大小主要由块大小决定。
Advantage of having more key per node is explained well above so I will save my typing effort.
每个节点有更多键的优势在上面已经很好地解释了，所以我将节省我的打字工作。
回答by Charlie Martin
回答by Javier
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):
B+ 树尤其适用于基于块的存储（例如：硬盘）。考虑到这一点，您将获得几个优势，例如（从我的头顶）：
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.
高扇出/低深度：这意味着您必须获得更少的块才能获取数据。数据与指针混合在一起，每次读取获得的指针较少，因此您需要更多的尝试来获取数据
简单一致的块存储：内部节点有 N 个指针，没有别的，叶节点有数据，没有别的。这使得解析、调试甚至重建变得容易。
高键密度意味着顶级节点几乎肯定在缓存中，在许多情况下，所有内部节点都会被快速缓存，因此只有数据访问必须转到磁盘。
回答by VS7
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! :)
在 B+ 树中，由于内部节点只存储指针，因此它们的大小明显小于 B 树的内部节点（同时存储数据+密钥）。因此，可以在单次磁盘读取中从外部存储中获取 B+ 树的索引，进行处理以找到目标的位置。如果它是 B 树，则每个决策过程都需要读取磁盘。希望我说清楚了！:)
回答by Kapil Kumar
**
**
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
B-Tree 的主要缺点是难以按顺序遍历键。B+ Tree 保留了 B-Tree 的快速随机访问特性，同时也允许快速顺序访问
** ref: Data Structures Using C// Author: Aaro M Tenenbaum
** 参考：使用 C 的数据结构// 作者：Aaro M Tenenbaum
