Editing B+ tree (section)

==Characteristics==
The ''order'' or ''[[branching factor]]'' {{mvar|b}} of a B+ tree measures the capacity of interior nodes, i.e. their maximum allowed number of direct child nodes. This value is constant over the entire tree. For a {{mvar|b}}-order B+ tree with {{mvar|h}} levels of index:{{citation needed|date=December 2016}}
* The maximum number of records stored is <math>n_{\max} = b^h - b^{h-1}</math>
* The minimum number of records stored is <math>n_{\min} = 2\left\lceil\tfrac{b}{2}\right\rceil^{h-1}-2\left\lceil\tfrac{b}{2}\right\rceil^{h-2}</math>
* The minimum number of keys is <math>n_\mathrm{kmin} = 2\left\lceil\tfrac{b}{2}\right\rceil^{h-1}-1</math>
* The maximum number of keys is <math>n_\mathrm{kmax} = b^h-1</math>
* The space required to store the tree is <math>O(n)</math>
* Inserting a record requires <math>O(\log_bn)</math> operations
* Finding a record requires <math>O(\log_bn)</math> operations
* Removing a (previously located) record requires <math>O(\log_bn)</math> operations
* Performing a [[range query]] with ''k'' elements occurring within the range requires <math>O(\log_bn+k)</math> operations
* The B+ tree structure expands/contracts as the number of [[Row (database)|records]] increases/decreases. There are no restrictions on the size of B+ trees. Thus, increasing usability of a [[Database|database system]].
* Any change in structure does not affect performance due to balanced tree properties.<ref name=":0">{{cite book | doi=10.1007/978-3-642-12098-5_15 | chapter=Scalable Splitting of Massive Data Streams | title=Database Systems for Advanced Applications | series=Lecture Notes in Computer Science | date=2010 | last1=Zeitler | first1=Erik | last2=Risch | first2=Tore | volume=5982 | pages=184–198 | isbn=978-3-642-12097-8 | chapter-url=http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-136403 }}</ref>
* The data is stored in the leaf nodes and more branching of internal nodes helps to reduce the tree's height, thus, reduce search time. As a result, it works well in secondary storage devices.<ref>{{cite book | doi=10.1007/978-3-642-12098-5_22 | chapter=Update Migration: An Efficient B+ Tree for Flash Storage | title=Database Systems for Advanced Applications | series=Lecture Notes in Computer Science | date=2010 | last1=Xu | first1=Chang | last2=Shou | first2=Lidan | last3=Chen | first3=Gang | last4=Yan | first4=Cheng | last5=Hu | first5=Tianlei | volume=5982 | pages=276–290 | isbn=978-3-642-12097-8 }}</ref>
* Searching becomes extremely simple because all records are stored only in the leaf node and are sorted sequentially in the linked list.
* We can retrieve range retrieval or partial retrieval using B+ tree. This is made easier and faster by traversing the tree structure. This feature makes B+ tree structure applied in many search methods.<ref name=":0" />