Editing B-tree (section)

===Node structure===
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''. 

Note the following variable definitions:

* {{mvar|K}}&thinsp;: Maximum number of potential search keys for each node in a B-tree. (this value is constant over the entire tree).
* {{mvar|pt{{sub|i}}}}&thinsp;: The pointer to a child node which starts a sub-tree.
* {{mvar|pr{{sub|i}}}}&thinsp;: The pointer to a record which stores the data.
* {{mvar|k{{sub|i}}}}&thinsp;: The search key at the zero-based node index {{mvar|i}}.

In B-trees, the following properties are maintained for these nodes:

* If {{mvar|k{{sub|i}}}} 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).

Each internal node in a B-tree has the following format:
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
|+Internal node structure
!''pt''<sub>0</sub>
!''k''<sub>0</sub>
!''pt''<sub>1</sub>
!''pr''<sub>0</sub>
!''k''<sub>1</sub>
!''pt''<sub>2</sub>
!''pr''<sub>1</sub>
!...
!''k''<sub>''K''-1</sub>
!''pt''<sub>''K''</sub>
!''pr''<sub>''K''-1</sub>
|}
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
|+Internal node pointer structure
|
! {{math|''pt''{{sub|0}}}}
! colspan="3" | {{mvar|pt{{sub|i}}}} 
|
! colspan="2" | {{mvar|pr{{sub|i}}}} 
|-
! {{rh|align=right}} | when 
! {{math|''k''{{sub|0}}}} exists
! {{math|''k''{{sub|''i''-1}}}} and {{mvar|k{{sub|i}}}}<br/>exist
! {{math|''k''{{sub|''i''-1}}}} exists,<br/>and {{mvar|k{{sub|i}}}} does not exist
! {{math|''k''{{sub|''i''-1}}}} and {{mvar|k{{sub|i}}}}<br/>do not exist
|
! {{mvar|k{{sub|i}}}} exists
! {{mvar|k{{sub|i}}}} does not exist
|-
! {{rh|align=right}} | {{mvar|P{{sub|t}}}}&thinsp;:<br/>Points to subtree<br/>in which all search keys
| {{math|''P{{sub|t}}'' < ''k''{{sub|0}}}}
| {{math|''k''{{sub|''i''-1}} < {{var|P{{sub|t}}}} < {{var|k{{sub|i}}}}}}
| {{math|''P{{sub|t}}'' > ''k''{{sub|''i''-1}}}}
| {{mvar|pt{{sub|i}}}} is empty.
|
| Points to a record with a value<br/>{{math|''P{{sub|r}}'' {{=}} ''k{{sub|i}}''}}
| {{mvar|pr{{sub|i}}}} is empty.
|}
Each leaf node in a B-tree has the following format:
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
|+Leaf node structure
!''pr''<sub>0</sub>
!''k''<sub>0</sub>
!''pr''<sub>1</sub>
!''k''<sub>1</sub>
!...
!''pr''<sub>''K''-1</sub>
!''k''<sub>''K''-1</sub>
|}
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
|+Leaf node pointer structure
!{{mvar|pr{{sub|i}}}} when {{mvar|k{{sub|i}}}} exists
!{{mvar|pr{{sub|i}}}} when {{mvar|k{{sub|i}}}} does not exist
|-
|Points to a record with a value equal to {{mvar|k{{sub|i}}}}.
|Here, {{mvar|pr{{sub|i}}}} is empty.
|}
The node bounds are summarized in the table below:
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
! rowspan="2" | Node type
! colspan="2" | number<br/> of keys
! colspan="2" | number<br/> 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="Navathe2">{{cite book |last=Navathe |first=Ramez Elmasri, Shamkant B. |title=Fundamentals of database systems |publisher=Pearson Education |year=2010 |isbn=9780136086208 |edition=6th |location=Upper Saddle River, N.J. |pages=652–660}}</ref>
|<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
|}