在b-树中,您可以将键和数据存储在内部节点和叶节点中,但在b+树中,您必须仅将数据存储在叶节点中。

在b+树中这样做有什么好处吗?

为什么不在所有地方都使用b-树而不是b+树,因为直觉上它们看起来更快?

我的意思是,为什么需要在b+树中复制键(数据)?


当前回答

B+树是一种平衡的树,其中从树的根到叶子的每条路径都是相同的长度,树的每个非叶子节点都有[n/2]到[n]个子节点,其中n对于特定的树是固定的。它包含索引页和数据页。 二叉树的每个父节点只有两个子节点,而B+树的每个父节点可以有不同数量的子节点

其他回答

在B+树中,由于只有指针存储在内部节点中,因此它们的大小明显小于B树的内部节点(存储数据+键)。 因此,B+树的索引可以在一次磁盘读取中从外部存储中提取,处理后找到目标的位置。如果它是一个B树,那么每个决策过程都需要读取磁盘。希望我把我的观点讲清楚了!:)

Adegoke A, Amit

我想你们忽略的一个关键点是数据和指针之间的区别,就像本节中解释的那样。

指针:指向其他节点的指针。

数据:—在数据库索引的上下文中,数据只是另一个指向其他地方的真实数据(行)的指针。

因此在B树的情况下,每个节点都有三个信息键,指向与键相关的数据的指针和指向子节点的指针。

在B+树中,内部节点保存指向子节点的键和指针,而叶节点保存指向相关数据的键和指针。这允许为给定大小的节点提供更多的键数。节点大小主要由块大小决定。

每个节点拥有更多键的好处已经在上面解释过了,这样可以节省我的输入工作量。

由于终端节点形成了一个链表,B+树更容易进行全面扫描,而且性能更高,可以查看树索引的每一块数据。要使用B-Tree进行完整扫描,您需要进行完整的树遍历以查找所有数据。

另一方面,当您执行seek(按键查找特定数据段)时,B-Trees可以更快,特别是当树驻留在RAM或其他非块存储中时。由于可以提升树中常用的节点,因此获取数据所需的比较较少。

**

B-Tree的主要缺点是遍历键的难度 按顺序。B+树保留了的快速随机访问属性 b -树,同时也允许快速顺序访问

** 参考:Data Structures Using C//作者: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

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.