Editing B+ tree (section)

==Structure==
{{see also|Graph (discrete mathematics)#Graph|Tree (data structure)#Terminology}}

=== Pointer structure ===
[[File:B+tree node format.png|thumb|304x304px|B+ tree node format where K=4. (p_i represents the pointers, k_i represents the search keys).]]
As with other trees, B+ trees can be represented as a collection of three types of nodes: ''root'', ''internal'' (a.k.a. interior), and ''leaf''. In B+ trees, the following properties are maintained for these nodes:

* If <math display="inline">k_i</math> exists in any node in a B+ tree, then {{math|''k''{{sub|''i''-1}}}} exists in that node where <math>i \ge 1</math>.
* All leaf nodes have the same number of ancestors (i.e., they are all at the same depth).

The pointer properties of nodes are summarized in the tables below:

* {{mvar|K}}: Maximum number of potential search keys for each node in a B+ tree. (this value is constant over the entire tree).
* {{mvar|p{{sub|i}}}}: The pointer at the zero-based node index {{mvar|i}}.
* {{mvar|k{{sub|i}}}}: The search key at the zero-based node index {{mvar|i}}.

{| class="wikitable"
|+Internal Node Pointer Structure
|
! {{math|''p''{{sub|0}}}}
! colspan="3" | {{mvar|p{{sub|i}}}} 
|- 
! {{rh|align=right}} | when
! {{math|''k''{{sub|0}}}} exists
! {{math|''k''{{sub|''i''-1}}}} and {{mvar|k{{sub|i}}}} exist
! {{math|''k''{{sub|''i''-1}}}} exists, and {{mvar|k{{sub|i}}}} does not exist
! {{math|''k''{{sub|''i''-1}}}} and {{mvar|k{{sub|i}}}} do not exist
|-
! {{rh|align=right}} | {{mvar|P}}: Points to subtree in which all search keys
| {{math|''P'' < ''k''{{sub|0}}}}.
| {{math|''k''{{sub|''i''-1}} {{abbr|&le;|less than or equal to}} ''P'' < ''k{{sub|i}}''}}.
| {{math|''P'' {{abbr|&ge;|greater than or equal to}} ''k''{{sub|''i''-1}}}}.
| {{mvar|p{{sub|i}}}} is empty.
|}
{| class="wikitable"
|+Leaf Node Pointer Structure
!{{mvar|p{{sub|i}}}} when {{mvar|k{{sub|i}}}} exists
!{{mvar|p{{sub|i}}}} when {{mvar|k{{sub|i}}}} does not exist and <math>i \ne  K</math>
!{{mvar|p{{sub|K}}}}
|-
|Points to a record with a value equal to {{mvar|k{{sub|i}}}}.
|Here, {{mvar|p{{sub|i}}}} is empty.
|Points to the next leaf in the tree.
|}

=== Node bounds ===
The node bounds are summarized in the table below:<ref name="algorithms-pdf" /><ref>{{Cite book |last1=Silberschatz |first1=Abraham |title=Database system concepts |last2=Korth |first2=Henry F. |last3=Sudarshan |first3=S. |date=2020 |publisher=McGraw-Hill Education |isbn=978-1-260-08450-4 |edition=Seventh |location=New York, NY}}</ref>
{| class="wikitable"
|-
! rowspan="2" | Node Type 
! colspan="2" | Number of Keys
! colspan="2" | Number of Child Nodes
|-
! Min !! Max
! Min !! Max
|-
| Root Node (when it is a leaf node) || 0 || {{mvar|K}}
|0
|0
|- 
| Root Node (when it is an internal node) || 1 || {{mvar|K}}
|2<ref name="Navathe" />
|<math> K + 1 </math>
|-
| Internal Node || <math> \lfloor K/2 \rfloor </math>|| {{mvar|K}}
|<math> \lceil (K + 1)/2 \rceil \equiv \lfloor K / 2 \rfloor + 1 </math>
|<math> K + 1 </math>
|-
| Leaf Node || <math>  \lceil K / 2 \rceil </math>|| {{mvar|K}}
|0
|0
|}

===Intervals in internal nodes===
{{see also|comparability|total order|Partially ordered set#Intervals}}

[[File:Bplustree.png|thumb|400px|right|A simple B+ tree example linking the keys 1–7 to data values d<sub>1</sub>-d<sub>7</sub>. The linked list (red) allows rapid in-order traversal. This particular tree's branching factor is <math> b </math>=4. Both keys in leaf and internal nodes are colored gray here.]]

By definition, each value contained within the B+ tree is a key contained in exactly one leaf node. Each key is required to be directly [[comparability|comparable]] with every other key, which forms a [[total order]].<ref name=total-order>{{cite web |url=https://db.inf.uni-tuebingen.de/staticfiles/teaching/ss13/db2/db2-04-1up.pdf|title="Tree-Structured Indexing: ISAM and B+-trees"|last=Grust|first=Torsten|date=Summer 2013|website=Logo der Universität Tübingen Department of Computer Science: Database Systems|page=84|archive-url=https://web.archive.org/web/20201031195459/https://db.inf.uni-tuebingen.de/staticfiles/teaching/ss13/db2/db2-04-1up.pdf|archive-date=2020-10-31}}</ref> This enables each leaf node to keep all of its keys sorted at all times, which then enables each internal node to construct an ordered collection of [[Partially ordered set#Intervals|intervals]] representing the contiguous extent of values contained in a given leaf. Internal nodes higher in the tree can then construct their own intervals, which recursively aggregate the intervals contained in their own child internal nodes. Eventually, the root of a B+ Tree represents the whole range of values in the tree, where every internal node represents a subinterval.

For this recursive interval information to be retained, internal nodes must additionally contain <math>m - 1</math> copies of keys <math>l_i</math> for <math>i \in [1, m - 1]</math> representing the least element within the interval covered by the child with index {{mvar|i}} (which may itself be an internal node, or a leaf). Where {{mvar|m}} represents the ''actual'' number of children for a given internal node.