Editing B+ tree (section)

{{Short description|Data structure}}
{{Multiple issues|
{{external links|date=October 2016}}
{{more citations needed|date=November 2012}}
}}
{{Use Oxford spelling |date=March 2025}}
{{Use dmy dates |date=March 2025}}
{{Infobox data structure
|name=B+ tree
|type=[[Tree (data structure)]]
|space_avg= O(''n'')
|space_worst= O(''n'')
|search_avg= O(log ''n'')
|search_worst= O(log ''n'')
|insert_avg= O(log ''n'')
|insert_worst= O(log ''n'')
|delete_avg= O(log ''n'')
|delete_worst= O(log ''n'')
}}

A '''B+ tree''' is an [[m-ary tree]] with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves.<ref name=Navathe>{{cite book
|first1=Ramez |last1=Elmasri |author1-link=Ramez Elmasri |first2=Shamkant B. |last2=Navathe |author2-link=Shamkant Navathe |year=2010 |title=Fundamentals of database systems |edition=6th |pages=652–660 |publisher=Pearson Education |location=Upper Saddle River, N.J. |url=https://openlibrary.org/books/OL24411294M/Fundamentals_of_database_systems |isbn=9780136086208 |lccn=2010010677 |oclc=586123196 |ol=OL24411294M }}</ref> The root may be either a leaf or a node with two or more children.

A B+ tree can be viewed as a [[B-tree]] in which each node contains only keys (not key–value pairs), and to which an additional level is added at the bottom with linked leaves.

The primary value of a B+ tree is in storing data for efficient retrieval in a [[Block (data storage)|block-oriented]] storage context—in particular, [[filesystems]]. This is primarily because unlike [[binary search tree]]s, B+ trees have very high fanout (number of pointers to child nodes in a node,<ref name=Navathe /> typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.