查看“︁B+树”︁的源代码

{{noteTA
|G1=IT
}}
{{Infobox data structure
|name=B+树
|type=[[树 (数据结构)|树]]
|space_avg= <math>O(n)</math>
|space_worst= <math>O(n)</math>
|search_avg= <math>O(\log n)</math>
|search_worst= <math>O(\log n)</math>
|insert_avg= <math>O(\log n)</math>
|insert_worst= <math>O(\log n)</math>
|delete_avg= <math>O(\log n)</math>
|delete_worst= <math>O(\log n)</math>
}}
[[File:Bplustree.png|thumb|400px|right|把键1-7连接到值 d<sub>1</sub>-d<sub>7</sub> 的B+树。链表（红色）用于快速顺序遍历叶子节点。树的分叉因子 <math> b </math>=4。]]
'''B+树'''（{{lang-en|B+ tree}}）是一种[[树 (数据结构)|树数据结构]]，通常用于[[数据库]]和[[操作系统]]的[[文件系统]]中。B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入，这与[[二叉树]]恰好相反。

B+树在节点访问时间远远超过节点内部访问时间的时候，比可作为替代的实现有着实在的优势。这通常在多数节点在[[次级存储]]比如[[硬盘]]中的时候出现。通过最大化在每个[[内部节点]]内的[[子节点]]的数目减少树的高度，平衡操作不经常发生，而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的[[磁盘块]]或近似的大小。

B+樹背后的想法是内部节点可以有在预定范围内的可变数目的子节点。因此，B+树不需要像其他[[自平衡二叉查找树]]那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。例如，在 2-3 B 树（常简称为'''2-3 树'''）中，每个内部节点只可能有 2 或 3 个子节点。如果节点有无效数目的子节点则被当作处于违规状态。

B+树的创造者[[Rudolf Bayer]]没有解释「B」的意義，最常见的观点是代表「平衡」（balanced）或其名字「Bayer」。

== 节点结构 ==

在B+树中的节点通常被表示为一组有序的元素和子指针。如果此B+树的阶数是m，则除了根之外的每个节点都包含最少 <math> \lfloor m/2 \rfloor </math> 个元素最多 <math> m-1 </math> 个元素，对于任意的结点有最多 m 个子指针。对于所有内部节点，子指针的数目总是比元素的数目多一个。所有叶子都在相同的高度上，叶结点本身按关键字大小从小到大链接。

== 算法 ==

=== 查找 ===

查找以典型的方式进行，类似于[[二叉查找树]]。起始于根节点，自顶向下遍历树，选择其分离值在要查找值的任意一边的子指针。在节点内部典型的使用是[[二分查找]]来确定这个位置。

=== 插入 ===

节点要处于违规状态，它必须包含在可接受范围之外数目的元素。

# 首先，查找要插入其中的节点的位置。接着把值插入这个节点中。
# 如果没有节点处于违规状态则处理结束。
# 如果某个节点有过多元素，则把它分裂为两个节点，每个都有最小数目的元素。在树上递归向上继续这个处理直到到达根节点，如果根节点被分裂，则建立一个新根节点。为了使它工作，元素的最小和最大数目典型的必须选择为使最小数不小于最大数的一半。

=== 删除 ===

#首先，查找要删除的值。接着从包含它的节点中删除这个值。
#如果没有节点处于违规状态则处理结束。
#如果节点处于违规状态则有两种可能情况：
##它的兄弟节点，就是同一个父节点的子节点，可以把一个或多个它的子节点转移到当前节点，而把它返回为合法状态。如果是这样，在更改父节点和两个兄弟节点的分离值之后处理结束。
##它的兄弟节点由于处在低边界上而没有额外的子节点。在这种情况下把两个兄弟节点合并到一个单一的节点中，而且我们递归到父节点上，因为它被删除了一个子节点。持续这个处理直到当前节点是合法状态或者到达根节点，在其上根节点的子节点被合并而且合并后的节点成为新的根节点。

== 注解 ==

