each leaf contains at least floor( keys every key from the table appears in leafin left-to-right sorted order in our exampleswe'll continue to use for looking at our invariantsthis requires that each leaf have at least two keysand each internal node to have at least two children (and thus at least one key insertion algorithm descend to the leaf where the key fits if the node has an empty spaceinsert the key/reference pair into the node if the node is already fullsplit it into two nodesdistributing the keys evenly between the two nodes if the node is leaftake copy of the minimum value in the second of these two nodes and repeat this insertion algorithm to insert it into the parent node if the node is non-leafexclude the middle value during the split and repeat this insertion algorithm to insert this excluded value into the parent node initialinsert insert