Editing B+ tree (section)

=== 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.
|}