假定 <var>L</var> 是节点允许拥有子节点的最小数目，而 <var>U</var> 是最大数目。则每个节点总是有在 <var>L</var> 和 <var>U</var> 之间（包含它们在内）个子节点，除了一个例外：根节点有从''2''到<var>U</var>（包含它们在内）个子节点。换句话说，根节点豁免于低边界限制，而拥有它自己的低边界''2''。这允许树持有小数目的元素。根有一个子节点没有意义，因为附着在这个子节点上的子树可以简单的附着在根节点上。允许根节点没有子节点也是不需要的，因为没有元素的树典型的表示为没有根节点。

[[Robert Tarjan]] 证明了均摊的分裂／合并数目是 2。

== 参见 ==
*[[NTFS]]
*[[数据库]]
*[[二叉树]]
*[[B sharp tree|B# Tree]]
*[[B树]]
*[[Bitmap index]]

== 外部链接 ==
{{Wikibookspar|Transwiki|B+ tree}}
* [http://disl.cc.gatech.edu/courses/4420/05Spring/project/Bplustree.c B+ tree in C language]{{Wayback|url=http://disl.cc.gatech.edu/courses/4420/05Spring/project/Bplustree.c |date=20070703021551 }}
* [https://web.archive.org/web/20080509090511/http://www.scalingweb.com/opensource.php Open Source C++ B+ Tree Implementation]
* [http://idlebox.net/2007/stx-btree/ B+ tree implementation as C++ template library]{{Wayback|url=http://idlebox.net/2007/stx-btree/ |date=20080416021134 }}
* [http://search.cpan.org/~hanenkamp/Tree-BPTree-1.07 Perl implementation of B+ trees]{{Wayback|url=http://search.cpan.org/~hanenkamp/Tree-BPTree-1.07 |date=20080607025841 }}
* [http://bplusdotnet.sourceforge.net java/C#/python implementations of B+ trees]{{Wayback|url=http://bplusdotnet.sourceforge.net/ |date=20110724073344 }}
* [http://savutils.sf.net Your Grandmother's guide to Algorithms] Java implementation of in-memory B+-Trees and other algorithms.
* [https://web.archive.org/web/20070927071642/http://www-users.itlabs.umn.edu/classes/Spring-2006/csci4707/B+Trees.pdf Study notes for B+ Trees - Insertion and Deletion]
* [https://web.archive.org/web/20080723122307/http://www.cecs.csulb.edu/%7emonge/classes/share/B+TreeIndexes.html Dr. Monge's B+ Tree index notes]
* [http://www.virtualmachinery.com/btreeguide.htm Link to how BTrees work]{{Wayback|url=http://www.virtualmachinery.com/btreeguide.htm |date=20080416170040 }}
* [https://web.archive.org/web/20070927071643/http://www.enel.ucalgary.ca/~whassane/papers/CSB+_ccece_2007.pdf Evaluating the performance of CSB+-trees on Mutithreaded Architectures] 
* [https://web.archive.org/web/20080829230826/http://www.eecs.umich.edu/~jignesh/quickstep/publ/cci.pdf Effect of node size on the performance of cache conscious B+-trees] 
* [https://web.archive.org/web/20070928103850/http://www.pittsburgh.intel-research.net/people/gibbons/papers/fpbptrees.pdf Fractal Prefetching B+-trees] 
* [https://web.archive.org/web/20070927071643/http://gemo.futurs.inria.fr/events/EXPDB2006/PAPERS/Jonsson.pdf Towards pB+-trees in the field: implementations Choices and performance]
* [https://oa.doria.fi/bitstream/handle/10024/2906/cachecon.pdf?sequence=1 Cache-Conscious Index Structures for Main-Memory Databases]{{dead link|date=2017年11月 |bot=InternetArchiveBot |fix-attempted=yes }}
* [https://web.archive.org/web/20080612231419/http://ale3hs.aliagas.gr/content/view/23/1/ B+Tree Java SortedMap Implementation]

{{-}}
{{计算机科学中的树}}

[[Category:B树]]