![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Bplustree.png/640px-Bplustree.png&w=640&q=50)
B+树
維基百科,自由的 encyclopedia
B+树(英語:B+ tree)是一种树数据结构,通常用于数据库和操作系统的文件系统中。B+树的特点是能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入,这与二叉树恰好相反。
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Bplustree.png/640px-Bplustree.png)
B+树在节点访问时间远远超过节点内部访问时间的时候,比可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度,平衡操作不经常发生,而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。
B+樹背后的想法是内部节点可以有在预定范围内的可变数目的子节点。因此,B+树不需要像其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。例如,在 2-3 B 树(常简称为2-3 树)中,每个内部节点只可能有 2 或 3 个子节点。如果节点有无效数目的子节点则被当作处于违规状态。
B+树的创造者Rudolf Bayer没有解释「B」的意義,最常见的观点是代表「平衡」(balanced)或其名字「Bayer」。