Editing B+ tree (section)

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